「力扣」第 50 题：Pow(x, n)

这题我提供了「自顶向下」与「自顶向上」的解决办法。「自顶向下」是分治算法、递归实现。「自顶向上」借助了指数的二进制分解。

方法一：分而治之（自顶向下思考问题）

我们的目的是 降低指数的值，因此可以将问题进行不断拆分，直到不能拆分为止，再一层一层向上传递结果。以下是计算 $2^7$ 的示意图。

参考代码 1：

public class Solution {

    public double myPow(double x, int n) {
        long b = n;
        if (n < 0) {
            return 1 / myPow(x, -n);
        }
        return myPow(x, b);
    }

    private double myPow(double x, long n) {
        if (n == 0) {
            return 1;
        }
        if ((n % 2) == 1) {
            return x * myPow(x, n - 1);
        }
        return myPow(x * x, n / 2);
    }
}

方法二：自底向上

当指数为负数的时候，可以转化为底数取倒数，指数取相反数的情况，这一点并不难理解。

为了避免一次又一次将底数相乘，我们采用这样「偷懒」的策略，比如要计算 $5^{18}$ ，其实我们只要算出 $5^9$ ，然后再自己乘自己就好了，这样就可以避免做 $9$ 次 $\times 5$ 的运算。

有一种办法可以帮助我们找到一个整数的合适的「分解」，那么就是将一个整数看成它的二进制形式。就那上面的例子来说， $18$ 的二进制表示为 $(10010)_2$ ，即：

18 = 1 \times 2^4 + 1\times2^1

那么：

5^{18} = 5^{2^4} \times 5^{2^1}

于是，我们可以把指数 $n$ 做「二进制分解」，在底数不断自身乘以自身的过程中，将最终结果需要的部分保存下来。

参考代码 2：

public class Solution {

    public double myPow(double x, int n) {
        // 注意：这里的类型转换
        // 应对 -2147483648 这种用例
        long b = n;
        if (n < 0) {
            x = 1 / x;
            b = -b;
        }

        double res = 1.0;

        while (b > 0) {
            if ((b % 2) == 1) {
                res *= x;
            }
            x *= x;
            b >>= 1;
        }
        return res;
    }
}