2026-08-29
#50 数学模拟 中等

Pow(x, n)

在 LeetCode 上查看 ↗

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

实现 pow(x, n)，即计算 x 的整数 n 次幂函数（即，xn）。

示例 1

输入：x = 2.00000, n = 10
输出：1024.00000

示例 2

输入：x = 2.10000, n = 3
输出：9.26100

示例 3

输入：x = 2.00000, n = -2
输出：0.25000
2-2 = 1/22 = 1/4 = 0.25

💭 模拟答题者思考

1. 最直接：循环 n 次做 result *= x——思路对，但 n 可达 2³¹，O(n) 必超时。

2. 重复在哪里？乘方满足 xn = xn/2 × xn/2（n 为偶数）或 xn = x × xn-1（n 为奇数）——同一底数被反复平方，可以「折半」处理指数。

3. 关键转化（快速幂）：把 n 写成二进制，例如 10 = 1010₂，则 x10 = x8 × x2。从低位到高位扫描：当前位为 1 就把 result 乘上此时的 x，然后 x 自乘、n 右移一位。

4. 手推示例 1（x=2, n=10）：10 = 1010₂。第 1 轮（末位 0）只平方 x→4；第 2 轮（末位 1）result×4=4，x→16；第 3 轮（末位 0）x→256；第 4 轮（末位 1）result×256=1024。✓

5. 负指数：若 n < 0，等价于计算 (1/x)|n|，先把 x 取倒数、exp 取绝对值；n = INT_MIN 时 -n 在 32 位会溢出，必须用 long long 存指数。

🧠 变量语义（先读这三句再编码）

变量类型语义（三句法）
resultdouble定义：当前已累积的幂次结果，初始为 1.0
维护：每当指数 exp 的最低二进制位为 1 时，乘上当前的底数 x
更新：若 exp & 1 则 result *= x；每轮循环结束后 x 会自乘，exp 右移一位
xdouble定义：当前轮的「底数」，代表 原底数2k（k 为已右移的位数）
维护：每轮循环末尾自乘一次，相当于底数平方
更新：若 n < 0 先变为 1/x；循环中 x *= x
explong long定义：剩余待处理的指数（绝对值），用 long long 避免 INT_MIN 取负溢出
维护：每轮右移一位，等价于将指数二进制表示从低位向高位消费
更新：若原 n < 0 则 exp = -(long long)n；否则 exp = n；循环中 exp >>= 1

⌨️ 落码步骤

1. 若 n < 0：令 x = 1.0 / x，exp = -(long long)n；否则 exp = n

2. 初始化 result = 1.0

3. 循环 while exp > 0：若 exp & 1（最低位为 1），则 result *= x

4. 每轮末尾：x *= x（底数平方），exp >>= 1（指数折半）

5. 返回 result

💻 代码实现 

class Solution:
    def myPow(self, x: float, n: int) -> float:
        exp = n
        if exp < 0:
            x = 1.0 / x
            exp = -exp          # Python int 无溢出，INT_MIN 也安全
        result = 1.0
        while exp:
            if exp & 1:         # 当前二进制位为 1，乘上这一轮的底数
                result *= x
            x *= x              # 底数平方，对应指数左移一位
            exp >>= 1
        return result
class Solution {
public:
    double myPow(double x, int n) {
        long long exp = n;          // 用 long long 避免 INT_MIN 取负溢出
        if (exp < 0) {
            x = 1.0 / x;
            exp = -exp;
        }
        double result = 1.0;
        while (exp > 0) {
            if (exp & 1)            // 当前二进制位为 1
                result *= x;
            x *= x;                 // 底数平方
            exp >>= 1;
        }
        return result;
    }
};
// 时间 O(log|n|)，空间 O(1)

📈 复杂度分析

时间复杂度 O(log|n|)
空间复杂度 O(1)

⚠️ 常见坑

❗ n = INT_MIN (-2147483648) 时，-n 在 32 位 int 中会溢出；C++ 必须先把 n 转成 long long 再取负。

❗ 负指数要先对 x 取倒数再算正指数幂，不要直接循环负数次乘法。

❗ 判断当前位用 exp & 1 或 exp % 2 == 1，不要用浮点；底数 x 可以为 0（此时 n > 0 才出现，结果为 0）。

🔍 必测边界 Case

Case 1：指数为 0
x = 2.0, n = 0 → 1.0（任何非零数的 0 次幂为 1）
Case 2：负指数
x = 2.0, n = -2 → 0.25（等价于 1/4）
Case 3：底数为 1
x = 1.0, n = 100000 → 1.0
Case 4：INT_MIN 指数
x = 2.0, n = -2147483648 → 2.0-2147483648（需 long long 处理，不能对 int 直接取负）
Case 5：底数为负、指数为偶数
x = -2.0, n = 2 → 4.0（负底数偶次幂为正）