LeetCode 50 Pow(x, n)
Implement pow(x, n).
遇到math类的题，比如pow(x,n)，reverse integer，divide two integer，pow of two等，都需要判断overflow问题！！！
常见的overflow包括：
- int是否越界，包括两个int相加，相乘，相除是否会超过int的范围。注意java中的int类型存储长度为32bit.所以范围是-232到232-1，也就是-2147483648到2147483647。因此当-2147483648需要取相反数时就会产生越界！！！
- Math.abs(-2147483648)仍为-2147483648！！！
- 除法中除数为0时，会产生overflow。被除数为-2147483648，除数为-1时，也会因为2147483648而越界！！！
- 对于pow(x,n)，n=0时pow(x,n)=1；x=0时，pow(x,n)=0！！！
- 二分法求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))。
为了加速幂的求解，可以用分治法，将xn拆分为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;
}
}
