LeetCode-50 快速幂运算

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

示例 1:

输入: 2.00000, 10
输出: 1024.00000
示例 2:

输入: 2.10000, 3
输出: 9.26100
示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

说明:

-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

先给出最优答案 非递归位运算

3 ^ 999 = 3 3 3 … 3
直接乘要做998次乘法。但事实上可以这样做，先求出2^k次幂：

也就是从低往高走，有点像上楼梯的动态规划方法。看看有没有达到要求呀？没有达到我再翻倍。再加上原来的。但是这里不用数组保存每次的结果。

3 ^ 2 = 3 3
3 ^ 4 = (3 ^ 2) (3 ^ 2)
3 ^ 8 = (3 ^ 4) (3 ^ 4)
3 ^ 16 = (3 ^ 8) (3 ^ 8)
3 ^ 32 = (3 ^ 16) (3 ^ 16)
3 ^ 64 = (3 ^ 32) (3 ^ 32)
3 ^ 128 = (3 ^ 64) (3 ^ 64)
3 ^ 256 = (3 ^ 128) (3 ^ 128)
3 ^ 512 = (3 ^ 256) (3 ^ 256)
再相乘：
3 ^ 999 = 3 ^ (512 + 256 + 128 + 64 + 32 + 4 + 2 + 1)
= (3 ^ 512) (3 ^ 256) (3 ^ 128) (3 ^ 64) (3 ^ 32) (3 ^ 4) (3 ^ 2) 3

可以看出来，我们是把999拆成了若干个2的n次方，这不就是999的2进制表示么。
也就是我们算出3 ^ 512，再加上前面算的。

这样只要做16次乘法。即使加上一些辅助的存储和运算，也比直接乘高效得多（尤其如果这里底数是成百上千位的大数字的话）。
我们发现，把999转为2进制数：1111100111，其各位就是要乘的数。这提示我们利用求二进制位的算法（其中mod是模运算）：

把999转为2进制数：1111100111，其各位就是要乘的数,为1的话就乘一次当前x，为0的话就跳过不乘

class Solution {
    /**
     *3 ^ 999 = 3 ^ (512 + 256 + 128 + 64 + 32 + 4 + 2 + 1)
     = (3 ^ 512) * (3 ^ 256) * (3 ^ 128) * (3 ^ 64) * (3 ^ 32) * (3 ^ 4) * (3 ^ 2) * 3
     把999转为2进制数：1111100111，其各位就是要乘的数,为1的话就乘一次当前x，为0的话就跳过不乘
     */
    static double myPow(double x, int n) {

        if(n == 0 || x == 1 ) return 1;
        if(x == -1 ) return  n % 2 != 0 ? -1 : 1;
        if(n > Integer.MAX_VALUE || n <= Integer.MIN_VALUE) return 0;
        if(n == 1) return x;
        boolean flag = n < 0 ? false : true;//1表示正
        n = flag ? n : -n;//根据正负修改

        double result = 1;
        while (n > 0)
        {
            if (n % 2 != 0) {        //若为奇数则乘一次当前的x  若为偶数的话不乘x
                result *= x;
            }
            n >>= 1;          //右移一位相当于n/2(类比十进制来理解),计算一次少一倍
            x *= x;            //计算一次翻一倍
        }
        return flag ? result : 1 / result;
    }
}

递归解法

class Solution {
       public static double myPow(double x, int n) {
        double r;
        if(n==0) return 1.0;
        if(n==1) return x;
        if(n%2 == 0) {
            r = myPow(x, n/2);
            return r*r;
        }
        else {
            if (n < 0) {
                r = myPow(x, -n/2);
                return 1 / (x * r * r);
            } else {
                r = myPow(x, n/2);
                return x * r * r;
            }
        }
    }
}