**binary-search medium **

题目

实现 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/2^2 = 1/4 = 0.25

说明：

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

思路

本题的方法被称为「快速幂算法」，有递归和迭代两个版本。这篇题解会从递归版本的开始讲起，再逐步引出迭代的版本。

当指数 n 为负数时，我们可以计算 ，再取倒数得到结果，因此我们只需要考虑 n 为自然数的情况。

方法一：快速幂 + 递归

「快速幂算法」的本质是分治算法。举个例子，如果我们要计算，我们可以按照：

的顺序，从 x 开始，每次直接把上一次的结果进行平方，计算 6 次就可以得到 的值，而不需要对 x 乘 63 次 x 。

再举一个例子，如果我们要计算，我们可以按照：

的顺序，在这些步骤中，我们直接把上一次的结果进行平方，而在这些步骤中，我们把上一次的结果进行平方后，还要额外乘一个 x 。

直接从左到右进行推导看上去很困难，因为在每一步中，我们不知道在将上一次的结果平方之后，还需不需要额外乘 x 。但如果我们从右往左看，分治的思想就十分明显了：

• 当我们要计算 时，我们可以先递归地计算出，其中表示对 a 进行下取整；
• 根据递归计算的结果，如果 n 为偶数，那么 ；如果 n 为奇数，那么 ；
• 递归的边界为 n = 0 ，任意数的 0 次方均为 1 。

由于每次递归都会使得指数减少一半，因此递归的层数为 ，算法可以在很快的时间内得到结果。
复杂度分析

• 时间复杂度：，即为递归的层数。
• 空间复杂度：，即为递归的层数。这是由于递归的函数调用会使用栈空间。

代码实现

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def quickMul(N):
            if N == 0:
                return 1.0
            y = quickMul(N // 2)
            return y * y if N % 2 == 0 else y * y * x

        return quickMul(n) if n >=0 else 1.0 / quickMul(-n)

方法二：快速幂 + 迭代

由于递归需要使用额外的栈空间，我们试着将递归转写为迭代。在方法一中，我们也提到过，从左到右进行推导是不容易的，因为我们不知道是否需要额外乘 x 。但我们不妨找一找规律，看看哪些地方额外乘了 x ，并且它们对答案产生了什么影响。

利用十进制数字 n 的二进制表示，可对快速幂进行数学化解释。

• 对于任何十进制正整数 n ，设其二进制为 ，为二进制某位值，，则有：
  • 二进制转十进制： （即二进制转十进制公式）；
  • 幂的二进制展开：
• 根据以上推导，可把计算 转化为解决以下两个问题：
  • 计算 的值： 循环赋值操作 即可；
  • 获取二进制各位 的值：循环执行以下操作即可。
    • （与操作）： 判断 n 二进制最右一位是否为 1 ；
    • （移位操作）： n 右移一位（可理解为删除最后一位）。

因此，应用以上操作，可在循环中依次计算的值，并将所有 累计相乘即可，其中：

我们还是以 作为例子：

并且把需要额外乘 x 的步骤打上了 + 标记。可以发现：

• 中额外乘的 x 在 中贡献了 x ；
• 中额外乘的 x 在之后被平方了 2 次，因此在 中贡献了 ；
• 中额外乘的 x 在之后被平方了 3 次，因此在 中贡献了 ；
• 最初的 x 在之后被平方了 6 次，因此在 中贡献了 。

我们把这些贡献相乘，。而这些贡献的指数部分又是什么呢？它们都是 2 的幂次，这是因为每个额外乘的 x 在之后都会被平方若干次。而这些指数 1,4,8,64 ，恰好就对应了 77 的二进制表示中的每个 1 ！

因此我们借助整数的二进制拆分，就可以得到迭代计算的方法，一般地，如果整数 nn 的二进制拆分为

那么

这样以来，我们从 x 开始不断地进行平方，得到 如果 n 的第 k 个（从右往左，从 0 开始计数）二进制位为 1 ，那么我们就将对应的贡献计入答案。

转化为位运算：**

• 向下整除 等价于 右移一位 ；
• 取余数 等价于 判断二进制最右位 ；

算法流程：

1. 当 x = 0.0 时：直接返回 0.0 ，以避免后续 1 除以 0 操作报错。分析：数字 0 的正数次幂恒为 0 ； 0 的 0 次幂和负数次幂没有意义，因此直接返回 0.0 即可。
2. 初始化 res = 1 。
3. 当 n < 0 时：把问题转化至 的范围内，即执行 x = 1/x ， n = -n 。
4. 循环计算：当 n = 0 时跳出。
   1. 当 时：将当前 x 乘入 res （即 res *= x ）。
   2. 执行 （即 x *= x ）。
   3. 执行 n 右移一位（即 n >>= 1 ）。
5. 返回 res 。

复杂度分析：

• 时间复杂度 ：二分的时间复杂度为对数级别。
• 空间复杂度 ： res , b 等变量占用常数大小额外空间。

代码实现

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0: return 0.0
        res = 1
        if n < 0:
            x, n = 1 / x, -n
        while n:
            if n & 1:
                res *= x
            x *= x
            n >>= 1
        return res

• 作者：LeetCode-Solution
• 链接：https://leetcode-cn.com/problems/powx-n/solution/powx-n-by-leetcode-solution/
• 作者：jyd
• 链接：https://leetcode-cn.com/problems/powx-n/solution/50-powx-n-kuai-su-mi-qing-xi-tu-jie-by-jyd/