LeetCode 剑指 Offer 16. 数值的整数次方

约 8 分钟
文章信息 10 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 腾讯 京东 亚马逊 剑指 Offer 剑指 Offer（第 2 版）
标签
数学 递归
目录

题目描述

✅ 剑指 Offer 16. 数值的整数次方

image-20241107205028883

题意分析

给定浮点底数 x 和 32 位有符号整数指数 n，返回 x 的 n 次幂，不允许直接调用语言自带的幂函数。

指数是 int 全域，绝对值可以接近 21 亿，这条约束直接否决了「循环 n 次连乘」的写法——不是精度问题，而是时间上根本跑不完，必须把对 n 的依赖压到对数级。

指数可以为负，需要一次取倒数的转换；而 n 的下界是 -2147483648，它的相反数在 int 里表示不出来，这是本题最容易被面试官追问的坑。

边界还包括：n 为 0 时无论 x 是什么都返回 1；x 为 0 且 n 为负时数学上无定义，测试数据不会给出这种输入，代码里出现除零得到 Infinity 也不影响判题。

解法：迭代快速幂

核心思路

朴素做法是从 1 开始乘 n 次 x，需要 $O( n )$ 次乘法。瓶颈非常直白：n 的量级是 $2^{31}$，二十亿次浮点乘法既超时又会把误差累积得很难看。
观察点是幂运算的结合律：$x^{2k} = (x^2)^k$，$x^{2k+1} = x \cdot (x^2)^k$。也就是说，指数每减半一次，只要付出「把底数平方一次」的常数代价。指数从 n 减半到 0 只需要 $\log_2 n $ 步，乘法次数因此从二十亿降到三十出头。

把递归展开成迭代，本质就是按 n 的二进制位从低到高扫描：$n = \sum_i b_i 2^i$，于是 $x^n = \prod_{b_i = 1} x^{2^i}$。第 i 轮手上的 base 恰好是 $x^{2^i}$，该位为 1 就把它乘进答案。

由此得到循环维护的不变量：每轮循环开始时，res * base^exp 恒等于最终答案。初始 res = 1、base = x、exp = n 显然成立；每轮若最低位为 1 就把 base 乘入 res 并把该位从 exp 上抹去，然后 base 平方、exp 右移，等式两边的值不变。exp 归零时 base^0 = 1，res 就是答案。

负指数的处理放在进入循环之前：$x^{-m} = (1/x)^m$，把底数取倒数、指数取绝对值即可。为了让 -2147483648 也能安全取相反数，先把 n 提升到 64 位再取负。

解题步骤

  • 把 n 赋给一个 64 位变量 exp。这一步不是为了大数，而是专门防 Integer.MIN_VALUE：在 int 里 -(-2147483648) 会溢出回自身，导致后面的 exp > 0 判断直接为假，函数错误地返回 1。
  • 若 exp 为负，令 x = 1 / x 并 exp = -exp，把问题统一成正指数。之所以能这样转换，是因为倒数与幂运算可交换，先取倒数再乘幂和先乘幂再取倒数结果一致，而前者能让主循环只处理一种情况。
  • 初始化 res = 1.0、base = x，此时不变量 res * base^exp 已经等于答案。
  • 循环直到 exp 为 0：若 exp & 1 为 1，说明当前二进制位对答案有贡献，把 base 乘进 res。这一步对应「从 exp 中扣掉这一位」。
  • 每轮固定执行 base *= base 与 exp >>= 1，让 base 始终等于 $x^{2^i}$ 与 exp 的当前最低位对齐。两者必须成对出现，少做一个不变量就断了。
  • exp 归零后返回 res。n 为 0 时循环一次都不进，直接返回 1.0，天然覆盖了零次幂。

以 x = 2.0、n = 10 走一遍：exp = 10 为正，不做倒数转换，res = 1.0，base = 2.0。10 的二进制是 1010。

第一轮 exp = 10，最低位为 0，res 保持 1.0；base 变成 4.0，exp 右移成 5。第二轮 exp = 5，最低位为 1，res 变成 1.0 * 4.0 = 4.0，也就是把 $x^2$ 收进答案；base 变成 16.0，exp 右移成 2。第三轮 exp = 2，最低位为 0，res 仍是 4.0；base 变成 256.0，exp 右移成 1。第四轮 exp = 1，最低位为 1，res 变成 4.0 * 256.0 = 1024.0，即 $x^2 \cdot x^8$；base 平方成 65536.0，exp 右移成 0，循环结束，返回 1024.0。

整个过程只做了 4 次平方和 2 次乘入，验证了乘法次数是 $\log_2 10$ 级别；答案 1024 也正好等于 $2^{2} \cdot 2^{8}$，与「二进制 1010 的两个 1 位分别贡献 $x^2$ 和 $x^8$」完全吻合。

