question：pow(a,b)；

传统的算法是

int ans = 1;

for(int i = 1;i<=b;i++)

{

ans = ans * a;

}

这个算法的时间复杂度体现在for循环中，为O（b）.这个算法存在着明显的问题，如果a和b过大，很容易就会溢出。

所以我们换一种思想：

1.位运算思想：

假设我们要求a^b，那么其实b是可以拆成二进制的，该二进制数第i位的权为2^(i-1)，例如当b==11时

  a^11=a^(2^0+2^1+2^3)

11的二进制是1011，11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1，因此，我们将a¹¹转化为算 a^(2^0)*a^(2^1)*a^(2^3)，看出来快的多了吧原来算11次，现在算三次，但是这三项貌似不好求的样子….不急，下面会有详细解释。由于是二进制，很自然地想到用位运算这个强大的工具： &  和 >>  ，&运算通常用于二进制取位操作，例如一个数 & 1 的结果就是取二进制的最末位。还可以判断奇偶x&1==0为偶，x&1==1为奇。>>运算比较单纯,二进制去掉最后一位。直接看代码吧：

int poww(int a,int b){
    int ans=1,base=a;
    while(b!=0){
        if(b&1!=0)
        　　ans*=base;
        base*=base;
        b>>=1;
　 }
    return ans;
}

这就是利用二进制拆解和位运算来求，复杂度可以降低到O(logn).

2.二分的思想：

预备知识：a^b=(a^2)^(b/2)(b为偶数)，a^b=(a^2)^(b/2)*a(b为奇数)，实际上与上面是一样的，只不过是更加直观的二分形式：

直接上代码：

int fastpow(int m,int n)
{
    int ans=1;
    while(n)
    {
        if(n&1)
        {
            ans*=m;
        }
        m*=m;
        n/=2;
    }
    return ans;
}

因为使用快熟幂的情景一般都是数字非常大的，所以题目会要求取模运算，取模经常与快速幂一起出现，所以只需要在快速幂代码上稍微修改一下就变成快速幂取模了：

先引入一些预备知识：

取模运算法则：

（a+b)%c=(a%c+b%c)%c

（a*b)%c=(a%c)*(b%c)%c

所以a^b%c=(a^2%c)^(b/2)%c(b为偶数)，a^b=(a^2%c)^(b/2)*a%c(b为奇数)

代码：

int fastpow(int m,int n,int p)
{
    int ans=1;
    m=m%p;
    while(n)
    {
        if(n&1)
        {
            ans=(m*ans)%p;
        }
        m=(m*m)%p;
        n/=2;
    }
    return ans;
}