LeetCode 50. Pow(x, n) 题解:快速幂算法的数学原理与八种语言实现
LeetCode 50. Pow(x, n) 题解:快速幂算法的数学原理与八种语言实现
本篇技术指南以 doocs/leetcode 仓库中 0050.Pow(x, n) 的题解文档为骨架,系统讲解如何实现 pow(x, n) 计算 x 的整数 n 次幂。文章将剖析朴素连乘为何超时、快速幂如何借助二进制拆解指数把复杂度从 O(|n|) 降到 O(log n),并完整给出仓库中 Python3、Java、C++、Go、TypeScript、Rust、JavaScript、C# 共八种语言的实现及其边界处理细节。读完本文,你将掌握快速幂这一高频算法模板,并能从容应对负指数与 int 溢出等易错点。
题目描述与约束
实现 pow(x, n),即计算 x 的整数 n 次幂函数 x^n。
示例 1:
输入:x = 2.00000, n = 10
输出:1024.00000
示例 2:
输入:x = 2.10000, n = 3
输出:9.26100
示例 3:
输入:x = 2.00000, n = -2
输出:0.25000
解释:2^-2 = 1/2^2 = 1/4 = 0.25
提示(约束条件):
-100.0 < x < 100.0-2^31 <= n <= 2^31 - 1n是一个整数- 要么
x不为零,要么n > 0 -10^4 <= x^n <= 10^4
这些约束决定了实现必须关注的三个要点:n 可以为负(需要取倒数)、n 的绝对值最大可达 2^31(线性乘法不可行)、n 恰好覆盖 32 位有符号整数的下界(涉及取反溢出问题,详见下文"边界处理"一节)。
朴素连乘为什么不可行
若把 x 连乘 |n| 次,由于 |n| 最大约 2^31,线性乘法在时间上很容易超时;同时还要单独处理 n < 0 时取倒数的情况。
一次只乘一个 x 没有利用幂的倍增结构。注意到两个关键恒等式:
指数每次都可以折半,这正是快速幂的数学根基。
快速幂算法原理:按二进制拆解指数
快速幂算法的核心思想是将幂指数 n 拆分为若干个二进制位上的 1 的和,然后把 x 的 n 次幂转化为 x 的若干个幂的乘积。
以 x = 2, n = 10 为例:10 的二进制表示为 1010,即 10 = 8 + 2 = 2^3 + 2^1,因此:
迭代实现时维护两个量:ans(累乘结果,初始为 1)与 a(当前底数,初始为 x)。每一轮循环中:
- 用
n & 1检查n的最低位是否为1,若是则把当前底数乘进ans; - 执行
a *= a,让底数自乘(对应指数翻倍); - 执行
n >>= 1,把指数右移一位,继续考察下一位。
以 n = 10 手动走一遍流程:
| 轮次 | n(二进制) | n & 1 | 操作 | ans | a |
|---|---|---|---|---|---|
| 1 | 10 (1010) | 0 | 不乘入 | 1 | 4 |
| 2 | 5 (0101) | 1 | ans *= a | 4 | 16 |
| 3 | 2 (0010) | 0 | 不乘入 | 4 | 256 |
| 4 | 1 (0001) | 1 | ans *= a | 1024 | 65536 |
| 5 | 0 | — | 循环结束 | 1024 | — |
最终得到 2^10 = 1024,仅用 4 轮循环就完成了原本需要 10 次乘法的计算。整体来看,循环轮数等于 n 的二进制位数,即 O(log n)。
边界处理:负指数与 int 取反溢出
负指数:先按正指数计算出 x^|n|,再取倒数得到 x^n = 1 / x^|n|。示例 3 中 2^-2 = 1/2^2 = 0.25 即为此逻辑。
取反溢出:这是本题最经典的陷阱。当 n = -2^31(即 Integer.MIN_VALUE)时,直接对 int 执行 -n 会发生溢出——-(-2^31) 仍等于 -2^31,取倒数后结果完全错误。仓库中各语言实现的做法是先将指数提升到更宽的整数类型再做取反:
- Java 与 C# 将
int强转为long后传入qpow:1 / qpow(x, -(long) n); - C++ 的
qpow直接接收long long n; - Rust 先将
n as i64,再做-n; - Go 中
n的类型为int,在 64 位平台上是 64 位宽,-n不会溢出; - Python 的整数为任意精度,天然无此问题;
- JavaScript / TypeScript 则利用无符号右移
n >>>= 1,即使n = 2^31也能正确按 32 位无符号语义移位(注意 JS 位运算本身基于 32 位有符号整数,>>>无符号右移恰好规避了符号位问题)。
八种语言实现详解
以下实现全部来自仓库 0050.Pow(x, n) 题解文档,与各语言独立源码文件一一对应。
Python3
class Solution:
def myPow(self, x: float, n: int) -> float:
def qpow(a: float, n: int) -> float:
ans = 1
while n:
if n & 1:
ans *= a
a *= a
n >>= 1
return ans
return qpow(x, n) if n >= 0 else 1 / qpow(x, -n)
Python 的整数没有溢出问题,-n 可安全使用;while n 依赖非零判断直接作为循环条件。源码见 Solution.py。
Java
class Solution {
public double myPow(double x, int n) {
return n >= 0 ? qpow(x, n) : 1 / qpow(x, -(long) n);
}
private double qpow(double a, long n) {
double ans = 1;
for (; n > 0; n >>= 1) {
if ((n & 1) == 1) {
ans = ans * a;
}
a = a * a;
}
return ans;
}
}
关键在于 qpow 的指数参数声明为 long,且调用处显式 -(long) n,从而规避 n = Integer.MIN_VALUE 时 -n 的 int 溢出。源码见 Solution.java。
C++
class Solution {
public:
double myPow(double x, int n) {
auto qpow = [](double a, long long n) {
double ans = 1;
for (; n; n >>= 1) {
if (n & 1) {
ans *= a;
}
a *= a;
}
return ans;
};
return n >= 0 ? qpow(x, n) : 1 / qpow(x, -(long long) n);
}
};
C++ 版本使用 lambda 表达式封装 qpow,指数参数取 long long 以避免取反溢出。源码见 Solution.cpp。
Go
func myPow(x float64, n int) float64 {
qpow := func(a float64, n int) float64 {
ans := 1.0
for ; n > 0; n >>= 1 {
if n&1 == 1 {
ans *= a
}
a *= a
}
return ans
}
if n >= 0 {
return qpow(x, n)
}
return 1 / qpow(x, -n)
}
Go 的 int 在 64 位平台为 64 位宽,n 的 32 位取值范围下 -n 不会溢出。源码见 Solution.go。
TypeScript
function myPow(x: number, n: number): number {
const qpow = (a: number, n: number): number => {
let ans = 1;
for (; n; n >>>= 1) {
if (n & 1) {
ans *= a;
}
a *= a;
}
return ans;
};
return n >= 0 ? qpow(x, n) : 1 / qpow(x, -n);
}
注意循环步进使用无符号右移 n >>>= 1:JS 的位运算基于 32 位有符号整数,>>> 以无符号语义移位,即使 n 取到 2^31 也能正确折半。源码见 Solution.ts。
Rust
impl Solution {
#[allow(dead_code)]
pub fn my_pow(x: f64, n: i32) -> f64 {
let mut x = x;
let n = n as i64;
if n >= 0 {
Self::quick_pow(&mut x, n)
} else {
1.0 / Self::quick_pow(&mut x, -n)
}
}
#[allow(dead_code)]
fn quick_pow(x: &mut f64, mut n: i64) -> f64 {
// `n` should greater or equal to zero
let mut ret = 1.0;
while n != 0 {
if (n & 0x1) == 1 {
ret *= *x;
}
*x *= *x;
n >>= 1;
}
ret
}
}
Rust 版本先将 n as i64 拓宽类型再取反,quick_pow 通过可变引用原地更新底数,并以注释明确约定入参 n 必须非负。源码见 Solution.rs。
JavaScript
/**
* @param {number} x
* @param {number} n
* @return {number}
*/
var myPow = function (x, n) {
const qpow = (a, n) => {
let ans = 1;
for (; n; n >>>= 1) {
if (n & 1) {
ans *= a;
}
a *= a;
}
return ans;
};
return n >= 0 ? qpow(x, n) : 1 / qpow(x, -n);
};
与 TypeScript 版本逻辑一致,同样借助 n >>>= 1 无符号右移保证大指数下移位正确。源码见 Solution.js。
C#
public class Solution {
public double MyPow(double x, int n) {
return n >= 0 ? qpow(x, n) : 1.0 / qpow(x, -(long)n);
}
private double qpow(double a, long n) {
double ans = 1;
for (; n > 0; n >>= 1) {
if ((n & 1) == 1) {
ans *= a;
}
a *= a;
}
return ans;
}
}
与 Java 版本同构:qpow 接收 long 类型指数,-(long)n 避免 int 取反溢出。源码见 Solution.cs。
复杂度分析
快速幂每轮循环将指数右移一位,循环次数等于 n 的二进制位数,因此:
- 时间复杂度:
O(log n),其中n为幂指数。相比朴素连乘的O(|n|),当|n|接近2^31时两者差距巨大。 - 空间复杂度:
O(1),只使用了常数个变量,无递归栈开销。
仓库结构与延伸阅读
在 doocs/leetcode 仓库中,本题位于 solution/0000-0099 目录下,每个题目目录统一存放两种语言的题解文档与各编程语言的独立源码文件:
- 中文题解:README.md
- 英文题解:README_EN.md
- 八种语言的独立源码:
Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.rs、Solution.js、Solution.cs(均位于 0050.Pow(x, n) 目录下)
总结
求解 pow(x, n) 的核心是把指数 n 按二进制拆解,利用 x^{2k} = (x^k)^2 的倍增结构,通过"位检测 + 底数自乘 + 指数右移"三件事在 O(log n) 时间内完成计算。实现时务必注意两点:负指数需先算正幂再取倒数;当 n 触及 -2^31 时,在 Java、C#、C++、Rust 等语言中须先拓宽指数类型再取反,防止溢出。掌握这一模板后,矩阵快速幂、模意义下的快速幂(如 LCP 24. 数字游戏 之外的更多数论问题)也可触类旁通。