50. Pow(x, n) -M

Q:
Implement pow(x, n).

A:
----------4th pass---------Iterative way ------------

public class Solution {
    public double pow(double x, int n) {
        if(n<0)
            return 1/(x*pow(x,-(n+1)));
        double result = 1;        
        while(n!=0){
            if(n%2 ==1)
                result *= x;                
            x = x*x;
            n = n>>1;       
        }
        return result;   
    }
}

Mistakes:
1:   第一次实现的时候，，没有考虑效率。   就直接n 个x连乘了。
2:  当建立ArrayList 的时候，    while (al.get(al.size() - 1) *  2 <n) {   但是这里，应该是 <= n 的
3：


Learned:
1:计算以2为底的log函数

-----------------3rd pass -------------------直接来计算----------
Error:
1: 刚开始，分开考虑 n 的正负号。 但真因为这样，  负数转正数会有溢出的情况。
    public double pow(double x, int n) {
        if(n==0)
            return 1;
        if(n<0)
            return 1/powPos(x,-n);
        // now n>0
        return powPos(x,n);
    }
因此，上面是不对的。
2：    double  powPos（）的base case应该是 n == 0;
教训阿， 还是分情况简单好记。 否则的话，会容易惹出不必要的错误。 而且既然自己不太熟悉 bit 操作。 那就在面试的时候尽量避免。

class Solution {
public:
    double myPow(double x, int n) {
        if(n<0)
            return 1 /(x* myPow(x, -(n+1)));   // n -> -n  can have overflow if n<0
        if(n==0)
            return 1;
        double res = n&1 ? x : 1;
        double half = myPow(x, n/2);
        return res * half * half;
    }
};

最终改成了：  -----------  教训：  当int 负数变正数的时候，一定要检查是否有溢出。 （或者我们就一直用负数来搞。

public class Solution {
    public double pow(double x, int n) {
        return pow2(x,n);
    }
    private double pow2(double x, long n){
        if(n==0)
            return 1;
        if(n<0)
            return 1/pow2(x,-n);

        double b = pow2(x,n/2);
        if(n%2==0)
            return b*b;
        else
            return b*b*x;
    }
}

--------------------都当作负数来搞------------------------------------

public class Solution {
    public double pow(double x, int n) {
        if(n==0)
            return 1;
        if(n==-1)
            return 1/x;
        if(n>0)
            return 1/pow(x,-n);
            
        double b = pow(x,n/2);
        if(n%2==0)
            return b*b;
        else
            return b*b*1/x;
    }
}