Pow(x, n) 图解题解

这道题到底在问什么

输入

x = 2, n = 11

输出

2048（即 2^11）

最优解：一步一步想明白

1. 3记住两条线：base 每步自乘平方升档（x,x²,x⁴,x⁸…）；result 只在「当前二进制位是 1」时把 base 乘进去。
2. 4先把 n=11 写成二进制 1011。下面把它低位在左摆开，指针 i 从最低位扫到最高位。result 起步 1，base 起步 x=2。
3. 5二进制第 k 位的权重是 2^k。11 = 1+2+8，所以 2^11 只需把这几档（x 的 2^k 次方）乘起来。
4. 6一切就绪：result=1、base=x=2，指针 i 落在最低位（第 0 位）。下面开始逐位处理。
5. 7指针 i 走到第 0 位，这一位是 1。是 1，说明 x 的这一档（base）要算进答案。
6. 8这一位是 1：把当前档 base=2 乘进结果，result 从 1 变成 2。
7. 9不管这一位是几，扫完都把 base 自乘平方：base 从 2 升到 4，准备给更高一位用。
8. 10第 0 位处理完毕（标灰），指针 i 右移一格去看第 1 位。
9. 11指针 i 走到第 1 位，这一位是 1。是 1，说明 x 的这一档（base）要算进答案。
10. 12这一位是 1：把当前档 base=4 乘进结果，result 从 2 变成 8。
11. 13不管这一位是几，扫完都把 base 自乘平方：base 从 4 升到 16，准备给更高一位用。
12. 14第 1 位处理完毕（标灰），指针 i 右移一格去看第 2 位。
13. 15指针 i 走到第 2 位，这一位是 0。是 0，说明这一档跳过，result 暂时不动。
14. 16这一位是 0：什么都不乘，result 原样保留 8（标红的就是这个被跳过的 0）。
15. 17不管这一位是几，扫完都把 base 自乘平方：base 从 16 升到 256，准备给更高一位用。
16. 18第 2 位处理完毕（标灰），指针 i 右移一格去看第 3 位。
17. 19指针 i 走到第 3 位，这一位是 1。是 1，说明 x 的这一档（base）要算进答案。
18. 20这一位是 1：把当前档 base=256 乘进结果，result 从 8 变成 2048。
19. 21不管这一位是几，扫完都把 base 自乘平方：base 从 256 升到 65536，准备给更高一位用。
20. 22第 3 位是最高位，处理完它，整个二进制就扫完了。
21. 23四位全部扫完。所有「位是 1」的档（高亮处）都乘进了 result，最终 2^11 = 2048，这就是答案。

⚠️ 容易写错的地方

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

def myPow(x, n):
    if n < 0:                 # 负指数：取倒数、指数变正
        x, n = 1 / x, -n
    result = 1.0
    base = x
    while n > 0:
        if n & 1:             # 当前最低位是 1
            result *= base    # 把这一档乘进答案
        base *= base          # 升到下一档 x→x²→x⁴…
        n >>= 1               # 右移，看下一位
    return result

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

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

复杂度

面试官可能追问