如何用快速幂高效计算 x 的 n 次方？（LeetCode 50）

简化版

计算 x^n（x 是浮点数，n 是整数，可能为负）。朴素连乘 n 次是 O(n)，用快速幂（二分幂）能降到 O(log n)：核心思想是 x^n = (x^(n/2))²——把指数折半，每次平方，指数减半。n 为负时先取 x^(-n) 再取倒数。可用递归（分治）或迭代（按 n 的二进制位）实现。

详细版

迭代版（按二进制位，推荐）

double myPow(double x, int n) {
    long N = n;                     // 用 long 防止 n = Integer.MIN_VALUE 取负溢出
    if (N < 0) { x = 1 / x; N = -N; }
    double res = 1.0;
    while (N > 0) {
        if ((N & 1) == 1) res *= x; // 当前二进制位为 1，累乘当前的 x
        x *= x;                     // x 平方，对应指数翻倍
        N >>= 1;                    // 处理下一位
    }
    return res;
}

递归版（分治）

double myPow(double x, int n) {
    long N = n;
    if (N < 0) { x = 1 / x; N = -N; }
    return fastPow(x, N);
}
double fastPow(double x, long n) {
    if (n == 0) return 1.0;
    double half = fastPow(x, n / 2);      // 先算一半
    return n % 2 == 0 ? half * half : half * half * x;   // 平方，奇数再乘一个 x
}

核心：x^n = (x^(n/2))²，指数每次折半，O(log n) 次乘法。
负指数：x^(-n) = 1 / x^n，先把 x 变 1/x、n 变正。
溢出坑：n = Integer.MIN_VALUE（-2³¹）取负会溢出 int，必须先转 long。
复杂度：O(log n) 时间、O(1)（迭代）或 O(log n)（递归栈）空间。

完整版教学

一、朴素连乘的问题

x^n 最直接的算法是「乘 n 次」：res = 1; for n times: res *= x。O(n) 时间。当 n 很大（比如 2³¹）时，上亿次乘法太慢。快速幂利用「指数可以折半」把它降到 O(log n)。

二、核心思想：指数折半

关键恒等式：

x^n = (x^(n/2))²           （n 为偶数）
x^n = (x^(n/2))² × x       （n 为奇数，n/2 整除向下取整）

意思是：要算 x^n，先递归算出 x^(n/2)，再平方一下就得到 x^n（n 奇数时再补乘一个 x）。每递归一层，指数减半，所以只需 O(log n) 层，每层一次平方（乘法）。这就是「二分幂 / 快速幂」。

例：x^10 = (x^5)²，x^5 = (x^2)² × x，x^2 = (x^1)²……指数 10→5→2→1→0，只需 4 层，远少于 10 次连乘。

三、迭代版：按 n 的二进制位理解

迭代版更巧妙，从二进制角度看：任何 n 可写成二进制，如 13 = 1101₂ = 8 + 4 + 1，所以 x^13 = x^8 × x^4 × x^1。算法：

维护一个「当前位对应的幂」x（依次是 x^1, x^2, x^4, x^8, ...，每轮平方翻倍）。
从低位到高位扫 n 的每个二进制位，若该位是 1（N & 1），就把当前的 x 乘进结果。
x *= x（指数翻倍，对应下一位），N >>= 1（看下一位）。

这样把 x^n 拆成若干个「x 的 2 的幂次方」相乘，恰好 O(log n) 次。位运算 & 1、>> 1 让代码简洁高效。

四、负指数与溢出坑（关键）

负指数：x^(-n) = 1 / x^n。所以 n < 0 时，把 x 换成 1/x、n 换成 -n，再按正指数算。

溢出坑（高频错误）：n 是 int，范围 [-2³¹, 2³¹-1]。当 n = Integer.MIN_VALUE = -2³¹ 时，-n = 2³¹ 超出 int 上限（2³¹-1），直接取负会溢出成负数，导致死循环或错误。解决：先把 n 赋给一个 long N，再对 long 取负——long 范围足够大，-(-2³¹) 不会溢出。这是本题必踩的坑，务必用 long。

五、易错点与应用

忘记用 long 处理 MIN_VALUE → 最经典 bug。
递归版指数用 n/2 而非重复调用两次：half = fastPow(x, n/2) 只递归一次再平方，别写成 fastPow(x,n/2) * fastPow(x,n/2)（那样退化成 O(n)）。
应用广泛：快速幂取模（(x^n) mod p，在密码学 RSA、组合数取模里核心）——把每步乘法后 % p 即可；矩阵快速幂（用 O(log n) 求斐波那契第 n 项、线性递推）。这些都是快速幂的延伸。

