 快速幂全解：二分指数幂的递归与迭代实现（附多语言源码）)
LeetCode 50 Pow(x, n) 快速幂全解二分指数幂的递归与迭代实现附多语言源码【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文围绕 LeetCode 第 50 题「Pow(x, n)」实现pow(x, n)浮点幂运算展开系统讲解从 O(n) 暴力乘法到 O(log n) 二分指数幂快速幂的三级递进方案并深入剖析负指数、Integer.MIN_VALUE溢出、位运算溢出等经典陷阱。读完本文你将掌握快速幂的数学本质、递归与迭代两种实现形态、复杂度推导以及如何对照本仓库 python/0050-powx-n.py、java/0050-powx-n.java、cpp/0050-powx-n.cpp 等多语言题解进行验证与扩展。问题概览与前置知识题目要求计算 (x^n)其中x是浮点数float/double/f64等n是 32 位有符号整数可正、可零、可负取值范围覆盖-2^31到2^31 - 1。题目虽小却是考察分治思想、二进制运算与边界处理的经典载体。按本仓库 hints/pow-x-n.md 与 articles/pow-x-n.md 的总结动手前需要具备四块前置知识前置知识作用递归与分治Divide and Conquer反复把问题对半拆分以降低复杂度二分指数幂Binary Exponentiation核心恒等式偶数时 (x^n (x^2)^{n/2})位运算基础用power 1判断奇偶、power 1实现除 2边界处理负指数取倒数、n取绝对值时的整数溢出推荐复杂度目标Hint 0提示文档 开篇给出的目标很明确你应该追求O(log n) 时间、O(log n) 空间或更优的解其中n是给定的整数。也就是说暴力 O(n) 只是思路铺垫最终解必须达到对数级别。仓库中 cpp/0050-powx-n.cpp 的注释也印证了这一点分治写法Time: O(log n)且可从递归的 O(log n) 空间进一步优化为迭代的 O(1) 空间。逐步推导从暴力到二分Hint 14 拆解提示文档 用 4 条提示把解题路径串起来这里逐条展开Hint 1 —— 先想暴力再想更优。最直观的做法是线性循环n次、每次乘一个x得到 (x^n)。n为负时返回1 / (x^n)否则返回(x^n)。但线性乘法在大n下必然超时所以应转向递归思路。Hint 2 —— 用分治减少乘法次数。计算 (2^6) 时不必连乘 6 次先算 (2^3)再对结果平方即可。同理递归下去直到某个不可再分解的项——这就是递归的基准情形base case。Hint 3 —— 明确边界与递归式。在 ((x^n)) 中x 0时返回0n 0时返回1任何数的 0 次幂为 1否则递归计算 ((x^{n/2})) 并平方若n为奇数再补乘一个x。Hint 4 —— 负指数统一转正处理。递归入口使用|n|n的绝对值。得到结果res后n 0直接返回resn 0返回1 / res。方法一暴力乘法O(n) 时间思路与算法暴力法直接贴合幂运算的数学定义边界处理x 0返回0n 0返回1初始化res 1循环abs(n)次每次res * xn 0返回res否则返回1 / res。该方案正确性直观是很好的起点但对大指数例如n 2^31 - 1会超时。代码示例Pythonclass Solution: def myPow(self, x: float, n: int) - float: if x 0: return 0 if n 0: return 1 res 1 for i in range(abs(n)): res * x return res if n 0 else 1 / res仓库中 javascript/0050-powx-n.js 的第一个实现Brute Force - Multiply就是同款思路n 0时先取x 1 / x; n -n再线性累乘注释标注Time O(N) | Space O(1)。复杂度时间复杂度O(n)乘法次数随指数线性增长空间复杂度O(1)方法二递归二分指数幂O(log n) 时间 / O(log n) 空间思路与算法利用分治恒等式把规模对半砍n为偶数(x^n (x^2)^{n/2})n为奇数(x^n x \times (x^2)^{(n-1)/2})每一步指数减半、底数平方乘法次数从 O(n) 降到 O(log n)。负指数通过「先算 (x^{|n|})再取倒数」处理。算法步骤定义递归辅助函数helper(x, n)x 0返回0n 0返回1递归计算res helper(x * x, n // 2)n为奇数返回x * res偶数返回res入口调用helper(x, abs(n))得到幅值n为负返回1 / result否则返回result。代码示例Python / Cclass Solution: def myPow(self, x: float, n: int) - float: def helper(x, n): if x 0: return 0 if n 0: return 1 res helper(x * x, n // 2) return x * res if n % 2 else res res helper(x, abs(n)) return res if n 0 else 1 / resclass Solution { public: double myPow(double x, int n) { if (x 0) return 0; if (n 0) return 1; double res helper(x, abs(static_castlong(n))); return (n 0) ? res : 1 / res; } private: double helper(double x, long n) { if (n 0) return 1; double half helper(x, n / 2); return (n % 2 0) ? half * half : x * half * half; } };注意 C/Java 版本把n转成long再取绝对值这正是为规避Integer.MIN_VALUE溢出见后文陷阱章节。仓库源码佐证本仓库 python/0050-powx-n.py 与上述 Python 完全一致rust/0050-powx-n.rs 用match显式处理(0.0, _) 0.0、(_, 0) 1.0两个基准分支再对n / 2递归并区分奇偶补乘x是同一算法的函数式表达。复杂度时间复杂度O(log n)空间复杂度O(log n)递归调用栈深度方法三迭代二分指数幂O(log n) 时间 / O(1) 空间思路与算法递归版本的空间来自调用栈迭代版本把「平方底数、减半指数」的循环显式写出用常数空间达到同样 O(log n) 的时间。关键观察任意整数n都能写成二进制当前power为奇数时结果要多乘一个当前底数x循环内反复执行x x * x底数平方、power power 1指数右移一位即整除 2。负指数仍走 (x^n 1 / x^{|n|})用abs(n)计算最后按符号决定是否取倒数。算法步骤边界x 0返回0n 0返回1初始化res 1、power abs(n)当power 0若power为奇数res * x底数平方x x * x指数减半power 1n 0返回1 / res否则返回res。代码示例Python / Javaclass Solution: def myPow(self, x: float, n: int) - float: if x 0: return 0 if n 0: return 1 res 1 power abs(n) while power: if power 1: res * x x * x power 1 return res if n 0 else 1 / respublic class Solution { public double myPow(double x, int n) { if (x 0) return 0; if (n 0) return 1; double res 1; long power Math.abs((long)n); while (power 0) { if ((power 1) 1) { res * x; } x * x; power 1; } return n 0 ? res : 1 / res; } }仓库源码佐证cpp/0050-powx-n.cpp 的最终实现正是迭代版——long exponent abs(n)后for (long i exponent; i 0; i / 2)循环内「奇数时result * curr随后curr * curr」最后按n 0取倒数javascript/0050-powx-n.js 的Fast Power - Iterative实现与之等价。复杂度时间复杂度O(log n)空间复杂度O(1)比递归版更优常见陷阱与工程细节articles/pow-x-n.md 专门总结了三类高频踩坑点这里逐一展开1. 取负值时的整数溢出Integer.MIN_VALUE当n Integer.MIN_VALUE即-2147483648时abs(n)或-n的正值2147483648超过了Integer.MAX_VALUE2147483647直接溢出、结果未定义。因此必须先转成long再取绝对值——这正是上文中 Java、C 写法里Math.abs((long)n)/abs(static_castlong(n))的用意。仓库 java/0050-powx-n.java 给出了另一种规避思路对负数指数先判断奇偶偶数时先n n / 2; n -n; x (1 / x) * (1 / x)把取反操作拆到安全范围内注释明确写道if I do -N and NInteger.MIN_VALUE itll become a value which is greater than the max value of Integer.MAX_VALUE。2. 忘记处理负指数负指数意味着结果是1 / x^|n|。若漏掉最后的取倒数步骤所有n 0的用例都会答错。正确流程是统一用绝对值算幂再根据符号决定是否取倒数。3. 大指数下使用暴力法n达到2^31 - 1量级时O(n) 线性乘法必然超时TLE。二分指数幂通过「底数平方 指数减半」把操作数降到 O(log n)。4. JavaScript 位运算的 32 位陷阱在 JavaScript 中Math.abs(n)本身安全数字是双精度浮点但位运算power 1、power 1会先把power截断为有符号 32 位整数2147483648会变成-2147483648导致循环立即终止、结果错误。因此 JS 迭代版应改用power % 2判断奇偶、Math.floor(power / 2)代替右移见 javascript/0050-powx-n.js 中Fast Power - Iterative的写法。三方案复杂度对照方案核心思路时间复杂度空间复杂度适用场景暴力乘法线性累乘O(n)O(1)仅作思路铺垫小指数可跑递归二分指数幂指数减半 底数平方O(log n)O(log n)思路最直观的正式解迭代二分指数幂位运算扫描二进制位O(log n)O(1)面试/工程首选空间最优仓库多语言实现索引本仓库围绕该题提供了完整的 12 语言实现均可在仓库根目录下的对应语言目录中找到文件名统一为0050-powx-n.extPythonpython/0050-powx-n.pyJavajava/0050-powx-n.javaCcpp/0050-powx-n.cppJavaScriptjavascript/0050-powx-n.jsTypeScripttypescript/0050-powx-n.tsRustrust/0050-powx-n.rsKotlinkotlin/0050-powx-n.ktSwiftswift/0050-powx-n.swiftCc/0050-powx-n.cC#csharp/0050-powx-n.csRubyruby/0050-powx-n.rb建议学习路径先读懂 articles/pow-x-n.md 的三种解法推导再对照 hints/pow-x-n.md 的提示自测推导能力最后选取自己最熟悉的 12 种语言实现跑通并重点验证x 2, n -2 → 0.25、x 2, n 10 → 1024、x 2.1, n 3 → 9.261以及n Integer.MIN_VALUE等边界用例即可彻底吃透这道快速幂经典题。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode 50 Pow(x, n) 快速幂全解二分指数幂的递归与迭代实现附多语言源码【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文围绕 LeetCode 第 50 题「Pow(x, n)」实现pow(x, n)浮点幂运算展开系统讲解从 O(n) 暴力乘法到 O(log n) 二分指数幂快速幂的三级递进方案并深入剖析负指数、Integer.MIN_VALUE溢出、位运算溢出等经典陷阱。读完本文你将掌握快速幂的数学本质、递归与迭代两种实现形态、复杂度推导以及如何对照本仓库 python/0050-powx-n.py、java/0050-powx-n.java、cpp/0050-powx-n.cpp 等多语言题解进行验证与扩展。问题概览与前置知识题目要求计算 (x^n)其中x是浮点数float/double/f64等n是 32 位有符号整数可正、可零、可负取值范围覆盖-2^31到2^31 - 1。题目虽小却是考察分治思想、二进制运算与边界处理的经典载体。按本仓库 hints/pow-x-n.md 与 articles/pow-x-n.md 的总结动手前需要具备四块前置知识前置知识作用递归与分治Divide and Conquer反复把问题对半拆分以降低复杂度二分指数幂Binary Exponentiation核心恒等式偶数时 (x^n (x^2)^{n/2})位运算基础用power 1判断奇偶、power 1实现除 2边界处理负指数取倒数、n取绝对值时的整数溢出推荐复杂度目标Hint 0提示文档 开篇给出的目标很明确你应该追求O(log n) 时间、O(log n) 空间或更优的解其中n是给定的整数。也就是说暴力 O(n) 只是思路铺垫最终解必须达到对数级别。仓库中 cpp/0050-powx-n.cpp 的注释也印证了这一点分治写法Time: O(log n)且可从递归的 O(log n) 空间进一步优化为迭代的 O(1) 空间。逐步推导从暴力到二分Hint 14 拆解提示文档 用 4 条提示把解题路径串起来这里逐条展开Hint 1 —— 先想暴力再想更优。最直观的做法是线性循环n次、每次乘一个x得到 (x^n)。n为负时返回1 / (x^n)否则返回(x^n)。但线性乘法在大n下必然超时所以应转向递归思路。Hint 2 —— 用分治减少乘法次数。计算 (2^6) 时不必连乘 6 次先算 (2^3)再对结果平方即可。同理递归下去直到某个不可再分解的项——这就是递归的基准情形base case。Hint 3 —— 明确边界与递归式。在 ((x^n)) 中x 0时返回0n 0时返回1任何数的 0 次幂为 1否则递归计算 ((x^{n/2})) 并平方若n为奇数再补乘一个x。Hint 4 —— 负指数统一转正处理。递归入口使用|n|n的绝对值。得到结果res后n 0直接返回resn 0返回1 / res。方法一暴力乘法O(n) 时间思路与算法暴力法直接贴合幂运算的数学定义边界处理x 0返回0n 0返回1初始化res 1循环abs(n)次每次res * xn 0返回res否则返回1 / res。该方案正确性直观是很好的起点但对大指数例如n 2^31 - 1会超时。代码示例Pythonclass Solution: def myPow(self, x: float, n: int) - float: if x 0: return 0 if n 0: return 1 res 1 for i in range(abs(n)): res * x return res if n 0 else 1 / res仓库中 javascript/0050-powx-n.js 的第一个实现Brute Force - Multiply就是同款思路n 0时先取x 1 / x; n -n再线性累乘注释标注Time O(N) | Space O(1)。复杂度时间复杂度O(n)乘法次数随指数线性增长空间复杂度O(1)方法二递归二分指数幂O(log n) 时间 / O(log n) 空间思路与算法利用分治恒等式把规模对半砍n为偶数(x^n (x^2)^{n/2})n为奇数(x^n x \times (x^2)^{(n-1)/2})每一步指数减半、底数平方乘法次数从 O(n) 降到 O(log n)。负指数通过「先算 (x^{|n|})再取倒数」处理。算法步骤定义递归辅助函数helper(x, n)x 0返回0n 0返回1递归计算res helper(x * x, n // 2)n为奇数返回x * res偶数返回res入口调用helper(x, abs(n))得到幅值n为负返回1 / result否则返回result。代码示例Python / Cclass Solution: def myPow(self, x: float, n: int) - float: def helper(x, n): if x 0: return 0 if n 0: return 1 res helper(x * x, n // 2) return x * res if n % 2 else res res helper(x, abs(n)) return res if n 0 else 1 / resclass Solution { public: double myPow(double x, int n) { if (x 0) return 0; if (n 0) return 1; double res helper(x, abs(static_castlong(n))); return (n 0) ? res : 1 / res; } private: double helper(double x, long n) { if (n 0) return 1; double half helper(x, n / 2); return (n % 2 0) ? half * half : x * half * half; } };注意 C/Java 版本把n转成long再取绝对值这正是为规避Integer.MIN_VALUE溢出见后文陷阱章节。仓库源码佐证本仓库 python/0050-powx-n.py 与上述 Python 完全一致rust/0050-powx-n.rs 用match显式处理(0.0, _) 0.0、(_, 0) 1.0两个基准分支再对n / 2递归并区分奇偶补乘x是同一算法的函数式表达。复杂度时间复杂度O(log n)空间复杂度O(log n)递归调用栈深度方法三迭代二分指数幂O(log n) 时间 / O(1) 空间思路与算法递归版本的空间来自调用栈迭代版本把「平方底数、减半指数」的循环显式写出用常数空间达到同样 O(log n) 的时间。关键观察任意整数n都能写成二进制当前power为奇数时结果要多乘一个当前底数x循环内反复执行x x * x底数平方、power power 1指数右移一位即整除 2。负指数仍走 (x^n 1 / x^{|n|})用abs(n)计算最后按符号决定是否取倒数。算法步骤边界x 0返回0n 0返回1初始化res 1、power abs(n)当power 0若power为奇数res * x底数平方x x * x指数减半power 1n 0返回1 / res否则返回res。代码示例Python / Javaclass Solution: def myPow(self, x: float, n: int) - float: if x 0: return 0 if n 0: return 1 res 1 power abs(n) while power: if power 1: res * x x * x power 1 return res if n 0 else 1 / respublic class Solution { public double myPow(double x, int n) { if (x 0) return 0; if (n 0) return 1; double res 1; long power Math.abs((long)n); while (power 0) { if ((power 1) 1) { res * x; } x * x; power 1; } return n 0 ? res : 1 / res; } }仓库源码佐证cpp/0050-powx-n.cpp 的最终实现正是迭代版——long exponent abs(n)后for (long i exponent; i 0; i / 2)循环内「奇数时result * curr随后curr * curr」最后按n 0取倒数javascript/0050-powx-n.js 的Fast Power - Iterative实现与之等价。复杂度时间复杂度O(log n)空间复杂度O(1)比递归版更优常见陷阱与工程细节articles/pow-x-n.md 专门总结了三类高频踩坑点这里逐一展开1. 取负值时的整数溢出Integer.MIN_VALUE当n Integer.MIN_VALUE即-2147483648时abs(n)或-n的正值2147483648超过了Integer.MAX_VALUE2147483647直接溢出、结果未定义。因此必须先转成long再取绝对值——这正是上文中 Java、C 写法里Math.abs((long)n)/abs(static_castlong(n))的用意。仓库 java/0050-powx-n.java 给出了另一种规避思路对负数指数先判断奇偶偶数时先n n / 2; n -n; x (1 / x) * (1 / x)把取反操作拆到安全范围内注释明确写道if I do -N and NInteger.MIN_VALUE itll become a value which is greater than the max value of Integer.MAX_VALUE。2. 忘记处理负指数负指数意味着结果是1 / x^|n|。若漏掉最后的取倒数步骤所有n 0的用例都会答错。正确流程是统一用绝对值算幂再根据符号决定是否取倒数。3. 大指数下使用暴力法n达到2^31 - 1量级时O(n) 线性乘法必然超时TLE。二分指数幂通过「底数平方 指数减半」把操作数降到 O(log n)。4. JavaScript 位运算的 32 位陷阱在 JavaScript 中Math.abs(n)本身安全数字是双精度浮点但位运算power 1、power 1会先把power截断为有符号 32 位整数2147483648会变成-2147483648导致循环立即终止、结果错误。因此 JS 迭代版应改用power % 2判断奇偶、Math.floor(power / 2)代替右移见 javascript/0050-powx-n.js 中Fast Power - Iterative的写法。三方案复杂度对照方案核心思路时间复杂度空间复杂度适用场景暴力乘法线性累乘O(n)O(1)仅作思路铺垫小指数可跑递归二分指数幂指数减半 底数平方O(log n)O(log n)思路最直观的正式解迭代二分指数幂位运算扫描二进制位O(log n)O(1)面试/工程首选空间最优仓库多语言实现索引本仓库围绕该题提供了完整的 12 语言实现均可在仓库根目录下的对应语言目录中找到文件名统一为0050-powx-n.extPythonpython/0050-powx-n.pyJavajava/0050-powx-n.javaCcpp/0050-powx-n.cppJavaScriptjavascript/0050-powx-n.jsTypeScripttypescript/0050-powx-n.tsRustrust/0050-powx-n.rsKotlinkotlin/0050-powx-n.ktSwiftswift/0050-powx-n.swiftCc/0050-powx-n.cC#csharp/0050-powx-n.csRubyruby/0050-powx-n.rb建议学习路径先读懂 articles/pow-x-n.md 的三种解法推导再对照 hints/pow-x-n.md 的提示自测推导能力最后选取自己最熟悉的 12 种语言实现跑通并重点验证x 2, n -2 → 0.25、x 2, n 10 → 1024、x 2.1, n 3 → 9.261以及n Integer.MIN_VALUE等边界用例即可彻底吃透这道快速幂经典题。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
