题目链接：Pow(x, n)
Implement pow(x, n).
这道题的要求是实现pow(x, n)函数。
求x的n次幂。直接的暴力思路，将x乘以自身n次即可，时间复杂度O(n)。当n非常大时，计算时间过长。
考虑将n转化为二进制数，即n = a0*2^0 + a1*2^1 + a2*2^2 + … + an*2^n。而求x的n次幂，即为x^n = x^(a0*2^0 + a1*2^1 + a2*2^2 + … + an*2^n) = x^(a0*2^0) * x^(a1*2^1) * x^(a2*2^2) * … * x^(an*2^n)。
例如当n等于11的时候，
n=11: 1 0 1 1 （高位->低位）
结果: x^4 x^2 x^1（连乘的结果）
因此，每次将n除以2，将x乘以x，这样，当二进制的某位为1时，将此时的x乘到结果上。
注意一个问题，当n为负数的时候，需要将结果用1除一下。同时，由于负数右移1位并不等于除以2，因此不能为了提高速度而用移位来代替除以2的运算。
时间复杂度：O(logn)
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
class Solution
{
public:
double pow(double x, int n)
{
double res = 1.0;
for(int i = n; i != 0; i /= 2, x *= x)
if(i & 1)
res *= x;
return n >= 0 ? res : 1.0 / res;
}
};