六、二进制拆指数的乘法不变量

迭代快速幂维护 res * base^N 等于尚未变换前的目标幂。若 N 为奇数，把一个 base 乘入 res 后再折半；无论奇偶，base 平方对应下一位权值翻倍，N 右移删除已处理最低位。

计算 2^13，13=1101₂
初始 res=1, base=2, N=13
低位 1：res=2；base=4，N=6
低位 0：res=2；base=16，N=3
低位 1：res=32；base=256，N=1
低位 1：res=8192；N=0
结果 8192

校验维度	本题必须保持的结论
循环/递推不变量	每轮开始时 `res * base^N` 恒等于原目标；处理最低位后该等式继续成立。
边界条件	先把 int n 转 long 再取负，避免 `Integer.MIN_VALUE` 溢出；`0` 的负指数按题目输入约束处理。
复杂度与代价	指数每轮右移一位，O(log
自检方式	用最小输入、典型输入和触及边界的输入分别手推，结果应与定义一致。

这组推演的作用不是替代证明，而是把抽象规则落到每一步状态变化上。面试写完代码后，应主动指出不变量如何保证不漏解，以及边界为何不会越界或死循环。若手推结果与定义不一致，应先修正状态语义，而不是继续给代码打补丁。

七、面试现场如何验证这道题

数学题不能只凭样例相信公式，必须同时核对定义域、推导条件和定宽整数边界。本题应先复述这条不变量：每轮开始时 res * base^N 恒等于原目标；处理最低位后该等式继续成立。只有代码的初始化、更新顺序和终止条件都维持它，样例通过才具有证明力。

典型路径从“计算 2^13，13=1101₂”开始手推，最后应得到“结果 8192”。
边界复核：先把 int n 转 long 再取负，避免 Integer.MIN_VALUE 溢出；0 的负指数按题目输入约束处理。
代价复核：指数每轮右移一位，O(log |n|) 时间；迭代 O(1) 空间，递归 O(log |n|) 栈。
用 0、1、最小合法值和最大合法值检查公式的定义域。
乘法、取绝对值或取负前先判断是否可能触及 Integer.MIN_VALUE 等不对称边界。
若算法依赖单调性、抵消或整除关系，要明确题设保证何时成立、何时必须额外验证。

最后要主动构造一个“少写一次循环、改变一个不等号或交换两行更新就会失败”的反例。能说清反例破坏了哪条不变量，比只报出复杂度更能证明真正掌握了算法。

记忆钩子：本题的代码可以压缩，但“每轮开始时 res * base^N 恒等于原目标；处理最低位后该等式继续成立。”这条正确性主线不能省。

八、常见误区与追问

误区：递归写两次 fastPow(x,n/2) 仍是 O(log n)。 它形成两棵重复子树，递推会退化到 O(n)，应只算一次 half 再平方。
误区：-Integer.MIN_VALUE 会得到正数。 int 范围不对称，直接取负仍溢出；必须先提升到 long。
误区：负指数只需把最终结果取负。 负指数表示倒数，应把底数变为 1/x，而不是改变符号。
追问：为什么奇数指数要额外乘一次 base？ N=2k+1，折半平方只覆盖 base^(2k)，还缺一个 base。
追问：快速幂取模如何避免数值爆炸？ 每次乘法和平方后立即取模，并用更宽类型承接乘积。
追问：浮点结果为何可能不精确？ double 的二进制浮点表示和重复乘法都会引入舍入误差，算法只保证计算流程。

九、加强记忆

快速幂（求 x^n）= 指数折半、逐层平方，把 O(n) 降到 O(log n)。核心恒等式 x^n = (x^(n/2))²（奇数再补乘一个 x）。迭代版按 n 的二进制位：N&1 为 1 就 res *= x，然后 x *= x（指数翻倍）、N >>= 1——把 x^n 拆成若干「x 的 2 的幂」相乘。两个坑：负指数用 x=1/x, n=-n；n=Integer.MIN_VALUE 取负溢出，必须先转 long。延伸：快速幂取模（RSA）、矩阵快速幂（斐波那契 O(log n)）。核心：幂折半、底平方。

简化版

详细版