LeetCode 50. Pow(x, n)
题目描述
题意分析
计算浮点数
x的整数次幂xⁿ，指数n可能为正、为负或为零。正指数表示重复相乘，负指数表示对应正整数幂的倒数，零指数的结果为1。指数使用 32 位有符号整数，绝对值可能很大，不能依靠逐次乘
x来完成运算；最小负指数的绝对值还超出了正int的上界，处理符号时需要注意类型范围。
解法：迭代快速幂
核心思路
[!blue]
连续乘
x会重复做大量相同工作。平方可以把已有幂次直接翻倍：得到x²后再平方就是x⁴，再平方就是x⁸。任意非负整数又都能写成若干个二的幂之和，所以只需把指数二进制中为1的位置对应的幂相乘。先把
n保存到 64 位的power。如果指数为负，同时令底数变为1 / x、指数变为正数，利用x⁻ᴺ = (1/x)ᴺ统一成非负指数问题。必须先扩大类型再取反，否则最小负整数会在取反时先溢出。循环中，
ans保存已经选中的二进制位贡献，当前x保存这一位对应的幂。若power的最低位为1，就把当前x乘入ans；无论最低位是什么，随后都令x平方、power右移一位，处理下一个更高位。也可以用不变量理解这一顺序：把归一化后的初始底数和指数固定记为
B、N，始终有数学关系ans × x^power = B^N。偶数指数通过平方底数、指数减半保持不变；奇数指数先拿出一个x乘入ans，剩余部分就成为偶数。最终power = 0，未处理部分变为1，因此ans就是目标值。
解题步骤
- 用 64 位变量保存指数；若为负，先将底数取倒数，再将这个 64 位指数取反。
- 初始化
ans = 1，作为乘法的单位值。- 当
power > 0时，检查最低位；为1就执行ans *= x。- 执行
x *= x和power >>= 1，让下一轮对应更高一位的幂。- 指数归零后返回
ans；初始指数为0时直接返回初始值1。
代码实现
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 + 1))$，每轮处理指数的一位二进制；零指数直接得到初始答案。
- 空间复杂度：$O(1)$。迭代过程只使用常数个变量。
关键点总结
[!green]
- 平方让可复用的幂次翻倍，二进制分解决定哪些幂需要乘进结果。
- 当前位必须在底数平方之前结算，否则拿到的是下一位对应的幂。
- 负指数通过倒数和取反统一处理，扩大整数类型则负责覆盖最小负指数。
易错点总结
[!yellow]
- 写
long power = -n仍会先在 32 位中取反；应先保存n，再对已经扩大的变量取反。- 负指数只改符号而不把底数取倒数，会算成正指数结果。
- 先平方底数再判断当前最低位，会让被选中的幂全部错位。
- 对负数直接反复算术右移，可能停在
-1无法结束；应先统一成非负指数。- 将答案初始化为
0，后续乘法永远得不到正确结果；乘法累计值应从1开始。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 372. 超级次方 | 中等 | 同样利用幂的分解减少乘法，原题指数以十进制数组给出且需要取模。 |
| 29. 两数相除 | 中等 | 同样按倍增块处理大次数，原题倍增除数，本题通过平方形成二次幂块。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！