求解一个数的 n次方，我们一般直接累乘 n次，就像下面的代码一样：
def pow(x, n):
result = 1
for i in range(n):
result *= x
return result
但是这种方法只能用于指数 n比较小的情况，如果指数 n非常大的话，这种方法就不再适用了。
遇到这种情况下快速幂算法能够很好的解决我们的需求。
递归实现
观察 x^10 = x^5 * x^5
而 x^5 = x^4 * x
而 x^4 = x^2 * x^2
而 x^2 = x * x
即：x->x2->x5->x^10
根据上面的观察我们可以发现，下一步的结果总是上一步的平方或者上一步的平方再乘 x。
这样我们可以按照下面的规则从右边向左边计算：
- 计算 x^[n/2]。
- 如果 n是偶数，直接返回，否则乘上 x再返回。
- 如果 n=1，返回 x。
我们可以用递归来实现这个算法：
import math
def pow(x, n):
if n == 1:
return x
r = pow(x, math.floor(n/2))
return r*r if n%2 == 0 else r*r*x
迭代实现
任意一个正整数都可以用二进制来表示，比如：7 = 111(2) = 2^2 + 2^1 + 2^0
所以：x^7 = x ^ (2^2 + 2^1 + 2^0) = x^4 * x^2 * x
我们可以发现前一个式子总是后一个式子的 2n次方。
所以我们只要计算 x, x^2, x^4, x^8, ... , x^(2^n) ，然后根据 n的二进制表示来判断对应位是否带入计算，如果第 n位为 1，则结果乘上 x^(2^n)，然后计算 x^(2^(n+1))，否则只计算 x^(2^(n+1))。
代码如下：
def pow(x, n):
target = x
result = 1
while n > 0:
if (n & 1) == 1:
result *= target
n = n >> 1
target *= target
return result
如果考虑 n为负数的情况，只需要在前面添加判断即可。
如果 n为负数，则 x = 1/x, n=-n。
