50. Pow(x, n)
实现 pow(x, n) ，即计算 x 的 n 次幂函数。
示例 1:
输入: 2.00000, 10
输出: 1024.00000
示例 2:
输入: 2.10000, 3
输出: 9.26100
示例 3:
输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
说明:
- -100.0 < x < 100.0
- n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。
Python most votes solution:
class Solution(object):
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
if n < 0:
x = 1 / x
n = -n
pow = 1
while n:
if n & 1:
pow *= x
x *= x
n >>= 1
return pow
分析：
（1）因为输入的指数有可能是负数，所以要先对此情况进行处理，把指数是负数的情况转化为指数是正数的情况。
（2）判断条件 if n & 1 等价于 if n % 2；
移位操作 n >>= 1 等价于 n //= 2 。
（3）整个算法过程可以看成是“改变底数”与“剥离因子”的交替过程。
比如要求 (3^{10}) ，首先 (10 \% 2
e 0) ，此时会通过 x *= x 来改变底数（使底数由 3 变为 (9) ），同时，将指数除以 2。原本求 (3^{10}) 的过程就转变为求 (9^5) 。
接着进行第二轮 while 循环。注意到此时 (5 \% 2 = 1 e 0) ，因此从 (9^5) 中剥离出一个 9，并将其保存在 pow 中（即 (pow = 1 imes 9 = 9) ）。此时求 (9^5) 就变成了求 (9^4) ，同时 pow = 9。然后，再次改变底数，同时指数减半，使得求解目标变为 (81^2) 。
然后进行第三轮：(81^2 Rightarrow 6561^1) ，同时 pow = 9.
最后一轮：pow = 9 x 6561 = 59049
然后 return pow。