快速幂: 时间复杂度O(logn)，求位数: 时间复杂度O(1)

位数

我们知道 $10^n$的长度是 $n+1$，所以只要把底数变成10，就可以计算结果的长度，同时又知道$x^n={(10^{logx})}^n=10^{nlogx}$，所以$x^n$的长度就是$nlogx+1$，C++数学库当中有log10()函数，可以很方便地计算$log_{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

#include <bits/stdc++.h>

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，现在只要四次，快了很多。