---
title: "快速幂以及求幂运算结果的位数"
description: "快速幂: 时间复杂度O(logn)，求位数: 时间复杂度O(1)"
canonical_url: "https://yangqiuyi.com/blog/suan-fa/kuai-su-mi-yi-ji-qiu-mi-yun-suan-jie-guo-de-wei-shu"
---
> Index of every page on this site: [llms.txt](https://yangqiuyi.com/llms.txt)
快速幂: 时间复杂度O(logn)，求位数: 时间复杂度O(1)
## 位数
我们知道
1
0
n
的长度是
n
+
1
，所以只要把底数变成10，就可以计算结果的长度，同时又知道
x
n
=
(
1
0
l
o
g
x
)
n
=
1
0
n
l
o
g
x
，所以
x
n
的长度就是
n
l
o
g
x
+
1
，C++数学库当中有log10()函数，可以很方便地计算
l
o
g
10
x
## 快速幂
这玩意儿不难，比如
a
13
，指数13转化为二进制是1101，然后再把1101转化成十进制，就是
2
0
+
0
1
+
2
2
+
2
3
，因此可以把
a
13
看成
a
2
0
+
0
1
+
2
2
+
2
3
，也就是
a
2
0
a
0
a
2
2
a
2
4
，所以需要用到循环，并且指数转化为二进制之后有几位，就需要循环几次。
#### Code
```cpp
#include
using namespace std;
//快速幂
int poww(int base, int index)
{
int res = 1;
while (index != 0)
{
if (index & 1 != 0)
{
res *= base;
}
base *= base;
index >>= 1; //删除最后一位二进制位，举个例子，11001>>=1,结果就是1100
}
return res;
}
int main()
{
int base=2,index=13; // 求 2 的 13 次方
cout << "reslut:" << poww(base,index) << endl;
cout << "length:"
<< int(index*log10(base)+1); //计算位数
return 0;
}
```
通过观察代码，可以发现每循环一次，base就会进行一次自乘
第1次循环：res=base=2,base=base×base=4
第2次循环：res没有变，因为13转化成小数后第二位是0，所以res=res×1，base=base×base=16
第3次循环：res=res×base=2×16=32，base=base×base=256
第四次循环，也就是最后一次循环：
res=res×256=2×16×256,base=256*256
最后return res;
原本需要13次循环才能算出2^13，现在只要四次，快了很多。
## Sitemap
See the full [sitemap](https://yangqiuyi.com/sitemap.md) for all pages.