わたしの部屋

2.1 算法原理#

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

对于任何十进制正整数 $n$，设其二进制表示为 $b_m \dots b_3 b_2 b_1$（其中 $b_i \in \{0, 1\}$，$i \in [1, m]$），则有：

• 二进制转十进制： $n = 1b_1 + 2b_2 + 4b_3 + \dots + 2^{m-1}b_m$
• 幂的二进制展开： $x^n = x^{1b_1 + 2b_2 + 4b_3 + \dots + 2^{m-1}b_m} = x^{1b_1} x^{2b_2} x^{4b_3} \dots x^{2^{m-1}b_m}$

根据以上推导，可把计算 $x^n$ 转化为解决以下两个问题：

1. 计算 $x^1, x^2, x^4, \dots, x^{2^{m-1}}$ 的值： 循环赋值操作 $x = x^2$ 即可。
2. 获取二进制各位 $b_1, b_2, b_3, \dots, b_m$ 的值： 循环执行以下操作：
   • n & 1（与操作）： 判断 $n$ 二进制最右一位是否为 1。
   • n >> 1（移位操作）： $n$ 右移一位（相当于删除最后一位）。

因此，在循环中依次处理 $x^{2^0}, x^{2^1}, \dots, x^{2^{m-1}}$，并把所有二进制位为 $1$ 的项累计相乘即可。

下图直观地展示了迭代计算中 $x$ 的平方以及 $n$ 二进制位的变化过程：

2.2 迭代过程示例：以 $3^{13}$ 为例#

以上面的二进制拆分为基础，我们可以进一步观察快速幂循环中各个变量的变化过程。

对于 $3^{13}$：

$13 = 1101_2$

也就是：

$13 = 8 + 4 + 1$

所以最终应该只选择：

$3^1 \text{、} 3^4 \text{、} 3^8$

而 $3^2$ 只是循环过程中产生的候选值，并不会参与最终结果相乘。

快速幂循环中，x 会不断平方，依次表示：

$3^1 \rightarrow 3^2 \rightarrow 3^4 \rightarrow 3^8$

同时，b 会不断右移，依次检查二进制的最低位是否为 1。

过程如下：

因此最终：

$ans = 3^1 \times 3^4 \times 3^8$

也就是：

$3^{13} = 1594323$

从二进制角度看，13 的二进制为 $1101_2$。从右往左依次检查每一位：

所以代码中的：

1
if ((b & 1) == 1) {
2
    ans *= x;
3
}

这一步是在判断当前二进制位是否为 1。如果是 1，就把当前的 x 乘入答案。

而：

1
x *= x;
2
b >>= 1;

分别表示：

• x *= x：让当前幂次翻倍，例如 $3^1 \rightarrow 3^2 \rightarrow 3^4 \rightarrow 3^8$
• b >>= 1：让指数右移一位，继续检查下一位二进制

注意： 在 Java、C++ 等语言中，32 位有符号整数 int 的范围是 $[-2^{31}, 2^{31}-1]$。当 $n = -2^{31}$ 时，直接取相反数 -n 会导致溢出。解决方法是先将 $n$ 存入 64 位整数（例如 Java 的 long 类型）再进行计算。

2.3 代码实现#

1
class Solution {
2
    public double myPow(double x, int n) {
3
        // 0 次幂直接返回 1
4
        if (n == 0) {
5
            return 1.0;
6
        }
7
        // 0 的正整数次幂直接返回 0
8
        if (x == 0.0) {
9
            return 0.0;
10
        }
11

12
        long b = n;
13
        double ans = 1.0;
14
        // 负指数先转成倒数，再把指数变为正数
15
        if (b < 0) {
16
            x = 1.0 / x;
17
            b = -b;
18
        }
19

20
        while (b > 0) {
21
            // 当前二进制位为 1，就把当前幂次乘进答案
22
            if ((b & 1) == 1) {
23
                ans *= x;
24
            }
25
            // 当前幂次翻倍
26
            x *= x;
27
            // 指数右移一位，继续处理下一位
28
            b >>= 1;
29
        }
30
        return ans;
31
    }
32
}

