LeetCode 剑指 Offer 16. 数值的整数次方
题目描述
题意分析
计算浮点底数
x的整数n次幂，不调用库的求幂函数。指数可以为正、零或负；零次幂按题目约定返回一，负指数表示对应正次幂的倒数。指数范围是 32 位有符号整数，逐次相乘在绝对值很大时次数过多。需要减少乘法次数，并注意最小负指数在 32 位类型内不能直接取相反数。
解法：迭代快速幂
核心思路
[!blue]
先处理负指数：把指数提升到
long或int64后，再安全地取反，同时将底数替换为倒数。这样目标统一成非负指数的求幂，最小 32 位负数的绝对值也能够被保存。将剩余指数写成二进制，每一位对应底数的一次二次幂权值。用
base保存当前这一位对应的幂，初始为底数；每次平方后，它依次代表二次、四次、八次等幂。只有指数当前最低位为一，才把这个权值乘入累计结果res。也可以从每轮的不变量理解：
res * base^exp始终等于归一化后的目标。若exp为偶数，用base的平方和一半指数替换，值不变；若为奇数，先从指数中取出一个base乘到res，剩余指数就是偶数，再做同样的平方与折半。因此每轮先判断最低位并按需累乘，再令
base *= base、exp >>= 1，同步转向下一位。指数归零时，剩余幂为一，res就是答案；指数一开始为零时也自然保持初值一。每次把剩余指数折半，所以乘法轮数只与指数的二进制位数有关，而不是与指数绝对值成正比。底数为负时，正负号也由实际参与的乘法自然决定。
解题步骤
- 将
n先转换为宽整数exp。- 若指数为负，取底数倒数，并将宽整数指数取反。
- 初始化
res = 1、base为归一化后的底数。- 指数非零时，最低位为一就乘入
base，随后平方底数并右移指数。- 指数耗尽后返回
res。
代码实现
class Solution {
public double myPow(double x, int n) {
// 先提升类型，最小整数的相反数才能被表示。
long exp = n;
if (exp < 0) {
x = 1.0 / x;
exp = -exp;
}
double res = 1.0;
double base = x;
while (exp > 0) {
if ((exp & 1) == 1) {
// 只乘入指数中置位对应的底数幂。
res *= base;
}
// 底数平方与指数右移同步进入下一二进制位。
base *= base;
exp >>= 1;
}
return res;
}
}
func myPow(x float64, n int) float64 {
// 先提升类型，题目最小整数的相反数才能被表示。
exp := int64(n)
if exp < 0 {
x = 1.0 / x
exp = -exp
}
res := 1.0
base := x
for exp > 0 {
if exp&1 == 1 {
// 只乘入指数中置位对应的底数幂。
res *= base
}
// 底数平方与指数右移同步进入下一二进制位。
base *= base
exp >>= 1
}
return res
}
复杂度分析
- 时间复杂度：$O(1+\log(\lvert n\rvert+1))$。
- 空间复杂度：$O(1)$。
关键点总结
[!green]
- 指数每折半一次，底数要平方一次，两步共同保持目标幂不变。
- 最低位只决定当前权值是否参与，不能每轮都乘入结果。
- 宽类型转换必须发生在负指数取反之前。
res保存已处理指数位的贡献，base与exp表示尚未处理部分。
易错点总结
[!yellow]
- 在原 32 位整数内先取反再转换，最小负指数的溢出已经发生。
- 每轮无条件乘入
base，会把指数为零的二进制位也计入。- 只把负指数变正却不取底数倒数，会求出错误的幂。
- 指数右移与底数平方必须同步，漏掉其中一步会破坏每位权值。
- 累计结果初值应为一，若设为零，所有后续乘法都会保持零。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 372. 超级次方 | 中等 | 同样利用幂的分解减少乘法，原题指数以十进制数组给出且需要取模。 |
| 29. 两数相除 | 中等 | 同样按倍增块处理大次数，原题倍增除数，本题通过平方形成二次幂块。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！