LeetCode 50. Pow(x, n)
目录
题目描述
题意分析
题目给一个浮点底数
x和一个整数指数n，要求返回x的n次幂。返回的是一个具体的浮点数值，不是取模结果，也不要求高精度，误差在题目允许范围内即可。第一个必须读出来的信号是：
n可以为负。负指数意味着结果是倒数，x^(-3) = 1 / x^3，所以正负两种情况得先在入口处统一掉，后面的主循环才可能只写一套逻辑。第二个信号藏在数据范围里：
n的取值是 32 位有符号整数的完整区间，下界是-2^31。这个下界很关键，因为 32 位整数里没有+2^31这个数，对下界取相反数会原地溢出回它自己。也就是说「负指数就取反变正」这句话在边界上是假的，必须换更宽的类型来承接。剩下的边界都比较朴素：
n = 0时无论x是多少都返回1；x可以是负数，此时结果符号由指数奇偶决定，但这一点不需要单独判断，乘法自己会算对。真正需要动脑的只有两处，一是怎么把幂算快，二是怎么不在指数取反上翻车。
解法：迭代快速幂
核心思路
问题关键：逐次相乘需要 $O(\lvert n\rvert)$ 次操作，指数接近 20 亿时不可行。幂可以复用已经算出的结果：$x^{2k}=(x^k)^2$，每次把指数减半，复杂度就能降为对数级。
为什么选快速幂：把正指数写成二进制，例如 $13=(1101)_2=8+4+1$，于是 $x^{13}=x^8\cdot x^4\cdot x$。从低位到高位扫描指数；当前位为
1时把当前底数乘入答案，每处理一位就让底数平方、指数右移。这比递归版少递归栈，也比线性乘法更适合大指数。不变量：设尚未处理的指数为
power、当前底数为base，循环中始终有ans * base^power = x^|n|（负指数归一化后的目标）。若最低位为1，先把一个base乘入ans；随后base平方、power减半，等式仍成立。正确性：每轮准确处理
power的一个二进制位。当power = 0时，未处理部分为base^0 = 1，由不变量可知ans就是目标幂。负指数先利用 $x^{-k}=(1/x)^k$ 转为正指数，因此同一证明仍然适用。类型边界：
n可能是Integer.MIN_VALUE，在 32 位整数中直接取反仍会溢出。必须先提升为 64 位整数，再处理负号。
解题步骤
- 用 64 位变量
power保存n；若为负数，将x变为1 / x，再令power = -power。- 初始化
ans = 1，它表示已经确认的二进制位贡献。- 当
power > 0时，若最低位为1，执行ans *= x。- 执行
x *= x，让底数从 $x^{2^k}$ 变成 $x^{2^{k+1}}$；再将power右移一位。- 指数归零后返回
ans。口述样例：
2^10中10=(1010)_2。扫描四位时只在代表2和8的位上乘入底数，得到 $2^2\cdot2^8=1024$。
代码实现
class Solution {
public double myPow(double x, int n) {
long power = n;
if (power < 0) {
x = 1.0 / x;
power = -power;
}
double ans = 1.0;
while (power > 0) {
if ((power & 1) == 1) {
ans *= x;
}
// 每右移一位，底数平方对应下一位二进制贡献。
x *= x;
power >>= 1;
}
return ans;
}
}
func myPow(x float64, n int) float64 {
// 先提升到 int64，再对最小的 32 位指数取反才不会溢出。
power := int64(n)
if power < 0 {
x = 1.0 / x
power = -power
}
ans := 1.0
for power > 0 {
if power&1 == 1 {
ans *= x
}
// 指数二进制每处理一位，底数自乘一次。
x *= x
power >>= 1
}
return ans
}
复杂度分析
- 时间复杂度：$O(\log \lvert n\rvert)$。每轮右移一位，循环次数等于指数的二进制位数。
- 空间复杂度：$O(1)$。迭代过程只使用常数个变量。
关键点总结
- 快速幂的本质是按二进制拆指数，并复用平方结果。
ans * base^power是推导循环顺序的核心不变量；当前位的贡献必须在底数平方前结算。- 负指数在入口统一成倒数的正指数，主循环无需额外分支。
- 对有符号整数取反时，要主动检查最小值溢出；Java 用
long，Go 明确转为int64。- 面试追问取模快速幂时，只需将每次乘法和平方后取模，整体框架不变。
易错点总结
long power = -n仍会先在int中取反；应先写long power = n，再对power取反。反例：n = -2147483648。- 负指数只改指数或只改底数都会出错；
x = 2, n = -2应得到0.25。- 若先执行
x *= x再结算当前位，x = 2, n = 1会错误得到4。- 位运算前必须把指数转成非负数，否则负数算术右移可能一直停在
-1。- 递归快速幂若把同一个半幂计算两次，会退化为线性复杂度；半幂必须只算一次并复用。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 剑指 Offer 16. 数值的整数次方 | 中等 | 同一模板的镜像题，重点仍是负指数与最小值取反溢出 |
| 372. 超级次方 | 中等 | 指数以数组形式给出，需按十进制逐位递推并全程取模 |
| 29. 两数相除 | 中等 | 把折半思想搬到除法上，用倍增减法且同样卡最小值溢出 |
| 69. x 的平方根 | 简单 | 幂的逆运算，改用二分或牛顿迭代逼近而非位拆分 |
| 509. 斐波那契数 | 简单 | 递推的进阶解法是矩阵快速幂，把本题模板换成矩阵乘法 |