 的分治与二进制双视角解析)
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$设 $res1$则初始状态 $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$ 转化为解决以下两个问题计算 $x^1, x^2, x^4, \dots, x^{2^{m-1}}$ 的值循环赋值操作 $x x^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_21$、$b_41$将对应项乘入结果最终得到 $x^8 \cdot x^2 x^{10}$。这正是将幂拆解为若干个 $2$ 的整数次幂之和逐项相乘。算法流程完整算法流程如下当 $x 0.0$ 时直接返回 $0.0$以避免后续 $1$ 除以 $0$ 操作报错。分析数字 $0$ 的正数次幂恒为 $0$$0$ 的 $0$ 次幂和负数次幂没有意义因此直接返回 $0.0$ 即可。初始化 $res 1$。当 $n 0$ 时把问题转化至 $n \geq 0$ 的范围内即执行 $x 1/x$$n -n$。循环计算当 $n 0$ 时跳出当 $n 1 1$ 时将当前 $x$ 乘入 $res$即 $res * x$执行 $x x^2$即 $x * x$执行 $n$ 右移一位即 $n 1$。返回 $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 三种语言实现与仓库源码完全一致。Pythonclass 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 resJavaclass 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; } }Cclass 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.0ffloat 字面量返回使用0.0d/0.0double并且负数处理与循环均基于 long 型变量b进行以规避 int 最小值取反溢出。仓库源码对照与运行验证原题解文档对应的可运行代码散落在仓库多个目录中实现了同一套快速幂逻辑剑指 Offer 16 题与 LCR 134 同题Python 实现 ——sfo_16_powers_of_integers_s1.pyJava 实现 —— 含main驱动与测试用例C 实现 —— 含main驱动与测试用例精选 88 题 LeetCode 50 题Python 实现 ——lc_50_powx_n.pyJava 实现 ——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$迭代n二进制n 1resx初始10 (1010)—12110 (1010)01425 (0101)141632 (0010)0425641 (0001)1102465536结束0—1024—可见最终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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode-Book 快速幂精讲：LCR 134. Pow(x, n) 的分治与二进制双视角解析
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$设 $res1$则初始状态 $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$ 转化为解决以下两个问题计算 $x^1, x^2, x^4, \dots, x^{2^{m-1}}$ 的值循环赋值操作 $x x^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_21$、$b_41$将对应项乘入结果最终得到 $x^8 \cdot x^2 x^{10}$。这正是将幂拆解为若干个 $2$ 的整数次幂之和逐项相乘。算法流程完整算法流程如下当 $x 0.0$ 时直接返回 $0.0$以避免后续 $1$ 除以 $0$ 操作报错。分析数字 $0$ 的正数次幂恒为 $0$$0$ 的 $0$ 次幂和负数次幂没有意义因此直接返回 $0.0$ 即可。初始化 $res 1$。当 $n 0$ 时把问题转化至 $n \geq 0$ 的范围内即执行 $x 1/x$$n -n$。循环计算当 $n 0$ 时跳出当 $n 1 1$ 时将当前 $x$ 乘入 $res$即 $res * x$执行 $x x^2$即 $x * x$执行 $n$ 右移一位即 $n 1$。返回 $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 三种语言实现与仓库源码完全一致。Pythonclass 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 resJavaclass 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; } }Cclass 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.0ffloat 字面量返回使用0.0d/0.0double并且负数处理与循环均基于 long 型变量b进行以规避 int 最小值取反溢出。仓库源码对照与运行验证原题解文档对应的可运行代码散落在仓库多个目录中实现了同一套快速幂逻辑剑指 Offer 16 题与 LCR 134 同题Python 实现 ——sfo_16_powers_of_integers_s1.pyJava 实现 —— 含main驱动与测试用例C 实现 —— 含main驱动与测试用例精选 88 题 LeetCode 50 题Python 实现 ——lc_50_powx_n.pyJava 实现 ——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$迭代n二进制n 1resx初始10 (1010)—12110 (1010)01425 (0101)141632 (0010)0425641 (0001)1102465536结束0—1024—可见最终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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
