Pow(x, n) 图解题解

这道题到底在问什么

x, n

2.00000, 10

输出

1024.00000

最优解：一步一步想明白

1. 3最朴素的写法：把 x 连乘 n 次。可 n 最大约 21 亿，连乘 21 亿次必然超时，O(n) 走不通。
2. 4关键观察：13 的二进制是 1101，所以 x 的 13 次方 = x¹ × x⁴ × x⁸。只要逐位扫 n，遇到 1 就把当前这块乘进答案。
3. 513 的二进制 = 1101，置位的是第 0、2、3 位先看清 13 的二进制 1101：从低位到高位，第 0、2、3 位是 1，这三位决定哪些 base 要乘进答案。下面每一轮都拆成『看最低位、决定乘不乘』和『base 平方、n 减半』两帧，节奏全程一致。
4. 6ans=1.0 / base=2 / n=13（二进制 1101）开局三个变量：答案 ans 从 1 起步，base 就是 x（这里是 2），指数 n=13。每轮只盯 n 的最低位。
5. 7ans: 1 → 2（乘上 base=2）第 0 轮先看最低位：n=13 最低位是 1，把当前 base=2 乘进答案，ans 从 1 变成 2。这一帧只做这一件事——乘答案，base 还没动。
6. 8base: 2 → 4；n: 13 → 6本轮收尾固定两步：base 自己平方（2 变 4，代表 x²），n 右移一位（13 变 6）。base 翻倍指数，对应二进制往高位走。
7. 9n=6 最低位=0；ans 保持 2 不动进入第 1 轮，base 此刻是 4（上一轮平方而来，代表 x²）。看最低位：n=6 最低位是 0，说明 x² 这一项不要，ans 保持 2 不动。这一帧只是『看一眼、不乘』。
8. 10base: 4 → 16；n: 6 → 3和每轮一样收尾：base 平方（4 变 16，代表 x⁴），n 减半到 3。注意——base 在每轮结尾都恰好平方一次，时序固定，别数多也别数漏。
9. 11ans: 2 → 32（乘上 base=16）第 2 轮先看最低位：n=3 最低位是 1，此刻 base=16 正好代表 x 的 4 次方，乘进答案，ans 从 2 变 32。这一帧 base 仍是 16，还没平方。
10. 12base: 16 → 256；n: 3 → 1本轮收尾照旧：base 平方（16 变 256，代表 x⁸），n 减半到 1。记住这一步——256 是在第 2 轮结尾才长出来的，下一轮直接拿来用，不会再平方第二次。
11. 13ans: 32 → 8192（乘上 base=256）最后一轮，base 此刻正是 256（上一轮已由 16 平方而来，代表 x⁸），最低位仍是 1，直接 ans = 32 × 256 = 8192。这里没有任何『再平方』动作——256 是上轮收尾就备好的。
12. 14base: 256 → 65536；n: 1 → 0，结束收尾仍是同两步：base 再平方成 65536（但 n 已为 0，这个值用不上了），n 减半归 0。while 退出，ans=8192 正是 2 的 13 次方。每轮结尾平方一次，全程数下来 base 恰好平方了 4 次。
13. 152 的 -3 次方 = (1 除以 2) 的 3 次方 = 0.125遇到负指数别在循环里特判。开头统一把 x 变成它的倒数、n 取相反数变成正数，后面主循环完全一样。
14. 18一句话本质：n 的二进制每个为 1 的位，对应的 base 恰好是 x 的那一段，乘进去就还原了 x 的 n 次方。
15. 24同一套「遇 1 就乘、每轮平方」可迁移：把 base 换成矩阵，就能 O(log n) 求斐波那契、数图上长度为 n 的路径数。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1 / x
            n = -n
        ans = 1.0
        base = x
        while n:
            if n & 1:
                ans *= base
            base *= base
            n >>= 1
        return ans

class Solution {
public:
    double myPow(double x, int n) {
        long long exp = n;            // 防 INT_MIN 取负溢出
        if (exp < 0) {
            x = 1.0 / x;
            exp = -exp;
        }
        double ans = 1.0, base = x;
        while (exp > 0) {
            if (exp & 1) ans *= base;
            base *= base;
            exp >>= 1;
        }
        return ans;
    }
};

class Solution {
    public double myPow(double x, int n) {
        long exp = n;                 // 用 long 防 INT_MIN 溢出
        if (exp < 0) {
            x = 1.0 / x;
            exp = -exp;
        }
        double ans = 1.0, base = x;
        while (exp > 0) {
            if ((exp & 1) == 1) ans *= base;
            base *= base;
            exp >>= 1;
        }
        return ans;
    }
}

# 快速幂骨架：把指数 n 拆二进制
if n < 0:                 # ① 负指数先转正
    x, n = 1 / x, -n
ans, base = 1.0, x
while n:
    if n & 1:             # ② 当前最低位是 1 吗
        ans *= base       #    是 → 乘进答案
    base *= base          # ③ base 平方（指数翻倍）
    n >>= 1               # ④ 指数减半
return ans

long long exp = n;        // ① 用 long long 防溢出
if (exp < 0) { x = 1.0 / x; exp = -exp; }
double ans = 1.0, base = x;
while (exp > 0) {
    if (exp & 1) ans *= base; // ② 最低位为 1 才乘
    base *= base;             // ③ 平方
    exp >>= 1;                // ④ 减半
}
return ans;

long exp = n;             // ① 用 long 防溢出
if (exp < 0) { x = 1.0 / x; exp = -exp; }
double ans = 1.0, base = x;
while (exp > 0) {
    if ((exp & 1) == 1) ans *= base; // ② 最低位为 1 才乘
    base *= base;                     // ③ 平方
    exp >>= 1;                        // ④ 减半
}
return ans;

复杂度

面试官可能追问