企业官网建设流程全解析

LeetCode-Book 快速幂精讲：LCR 134. Pow(x, n) 的分治与二进制双视角解析

【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C++ 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book

导读

本文围绕 LeetCode-Book 仓库中 LCR 134. Pow(x, n).md) 题解文档，系统讲解快速幂算法的两种推导视角（分治法与二进制展开），并给出 Python、Java、C++ 三种语言的完整实现与仓库源码对照。读完本文，你将掌握如何把求 $x^n$ 的时间复杂度从朴素循环的 $O(n)$ 降至 $O(\log n)$，同时理解负数次幂、零底数以及 Java/C++ 中int最小值取反溢出等关键边界问题的处理手法。

该题在仓库中对应《剑指 Offer》第 16 题（剑指 Offer 16. 数值的整数次方）以及精选 88 题中的 LeetCode 50 题（50. Pow(x, n).md)），三套题解共用同一份快速幂核心实现。

问题定义与朴素解法

实现pow(x, n)，即计算 $x$ 的 $n$ 次幂，其中 $x$ 是浮点数，$n$ 是 32 位有符号整数（取值范围 $n \in [-2147483648, 2147483647]$）。

最直接的做法是循环将 $n$ 个 $x$ 乘起来，依次求 $x^1, x^2, \dots, x^{n-1}, x^n$，时间复杂度为 $O(n)$。当 $n$ 接近 21 亿（$2^{31}-1$）时，这种朴素乘法在时间上不可接受，因此需要快速幂法将时间复杂度降至 $O(\log n)$。快速幂可以从「分治法」和「二进制」两个角度来解析。

快速幂解析（分治法角度）

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

二分推导：由 $x^n = x^{n/2} \times x^{n/2} = (x^2)^{n/2}$，令 $n/2$ 为整数，则需要分为奇偶两种情况（设向下取整除法符号为 $//$）：

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

观察发现，当 $n$ 为奇数时，二分后会多出一项 $x$。

幂结果获取：

• 根据推导，可通过循环 $x = x^2$ 操作，每次把幂从 $n$ 降至 $n//2$，直至将幂降为 $0$；
• 设 $res=1$，则初始状态 $x^n = x^n \times res$。在循环二分时，每当 $n$ 为奇数时，将多出的一项 $x$ 乘入 $res$，则最终可化至 $x^n = x^0 \times res = res$，返回 $res$ 即可。

转化为位运算：

• 向下整除 $n // 2$等价于右移一位 $n >> 1$；
• 取余数 $n \mod 2$等价于判断二进制最右位 $n & 1$。

位运算等价变换是整个实现高性能的关键：右移与按位与都是常数时间的整数运算，避免了每次迭代中的除法与取模开销。

快速幂解析（二进制角度）

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

对于任何十进制正整数 $n$，设其二进制为 $b_m\dots b_3b_2b_1$（$b_i$ 为二进制某位值，$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}b_1}, x^{2^{1}b_2}, \dots, x^{2^{m-1}b_m}$ 的值，并将所有 $x^{2^{i-1}b_i}$ 累计相乘即可，其中：

$$ x^{2^{i-1}b_i}= \begin{cases} 1 & , b_i = 0 \ x^{2^{i-1}} & , b_i = 1 \ \end{cases} $$

直观示例：计算 $x^{10}$。$10$ 的二进制为 $1010$，即 $10 = 8 + 2$，于是 $x^{10} = x^8 \times x^2$。循环中依次对 $x$ 执行平方得到 $x^2, x^4, x^8$，并只在二进制位为 1 的位置（$b_2=1$、$b_4=1$）将对应项乘入结果，最终得到 $x^8 \cdot x^2 = x^{10}$。这正是将幂拆解为若干个 $2$ 的整数次幂之和，逐项相乘。

算法流程

完整算法流程如下：

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

关键边界处理说明：

• 零底数：提前拦截 $x = 0.0$，避免负数次幂时执行 $1/x$ 触发除零异常；
• 负指数：通过 $x = 1/x$ 与 $n = -n$ 将问题规约到非负指数，再利用快速幂计算；
• int 溢出（Java/C++ 特有）：int32 变量区间 $n \in [-2147483648, 2147483647]$，当 $n = -2147483648$ 时执行 $n = -n$ 会因越界而赋值出错。解决方法是先将 $n$ 存入 long 变量 $b$，后面用 $b$ 操作即可。这也是 Java/C++ 版本中long b = n;这行代码存在的根本原因。Python 的整数无位数限制，天然规避此问题。

