快速幂就是快速求a^b

       直接for循环的时间复杂度是o（n),比较low。那么如何提高时间复杂度呢，幂的本质是连乘，其中b可以写成二进制，拆成2的幂。拿a的11次方为例，11的二进制是1011，所以可以得到11=2⁰+2¹+2³，于是，a的11次方可以写成a^2⁰ * a^2¹ * a^2³,这样就变成三个数的乘积了，快了很多，那么怎么求这三个数呢，看看我们怎么写出这三个数的，没错，就是二进制，位数就是2的幂，整个流程就是从右往左搞，0就不管他，1就将a^2ⁿ乘进ans。

                                      

这是迭代

 

int mypow(int a,int b)
{
    int ans=1;//答案
    while(b!=0)//从右往左取，如果是零次幂就返回1
    {
        if(b&1)//如果这一位是1
        ans*=a;//就要乘上相对应的a的幂
        a*=a;//每移一位就将计算新的a的幂
        b>>=1;//移位
    }
    return ans;
}

 

 

       同时，这可以用递归实现，思想是把a的n次方变成两个a的n/2次方相乘，就像2的100次方等于4的五十次方=8的25次方……

 

int mypow(int a,int b)
{//求出a的b次方的结果
    int ans;
    if(b==0)//终止条件，a的0次幂是一
    return 1;
    ans=mypow(a*a,b/2);//求出a^2的b/2次方的结果
    if(b%2==1)//在本层，如果b是奇数，意味着上一步会少乘了一个a,所以补上
    ans=ans*a;
    return ans;
}