LeetCode 50 Pow(x, n)

Implement pow(x, n).

遇到math类的题，比如pow(x,n)，reverse integer，divide two integer，pow of two等，都不需要判断overflow问题！！！

常见的overflow包括：

1. int是否越界，包括两个int相加，相乘，相除是否会超过int的范围。注意java中的int类型存储长度为32bit.所以范围是-2^32到232-1，也就是-2147483648到2147483647。因此当-2147483648需要取相反数时就会产生越界！！！
2. Math.abs(-2147483648)仍未-2147483648！！！
3. 除法中除数为0时，会产生overflow。被除数为-2147483648，除数为-1时，也会因为2147483648而越界！！！
4. 对于pow(x,n)，n=0时pow(x,n)=1；x=0时，pow(x,n)=0！！！
5. 二分法求mid时，为了避免越界写成如下形式：mid=left+(right-left)/2。

对于上述问题，常见的解决-2147483648的方法是：

在求-2147483648的相反数或绝对值前，先将-2147483648转为long型，在long的状态下操作后，返回时再(int)转回int型。

对于本题，当幂为n=-2147483648时，首先将n+1，再取绝对值后计算剩余的值：pow(x,-(n+1))，最终结果为x*pow(x,-(n+1))。

为了加速幂的求解，可以用分治法，将x^n拆分为x2 * x^2 * ... * x^2 * x^1，这样的形式迭代求解。

代码如下：

public class Solution {
    public double myPow(double x, int n) {
        // Deal with corner case
        if (x == 0) return 0.0;
        if (n == 0) return 1.0;
        
        double ans = 1.0;
        // Seperate positive and negative cases:
        if (n > 0) {
            ans = myPowRecursive(x, n);
            return ans;
        } else {
            ans = x * myPowRecursive(x, -(n + 1));
            return 1.0 / ans;
        }
    }
    
    public double myPowRecursive(double x, int n) {
        if (n == 0) return 1.0;
        if (n == 1) return x;
        double res;
        res = myPowRecursive(x, n/2);
        if (n % 2 == 1)
            return x * res * res;
        else 
            return res * res;
    }
    
}