剑指 Offer 16. 数值的整数次方 (opens new window)

1.倍增算法

分析：采用快倍增算法，计算x的2、4、8、16...次方的结果。计算n次幂时，每次计算不大于n的最大2的指数次方幂。具体来说计算n=24次方时，计算顺序为16，8此方。

class Solution {
    public double myPow(double x, int n) {
        x=n<0?1/x:x;
        long b=n;
        double[] dp=new double[32];
        dp[0]=x;
        for(int i=1;i<dp.length;i++){
            dp[i]=dp[i-1]*dp[i-1];
        }
        long step=2147483648l;
        double res=1;
        b=Math.abs(b);
        if(b==4294967296l) return dp[31]*dp[31];
        for(int i=31;i>=0;i--){
            if(b>=step) {
                res*=dp[i];
                b-=step;
                if(b==0) break;
            }
            step=step>>1;
        }
        return res;
    }
}

2.递归+快速幂

思路和上述类似，但是此处不需要找出最大2的指数次幂的结果。次数计算也是从后往前计算。具体来说计算n=24的结果时，先计算12次方的结果，然后12次方结果依赖于6次方结果，接着是3次方，最后是1次方。