problem：
thinking：
（1）最简单想到的是直观上的数学幂函数求法，測试通过。算法时间复杂度为O（n）
（2）依照标签提示，使用二分搜索法。
pow(x,n) = pow(x,n-n/2)*pow(x,n/2),每次对n的规模缩半,注意对n的奇偶进行讨论,算法时间复杂度为log（n）
（3）除了上述方法，这里还提到了一种十分巧妙而且高速的方法，原文描写叙述例如以下：
Consider the binary representation of n. For example, if it is "10001011", then x^n = x^(1+2+8+128) = x^1 * x^2 * x^8 * x^128. Thus, we don't want to loop n times to calculate x^n. To speed up, we loop through each bit, if the i-th bit is 1, then we add x^(1
<< i) to the result. Since (1 << i) is a power of 2, x^(1<<(i+1)) = square(x^(1<<i)). The loop executes for a maximum of log(n) times.
该方法通过扫描n的二进制表示形式里不同位置上的1，来计算x的幂次，最坏为O（n），但平均复杂度非常好
code：
（1）递归法：accepted
class Solution {
public:
double pow(double x, int n) {
double ret=1.0;
if(x==1.0 )
return 1.0;
if(x==-1.0)
{
if(n%2==0)
return 1.0;
else
return -1.0;
}
if(n<0)
return 1.0/pow(x,-n);
while(n)
{
if(ret==0) //防止执行超时
return 0;
ret*=x;
n--;
}
return ret;
}
};
（2）二分法：accepted
class Solution {
public:
double pow(double x, int n) {
//double ret=1.0;
if(x==1.0 )
return 1.0;
if(x==-1.0)
{
if(n%2==0)
return 1.0;
else
return -1.0;
}
if(n==0)
return 1.0;
if(n<0)
return 1.0/pow(x,-n);
double half=pow(x,n>>1);
if(n%2==0)
return half*half;
else
return x*half*half;
}
};
（3）
为了正确计算x的n次幂，还须要考虑到下面一些情况：
1) x取值为0时。0的正数次幂是1，而负数次幂是没有意义的；推断x是否等于0不能直接用“==”。
2) 对于n取值INT_MIN时。-n并非INT_MAX。这时须要格外小心。
3) 尽量使用移位运算来取代除法运算，加快算法运行的速度。
class Solution {
public:
double pow(double x, int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(n<0)
{
if(n==INT_MIN)
return 1.0 / (pow(x,INT_MAX)*x);
else
return 1.0 / pow(x,-n);
}
if(n==0)
return 1.0;
double ans = 1.0 ;
for(;n>0; x *= x, n>>=1)
{
if(n&1>0)
ans *= x;
}
return ans;
}
};