Implement pow(x, n).
Example 1:
Input: 2.00000, 10
Output: 1024.00000

Example 2:
Input: 2.10000, 3
Output: 9.26100

double myPow(double x, int n) 
{
    if(n == 0)
        return 1.0;
    
    if(n == 1)
        return x;
    
    long long int m = n > 0 ? n : -n;
    double ans = x;
    long long int cur = 1.0;
    
    while(2 * cur < m)
    {
        cur = cur * 2;
        ans = ans *ans;
    }
    ans = ans * myPow(x,m-cur);
    return n>0 ? ans : 1.0/ans;
}

经验与教训

这道简单的题目实际上有两个坑要处理，就是INT_MIN比INT_MAX大一，如果n为INT_MIN取反后越界，因此不能使用for循环从1到n，然后去乘，假设我们要计算2的64次方，实现思路是计算x的2次方、4次方、8次方、16次方、2的32次方、2的64次方。
假设我们要计算2的63次方，实现思路是计算x的2次方、4次方、8次方、16次方、2的32次方、然后计算2的m-cur=63-32=31,ans*2的31次方即是2的63次方。
还有就是必须要采用这种”折半“的方法进行计算，否则会出现超时。

2020.10.28更新

上面的代码提交后发现错误，比较尴尬的是原因在上面的经验教训中写的很清楚了，但是上面却存在这个问题。当n为INT_MIN时，上面代码中long long int m = n > 0 ? n : -n;会报错（-n的值已经超越了int能表示的最大范围)。
错误内容:

Line 8: Char 19: runtime error: negation of -2147483648 cannot be represented in type 'int'; cast to an unsigned type to negate this value to itself [solution.c]

正确的处理方法是先把n赋值给精度更广的m，然后再取绝对值即可:

double myPow(double x, int n) 
{
    if(n == 0)
        return 1.0;
    if(n == 1)
        return x;
    
    long long m = n;
    m = m > 0 ? m : -m;
    
    double ans = x;
    long long int cur = 1.0;
    
    while(2 * cur < m)
    {
        cur = cur * 2;
        ans = ans *ans;
    }
    ans = ans * myPow(x,m-cur);
    return n>0 ? ans : 1.0/ans;
}

这里递归的形式是：

class Solution {
public:
    double myPow(double x, int n) {
        if(n == 0) return 1;
        double t = myPow(x,n/2);
        if(n%2)
        {
            return n>0 ? x*t*t:1.0/x*t*t;
        }
        else
        {
            return t*t;
        }
    }
};