再用 x = 2.0、n = -3 验证负指数：exp = -3 转换为 x = 0.5、exp = 3。第一轮最低位为 1，res = 0.5，base = 0.25，exp = 1；第二轮最低位为 1，res = 0.5 * 0.25 = 0.125，exp = 0，返回 0.125，正是 $1/8$。

代码实现

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(\log n)$，每轮把指数右移一位，循环次数等于 $ n $ 的二进制位数，最多 32 轮，每轮只做常数次浮点乘法。
  • 空间复杂度：$O(1)$，迭代写法只用 res、base、exp 三个变量，没有递归栈；若写成递归版本则需要 $O(\log n)$ 的栈深度。

关键点总结

  • 看到「指数/次数是 int 全域」就要意识到线性做法不可行，倍增（每步把规模减半）是把线性降到对数的标准手段，同一套模板可以套到模幂、矩阵幂、斐波那契上。
  • 快速幂的迭代写法就是「按二进制位拆解指数」，把 $x^n$ 写成若干 $x^{2^i}$ 的乘积，这个视角比递归更容易解释，也更好写对。
  • 循环不变量 res * base^exp = 答案 是验证代码正确性的抓手，写完后代入初始状态和终止状态各检查一次，比盲目试样例可靠得多。
  • 负数取绝对值前先扩宽类型，是所有涉及 Integer.MIN_VALUE 的题目的通用防御；同样的陷阱在「整数反转」「两数相除」里反复出现。
  • 面试视角：面试官几乎必问两件事——为什么用 long 存指数，以及递归版的栈深度和终止条件。递归写法要写成 half = myPow(x, n / 2); return n % 2 == 0 ? half * half : half * half * x;，务必只递归一次再平方，写成 myPow(x, n/2) * myPow(x, n/2) 会退化回 $O(n)$。

易错点总结

  • 错误写法：用 int 存指数并直接 n = -n → 用例 x = 2.0, n = -2147483648，取反后溢出仍是负数，while (n > 0) 一次都不执行，返回 1.0，正确答案是一个极小的正数（实际输出 0.0）。
  • 错误写法：把 exp >>= 1 写成 exp /= 2 却忘了先转正 → 用例 n = -3 未做取倒数转换时，负数右移与除法行为不同，循环无法终止或直接返回 1.0。
  • 错误写法：忘记在循环里更新 base *= base → 用例 x = 2.0, n = 10，base 恒为 2.0，答案退化成 2 的「1 位个数」次幂即 4.0，而不是 1024.0。
  • 错误写法：把 res *= base 写在位判断之外 → 用例 x = 2.0, n = 4，每轮都乘一次，得到 $2^{1+2+4+8}$ 量级的结果 32768.0，正确答案是 16.0。
  • 错误写法：递归版写成 return myPow(x, n / 2) * myPow(x, n / 2) → 用例 n = 1000000，两次递归让调用次数回到 $O(n)$，直接超时。
  • 错误写法：递归时用 n % 2 == 1 判奇偶而未先转正 → 用例 n = -3，Java 里 -3 % 2 等于 -1 而非 1，奇数分支被跳过，答案漏乘一个 x。
  • 错误写法：把 res 初始化成 x 而不是 1.0 → 用例 x = 2.0, n = 0，循环不执行直接返回 2.0，正确答案是 1.0。
  • 错误写法：为负指数写成 return 1 / myPow(x, -n) 而不提升类型 → 用例 n = -2147483648，-n 溢出成自身，递归参数仍为负，无限递归直到栈溢出。
  • 错误写法：用 Math.pow 偷懒 → 本题明确禁止调用库幂函数，考点是倍增思想，面试中这样写等于没答。
  • 错误写法：担心精度而给 res 做四舍五入，例如返回 Math.round(res * 1e5) / 1e5 → 用例 x = 0.00001, n = 2147483647，正常应返回 0.0，人为舍入反而在其它用例上把 2.0^-3 = 0.125 之类的正常结果精度打乱。

相似题目

题目 难度 考察点
50. Pow(x, n) 中等 完全同题的英文版，可直接对照递归与迭代两种写法
372. 超级次方 中等 指数以数组形式给出，需要结合取模与逐位拆解的模幂
29. 两数相除 中等 同样用倍增把线性减法降到对数，且同样要防 Integer.MIN_VALUE
231. 2 的幂 简单 反向判定，考察 n & (n - 1) 这类位运算技巧
326. 3 的幂 简单 底数非 2 无法用位运算，只能循环除或用最大幂取模
509. 斐波那契数 简单 快速幂的矩阵推广，可用 2×2 矩阵幂做到对数时间