遞歸版 非常好想但是比較費空間

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;

}