2.4 复杂度分析#

• 时间复杂度： $O(\log |n|)$，循环次数与 $n$ 的二进制位数成正比。
• 空间复杂度： $O(1)$，仅使用常数大小的额外空间。

3.1 算法原理#

快速幂实际上也是分治思想的一种典型应用。

• 当 $n < 0$ 时，我们可以利用倒数关系将其转换为正数次幂：$x^n = (1/x)^{-n}$。
• 当 $n \ge 0$ 时，我们可以将问题划分为规模减半的子问题。设 half = dfs(x, n / 2)，在 Java 中整数除法会自动向下取整，则有：

$x^n = \begin{cases} (x^{n / 2})^2, & n \text{ 为偶数} \\ (x^{n / 2})^2 \times x, & n \text{ 为奇数} \end{cases}$

根据上式，我们只需要先递归地计算 $x^{n / 2}$，然后根据 $n$ 的奇偶性，决定是否多乘一个 $x$ 即可。

3.2 递归过程示例：以 $3^{13}$ 为例#

上面的公式一开始可能不太直观，可以通过 $3^{13}$ 来理解递归快速幂的执行过程。

递归快速幂的核心是：每次先计算一半的幂次，然后根据当前指数的奇偶性决定如何合并结果。

对于 $3^{13}$：

由于 13 是奇数，所以：

$3^{13} = 3^6 \times 3^6 \times 3$

只要先算出 $3^6$，就可以得到 $3^{13}$。

继续拆分：

$3^6 = 3^3 \times 3^3$

因为 6 是偶数，所以平方即可，不需要额外乘 3。

继续拆分：

$3^3 = 3^1 \times 3^1 \times 3$

因为 3 是奇数，所以平方后还需要额外乘 3。

继续拆分：

$3^1 = 3^0 \times 3^0 \times 3$

当指数为 0 时，递归到达边界，直接返回 1。

递归调用过程如下：

返回过程如下：

可以看到，递归快速幂并不是从 $3^{13}$ 一步一步乘 13 次，而是不断把指数减半：

$13 \rightarrow 6 \rightarrow 3 \rightarrow 1 \rightarrow 0$

然后在返回时逐层合并结果。

因此，递归层数只和指数不断除以 2 的次数有关，时间复杂度为 $O(\log |n|)$。

• 递归边界： 当 $n = 0$ 时，返回 $1.0$。若 $x = 0.0$ 且 $n > 0$，直接返回 $0.0$。这里默认题目不会额外考察 $0$ 的负指数情况。

3.3 代码实现#

1
class Solution {
2
    public double myPow(double x, int n) {
3
        // 0 次幂直接返回 1
4
        if (n == 0) {
5
            return 1.0;
6
        }
7
        // 0 的正整数次幂直接返回 0
8
        if (x == 0.0) {
9
            return 0.0;
10
        }
11

12
        long b = n;
13
        // 负指数先在入口处处理，dfs 只负责非负指数
14
        if (n < 0) {
15
            x = 1.0 / x;
16
            b = -b;
17
        }
18

19
        return dfs(x, b);
20
    }
21

22
    private double dfs(double x, long n) {
23
        // 非负指数的递归边界
24
        if (n == 0) {
25
            return 1.0;
26
        }
27

28
        double half = dfs(x, n / 2);
29
        // 偶数次幂：直接平方
30
        if (n % 2 == 0) {
31
            return half * half;
32
        }
33
        // 奇数次幂：平方后再补一个 x
34
        return half * half * x;
35
    }
36
}

3.4 复杂度分析#

• 时间复杂度： $O(\log |n|)$，每次递归使幂次减半，因此递归树的深度为对数级别。
• 空间复杂度： $O(\log |n|)$，递归树的深度为 $O(\log |n|)$，需要占用对应大小的系统函数调用栈空间。