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

• 题目链接：50. Pow(x, n) (opens new window)；
• 题解链接：自顶向下（递归）与自顶向上（递推） (opens new window)。

今天要和大家分享的是「力扣」第 50 题：Pow(x, n)。这题有一个名称叫「快速幂」，我们这里只分享「递归」和「非递归」的写法，其中 「递归」对应「当指数为奇数时，把指数分解成偶数 + 1，当指数为偶数时，把指数除以 2」，「非递归」对应把指数转化成二进制。「快速幂」还有矩阵的求法，感兴趣的朋友可以在网络上自行搜索（我也不会）。

题目描述

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

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

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

提示：

• $-100.0 < x < 100.0$
• $-2^{31} \le n \le 2^{31}-1$
• $-10^4 \le x^n \le 10^4$​

把指数部分看做二进制数（Python 代码）

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

为了避免一次又一次将底数相乘，我们采用这样“偷懒”的策略，比如要计算 $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$ 做“二进制分解”，在底数不断自身乘以自身的过程中，将最终结果需要的部分保存下来。

写得比较晦涩，相信聪明的你看我写的代码一定能看懂。

class Solution:
    def myPow(self, x: float, n: int) -> float:

        if n < 0:
            x = 1 / x
            n = -n

        res = 1
        while n:
            if n & 1:
                res *= x
            x *= x
            n >>= 1
        return res