快速幂算法

LeetCode 50

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

• \(-100.0 < x < 100.0\)
• \(-2^{31} <= n <= 2^{31} - 1\)
• n 是一个整数
• 要么 x 不为零，要么 n > 0 。
• \(-10^4 <= x^n <= 10^4\)

由于 n 很大，所以不能暴力计算这个值，需要用到快速幂算法。

如何快速计算 \(x^8\) ？

\( x \to x^2 \to x^4 \to x^8 \)

从 x 开始，不断对自身平方，重复三次即可得到 \(x^8\)。

如何快速计算 \(x^{15}\) ？

\( x \cdot x^2 \cdot x^4 \cdot x^8 = x^{15} \)

在平方的过程中，把这些数全部相乘，即可得到 \(x^{15}\)。

如何快速计算 \(x^{13}\) ？

\( x \cdot x^4 \cdot x^8 = x^{13} \)

在平方的过程中，把 \(x, x^4, x^8\) 相乘，即可得到 \(x^{13}\)。

如何知道要把哪些数相乘？

把 n 看作二进制数，从低到高遍历二进制数，遇到 1 就和 x 的幂相乘。不断右移二进制数，右移前看最低位是否为 1。

\( 13 = 1101_{(2)} \)

如何处理 n < 0 的情况？

把 n 转换成 -n，把 x 转换成 1/x，就转换成了 n >= 0 的情况。

代码实现

double myPow(double x, int N) {
    double ans = 1;
    long long n = N;
    if (n < 0) { // x^-n = (1/x)^n
        n = -n;
        x = 1 / x;
    }
    while (n) { // 从低到高枚举 n 的每个比特位
        if (n & 1) { // 这个比特位是 1
            ans *= x; // 把 x 乘到 ans 中
        }
        x *= x; // x 自身平方
        n >>= 1; // 继续枚举下一个比特位
    }
    return ans;
}

时间复杂度：\(O(\log\lvert n \rvert)\)