快速幂

（1）递归方法

根据幂运算的性质，可以得出： 计算a的n次方，如果n是偶数（不为0），那么就先计算a的n/2次方，然后平方；如果n是奇数，那么就先计算a的n-1次方，再乘上a；递归出口是a的0次方为1。

根据以上原理可以得出递归的方法。递归方法时间复杂度为logn，递归不可避免的带来空间消耗

int myPow(int a, int n){ if(n == 0){ return 1; }else if(n % 2 == 1){ return myPow(a, n-1) * a; }else{ int temp = myPow(a, n / 2); return temp * temp; } }

(2) 非递归方法

我们换一个角度来引入非递归的快速幂。还是7的10次方，但这次，我们把10写成二进制的形式，也就是（1010）₂。

现在我们要计算7^（1010）₂，可以怎么做？我们很自然地想到可以把它拆分为 [公式] . 实际上，对于任意的整数，我们都可以把它拆成若干个7^(100…) 的形式相乘。而这些7 ^ (100…)，恰好就是 7^1 、 7^2 、 7^4 ……我们只需不断把底数平方就可以算出它们。

int myPow(int a, int n){ int ans = 1; while(n != 0){ if(a & 1 != 0){ ans *= a; } a *= a; n >>= 1; } return ans; }