快速幂




递归版 非常好想但是比较费空间

int qpow(int a,int n){

    if( n == 0 ) return 1;

    else if ( n%2 == 1)  return qpow( a, n-1 )*a;

    else{

        int temp = qpow(a, n / 2);        

        return temp * temp;

    }


}

必须要用一个temp，否则会退化成O(n)算法。




非递归快速幂


int qpow(int a, int n){

   int ans = 1;    

   while(n){        

        if(n&1)        //如果n的当前末位为1            

        ans *= a;  //ans乘上当前的a        

        a *= a;        //a自乘        

        n >>= 1;       //n往右移一位    

    }    

    return ans;

}