Pow(x, n)

Pow(x, n)

Implement pow(x, n).

Naive Way: brute force是O(n)。很明显x^5 = x^2 * x^2 * x 是缩小时间复杂度的关键。这里还要记得有负数次幂的情况。经观察和我第一次做时看别人做法的记忆，7=4+2+1 是核心。
x^7 = x^4 + x^2 + x^1。
那么先将[x^1,x^2,x^4...x^(logn)]罗列出来，
第一次n=7， 7/4 = 1...3 说明有一个x^4,
第二次n=3,    3/2 = 1...1 说明有一个x^2,
第三次n=1,    1/1 = 1...0 说明有一个x^1。
要注意如果商是0，说明没有对应项的乘因子，就不乘或者乘1.0。

这样就变成了不断取最高位的算法。算法复杂度是O(logn)，space是O(logn)

public class Solution {
    public double pow(double x, int n) {
        if(n==0 || x==1.0){return 1.0;}
        if(x==-1.0){return n%2==0?1.0:-1.0;}
        if(n < 0){return 1.0/pow(x,-n);}
        int len = (int)Math.floor(Math.log(n)/Math.log(2));
        double rlst = 1.0;
        double[] carry = new double[len+1];
        for(int i = 0;i <= len;i++)
            carry[i] = i==0?x:Math.pow(carry[i-1],2);
        while(n!=0){
            int num = n/(int)Math.pow(2,len);
            rlst *= num==0?1.0:carry[len]*num;
            n %= (int)Math.pow(2,len--);
        }
        return rlst;
    }
}


Improved Way:x^7 = x^4 + x^2 + x^1的这个信息，其实就藏在7这个数的比特位中，7 = 0x0111,
只需要用比特运算就可以提取对应位了。并且，因为这样不需要从高往低乘，可以从低往高乘，那么低位的乘因子乘过以后就不会再用了，不需要一直存着，可以通过与比特位递进同步平方乘因子，达到O(1)space的效果。

这种方法也太牛了，居然只用O(1) run time 和O(1) space。

public class Solution {
    public double pow(double x, int n) {
        if(n < 0){return 1.0/(n==Integer.MIN_VALUE?x*pow(x,-(n+1)):pow(x,-n));}
        double rlst = 1.0;
        while(n!=0){
            if((n & 1) == 1){
                rlst*= x;
            }
            x*=x;
            n = n >> 1;
        }
        return rlst;
    }
}