50. Pow(x, n)（Pow(x, n)）

频次 ★★★★ · 难度 🟡 · 高频：字节/腾讯

题目

实现 pow(x, n)，即计算 x 的 n 次幂。

示例：

输入: x = 2.0, n = 10
输出: 1024.0

输入: x = 2.0, n = -2
输出: 0.25

思路

快速幂（二分指数）：把 n 视为二进制，每次将指数除以 2，底数平方，当当前最低位为 1 时累乘到结果。

n 为负数时，先取 x = 1/x、n = -n，再按正数处理（注意 n = -2^31 取反溢出）。

代码

public double myPow(double x, int n) {
    long N = n;                       // 用 long 防 -2^31 取反溢出
    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;                       // 底数平方
        N >>= 1;                      // 指数右移
    }
    return res;
}

复杂度

• 时间：O(log |n|) —— 指数每轮右移一位
• 空间：O(1)

边界条件

• n = 0：任何非零数的 0 次幂为 1（0^0 未定义，面试可从约定返回 1）
• n = -2^31（即 Integer.MIN_VALUE）：直接取反 -n 会溢出（int 范围 [-2^31, 2^31-1]），所以必须用 long 接收
• x = 0 且 n ≤ 0：0 的负次幂未定义（除零），需额外处理；若 n > 0 返回 0
• x = 1 或 -1：任何整数次幂直接返回 1 或 ±1（可加提前返回优化）

变式

• 递归快速幂：pow(x, n) = pow(x, n/2) * pow(x, n/2) * (n%2==1 ? x : 1)，空间 O(log n) 调用栈
• 模幂：pow(x, n) % MOD，在快速幂过程中每次乘法后取模即可，用于大数组合数计算
• 矩阵快速幂：将底数换成矩阵，乘法换成矩阵乘法，常见于线性递推（斐波那契数列）

易错点

• n 为 Integer.MIN_VALUE 时取反溢出：-n 仍然等于 -2147483648，导致死循环（n 永远 < 0）。用 long N = n 解决
• 负数处理时 x = 1/x 不能取整，必须用浮点除法
• (N & 1) == 1 检测最低位是否为 1，注意运算符优先级：位运算优先级低于 ==，括号不能省
• 浮点数判等不能直接用 ==，但本题不涉及精确比较，结果保留在合理误差内即可

面试追问

• 如果 n 很大（10^9），递归和迭代哪个好？ 迭代 O(log n) 空间 O(1) 优于递归的 O(log n) 栈空间；超长指数没有大数问题，Java double 只能表示约 10^308 范围，指数过大结果直接溢出为 Infinity 或 0，实际工程中要么用高精度库要么限制场景
• 除了二进制，还能怎么分治？ 可以按照十进制或任意进制拆分，原理都是把指数分解为底数相乘，二进制最简单直接
• 0^0 怎么处理？ 数学上未定义，工程上通常返回 1（各语言实现不同，Java 的 Math.pow(0,0) 返回 1.0）

关联题

• 同套路：69. x 的平方根 —— 二分或牛顿迭代求整数平方根
• 进阶：372. 超级次方 —— 大数组指数的快速幂
• 知识点：快速幂是求模幂、矩阵快速幂的基础，见数学