CS-Notes 剑指 Offer 16 题解：数值的整数次方——分治思想下的快速幂实现

本篇技术指南基于 notes/16. 数值的整数次方.md 展开，讲解“给定 double 型浮点数 x 与 int 型整数 n，求 x 的 n 次方”这一经典面试算法题。读完本文，你将理解如何用分治（快速幂）把朴素 O(N) 的连续乘法优化到 O(logN)，掌握递归与迭代两种可落地的 Java 实现，并弄清负指数、整数最小值取负溢出等边界陷阱的处理方式。

题目描述

给定一个 double 类型的浮点数 x 和 int 类型的整数 n，求 x 的 n 次方。

注意题目对两个参数的类型限定：x 是浮点数，意味着结果必须按浮点语义返回；n 是有符号 32 位整数，既可能为正也可能为负，n 为负时实际要求的是 x 的 |n| 次方再取倒数。这两个类型细节是后续边界处理的根源。

核心思路：用分治替代线性乘法

为什么线性乘法不够好

最直观的解法是把 x 重复乘 n 次：x * x * x * ... * x，时间复杂度为 O(N)。当 n 达到 int 上限（约 21 亿）时，线性乘法在工程上完全不可行。

分治递推关系

因为乘法是可交换的，可以把连乘操作拆开成两半：(x*x*...*x) * (x*x*...*x)，两半的计算完全一样，只需计算一次。而对新拆出来的子问题，又可以继续拆下去——这就是分治思想：将原问题的规模拆成多个规模较小的子问题，最后把子问题的解合并起来。

用数学式表达，本题的递推关系为：

x^n = { x^(n/2) * x^(n/2)          n % 2 == 0
      { x * (x^(n/2) * x^(n/2))     n % 2 == 1

也就是说：子问题始终是 x^(n/2)，合并步骤是把子问题的解自乘；若 n 是奇数，拆成两半后会剩下一个 x，合并时再多乘一个 x 即可。

由于每次递归 n 都减半，递归树的深度是 logN，而每层合并只做常数次乘法，因此整个算法的时间复杂度为 O(logN)；递归调用栈的深度为 O(logN)，空间复杂度同为 O(logN)。

Java 递归实现（原笔记解法）

notes/16. 数值的整数次方.md 中给出的原始解法分为两层：外层 Power 负责处理负指数的符号转换，内层 pow 只处理非负指数，职责分离后递归逻辑非常干净：

public double Power(double x, int n) {
    boolean isNegative = false;
    if (n < 0) {
        n = -n;                 // 转为正指数，并记录需要取倒数
        isNegative = true;
    }
    double res = pow(x, n);
    return isNegative ? 1 / res : res;
}

private double pow(double x, int n) {
    if (n == 0) return 1;      // 递归出口：任何数的 0 次方为 1
    if (n == 1) return x;      // 递归出口：1 次方即自身
    double res = pow(x, n / 2);      // 分治：先解规模减半的子问题
    res = res * res;                // 合并：子问题解自乘
    if (n % 2 != 0) res *= x;       // 奇数指数：多乘一个 x
    return res;
}

以 x = 2, n = 13 走一遍合并过程：pow(2,13) -> pow(2,6) -> pow(2,3) -> pow(2,1) = 2，逐层回退合并时依次为 2*2=4（3 为奇数再乘 2 得 8，即 2^3）、8*8=64（2^6）、64*64=4096 再乘 2 得 8192（2^13）。递归链长度仅 4 层，而朴素连乘需要 13 次乘法——这正是 logN 与 N 的差距。

迭代实现：二进制快速幂

分治的本质是“反复平方、按需累乘”，用迭代可以完全消除递归栈开销，空间降为 O(1)。其依据是：把指数 n 写成二进制后，x^n 就是各个“2 的幂次方”对应的 x 的幂相乘。以 n = 13 = 1101(2) 为例，需要 x^8 * x^4 * x^1。

public double myPow(double x, int n) {
    long N = n;                    // 用 long 承接，规避 int 最小值取负的溢出
    if (N < 0) {
        x = 1 / x;                 // 负指数：先取底数倒数，把问题转正
        N = -N;
    }
    double ans = 1;
    while (N > 0) {
        if ((N & 1) == 1) ans *= x;   // 当前二进制位为 1：累乘进结果
        x *= x;                      // 底数自乘，对应幂次翻倍
        N >>= 1;                     // 右移一位，处理下一个二进制位
    }
    return ans;
}

两种实现结果一致、时间复杂度都是 O(logN)：递归版更贴近分治的推导过程、可读性强；迭代版没有调用栈开销，在指数极大时更稳。面试中建议先写出递归版讲清分治原理，再给出迭代版作为工程优化。

必须关注的边界情况

结合 notes/16. 数值的整数次方.md 原始解法中 n = -n 这一行写法，有几个容易踩的坑：

1. n = Integer.MIN_VALUE 时的取负溢出。Java 中 int 的取值范围是 [-2^31, 2^31-1]，-(-2147483648) 超出了 int 最大值，直接 n = -n 会得到错误的负数。规避方式有二：一是先把 x 替换为 1/x，再对正数取负（迭代版采用的做法）；二是像上面的 myPow 一样用 long 承接 n。
2. n = 0 时约定返回 1。递归出口 if (n == 0) return 1 保证了这一点；此时即使 x = 0 也按 1 返回，这是工程上的通行约定，实际业务中 0 的 0 次方是否合法应由调用方在入口处校验。
3. x = 0 且 n 为负数。0 的任何正次方为 0，取倒数 1/0.0 会溢出为无穷大；若题目保证结果有界，应在入口提前拦截“底数为 0 且指数为负”的非法输入，避免依赖浮点溢出行为。

分治思想在仓库中的脉络

在 notes/剑指 Offer 题解 - 目录.md 中，本题被归入“分治”专题，是该专题下剑指 Offer 系列的代表性题目；仓库的 notes/Leetcode 题解 - 分治.md 还收录了“给表达式加括号”“不同的二叉搜索树”等 LeetCode 分治题，可以对照阅读：这些题目的共同结构都是“确定拆分点 -> 递归解左右子问题 -> 合并子问题解”，而数值的整数次方是最小、最纯粹的分治样例，适合作为理解整个专题的起点。

小结

要点	结论
朴素解法	连续相乘，时间 O(N)，指数极大时不可行
分治解法	子问题 x^(n/2) 自乘合并，奇数多乘一个 x，时间 O(logN)
递归实现	外层处理负指数符号，内层只处理非负指数，代码见 notes/16. 数值的整数次方.md
迭代实现	二进制位驱动“按需累乘 + 反复平方”，空间 O(1)
高频陷阱	Integer.MIN_VALUE 取负溢出、n = 0 返回 1、底数为 0 时的负指数

掌握本题的关键在于把“求幂”抽象成“指数减半、平方合并”的分治过程，并能在递归与迭代两种形态之间自由转换，这正是分治类题目在面试中最核心的考察点。