三种语言完整代码

原文档提供了 Python、Java、C++ 三种语言实现，与仓库源码完全一致。

Python

class Solution: def myPow(self, x: float, n: int) -> float: if x == 0.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

Java

class Solution { public double myPow(double x, int n) { if(x == 0.0f) return 0.0d; long b = n; double res = 1.0; if(b < 0) { x = 1 / x; b = -b; } while(b > 0) { if((b & 1) == 1) res *= x; x *= x; b >>= 1; } return res; } }

C++

class Solution { public: double myPow(double x, int n) { if(x == 0.0f) return 0.0; long b = n; double res = 1.0; if(b < 0) { x = 1 / x; b = -b; } while(b > 0) { if((b & 1) == 1) res *= x; x *= x; b >>= 1; } return res; } };

注意 Java 与 C++ 版本中，判零使用x == 0.0f（float 字面量），返回使用0.0d/0.0（double），并且负数处理与循环均基于 long 型变量b进行，以规避 int 最小值取反溢出。

仓库源码对照与运行验证

原题解文档对应的可运行代码散落在仓库多个目录中，实现了同一套快速幂逻辑：

• 剑指 Offer 16 题（与 LCR 134 同题）：
  • Python 实现 ——sfo_16_powers_of_integers_s1.py
  • Java 实现 —— 含main驱动与测试用例
  • C++ 实现 —— 含main驱动与测试用例
• 精选 88 题 LeetCode 50 题：
  • Python 实现 ——lc_50_powx_n.py
  • Java 实现 ——lc_50_powx_n.java

仓库中的测试用例采用x = 2.0, n = 10，预期输出1024.0。以 Python 版本为例，其 Driver Code 流程为：

x = 2.0 n = 10 slt = Solution() res = slt.myPow(x, n) print(res) # 期望输出 1024.0

手动模拟该用例的循环过程（$n = 10$，二进制 $1010$）：

可见最终res = 1024 = 2^10，与测试用例预期一致，直接印证了「仅在二进制位为 1 时累乘当前 $x$」的算法正确性。

再验证负数场景：$x = 2.0, n = -3$。第一步将问题化为 $x = 0.5, n = 3$，随后循环计算 $0.5^3 = 0.125$，即 $2^{-3} = 0.125$，符合数学预期。而 Java/C++ 中若 $n = -2147483648$，-n在 int 域内仍为 $-2147483648$（溢出），只有先存入long b才能正确得到 $2147483648$，这正是两版代码先long b = n的原因。

复杂度分析

• 时间复杂度 $O(\log n)$：二分的时间复杂度为对数级别。无论 $n$ 正负，循环迭代次数等于 $n$ 二进制位数，约为 $\log_2 |n|$；
• 空间复杂度 $O(1)$：$res$、$b$ 等变量占用常数大小额外空间，迭代式写法避免了递归调用栈的额外开销。

扩展：快速幂思想的通用性

快速幂的本质是「通过倍增将指数二进制展开，把 $O(n)$ 次乘法压缩到 $O(\log n)$ 次」，这一思想不止适用于浮点幂运算：

• 整数取模幂：计算 $a^b \bmod m$ 时，将乘法改为 $x = (x \times x) \bmod m$ 即可，是 RSA 等密码学算法的核心原语；
• 矩阵快速幂：将标量乘法替换为矩阵乘法，可在 $O(\log n)$ 内计算 $M^n$，用于求解线性递推（如斐波那契数列）——仓库中 LCR 126. 斐波那契数 与其高频变体可相互印证；
• 倍增思想：与二分查找、倍增法求 LCA 等算法同源，掌握后可以举一反三。

总结

本文完整复现了原题解文档的推导脉络：先用分治法建立「奇偶二分 + 结果累积」的直觉，再用二进制展开给出严格的数学证明，最后落为「$n & 1$ 判断 + $x *= x$ 平方 + $n >>= 1$ 右移」三行核心循环。结合仓库中三种语言的实测代码与测试用例，你可以直接运行验证，并在此基础上深入理解快速幂在密码学、矩阵递推等场景下的广泛应用。

【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C++ 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book