Skip to content
当前页大纲

解题思路:

求 $x^n$ 最简单的方法是通过循环将 $n$ 个 $x$ 乘起来,依次求 $x^1, x^2, ..., x^{n-1}, x^n$ ,时间复杂度为 $O(n)$ 。 快速幂法 可将时间复杂度降低至 $O(\log n)$ ,以下从 「分治法」 和 「二进制」 两个角度解析快速幂法。

快速幂解析(分治法角度):

快速幂实际上是分治思想的一种应用。

二分推导: $x^n = x^{n/2} \times x^{n/2} = (x^2)^{n/2}$ ,令 $n/2$ 为整数,则需要分为奇偶两种情况(设向下取整除法符号为 "$//$" ):

$$ x^n = \begin{cases} (x^2)^{n//2} & , n 为偶数 \ x(x^2)^{n//2} & , n 为奇数 \ \end{cases} $$

观察发现,当 $n$ 为奇数时,二分后会多出一项 $x$ 。

幂结果获取:

  • 根据推导,可通过循环 $x = x^2$ 操作,每次把幂从 $n$ 降至 $n//2$ ,直至将幂降为 $0$ ;
  • 设 $res=1$ ,则初始状态 $x^n = x^n \times res$ 。在循环二分时,每当 $n$ 为奇数时,将多出的一项 $x$ 乘入 $res$ ,则最终可化至 $x^n = x^0 \times res = res$ ,返回 $res$ 即可。

Picture2.png

转化为位运算:

  • 向下整除 $n // 2$ 等价于 右移一位 $n >> 1$ ;
  • 取余数 $n \mod 2$ 等价于 判断二进制最右位 $n & 1$ ;

快速幂解析(二进制角度):

利用十进制数字 $n$ 的二进制表示,可对快速幂进行数学化解释。

对于任何十进制正整数 $n$ ,设其二进制为 "$b_m...b_3b_2b_1$"( $b_i$ 为二进制某位值,$i \in [1,m]$ ),则有:

  • 二进制转十进制: $n = 1b_1 + 2b_2 + 4b_3 + ... + 2^{m-1}b_m$ (即二进制转十进制公式)
  • 幂的二进制展开: $x^n = x^{1b_1 + 2b_2 + 4b_3 + ... + 2^{m-1}b_m} = x^{1b_1}x^{2b_2}x^{4b_3}...x^{2^{m-1}b_m}$ ;

根据以上推导,可把计算 $x^n$ 转化为解决以下两个问题:

  • 计算 $x^1, x^2, x^4, ..., x^{2^{m-1}}$ 的值: 循环赋值操作 $x = x^2$ 即可;
  • 获取二进制各位 $b_1, b_2, b_3, ..., b_m$ 的值: 循环执行以下操作即可。
    1. $n & 1$ (与操作): 判断 $n$ 二进制最右一位是否为 $1$ ;
    2. $n>>1$ (移位操作): $n$ 右移一位(可理解为删除最后一位)。

因此,应用以上操作,可在循环中依次计算 $x^{2^{0}b_1}, x^{2^{1}b_2}, ..., x^{2^{m-1}b_m}$ 的值,并将所有 $x^{2^{i-1}b_i}$ 累计相乘即可,其中:

$$ x^{2^{i-1}b_i}= \begin{cases} 1 & , b_i = 0 \ x^{2^{i-1}} & , b_i = 1 \ \end{cases} $$

Picture1.png

算法流程:

  1. 当 $x = 0.0$ 时:直接返回 $0.0$ ,以避免后续 $1$ 除以 $0$ 操作报错。分析: 数字 $0$ 的正数次幂恒为 $0$ ;$0$ 的 $0$ 次幂和负数次幂没有意义,因此直接返回 $0.0$ 即可。
  2. 初始化 $res = 1$ 。
  3. 当 $n < 0$ 时:把问题转化至 $n \geq 0$ 的范围内,即执行 $x = 1/x$ ,$n = - n$ 。
  4. 循环计算:当 $n = 0$ 时跳出。
    1. 当 $n & 1 = 1$ 时:将当前 $x$ 乘入 $res$ (即 $res *= x$ )。
    2. 执行 $x = x^2$ (即 $x *= x$ )。
    3. 执行 $n$ 右移一位(即 $n >>= 1$)。
  5. 返回 $res$ 。

代码:

Java 中 int32 变量区间 $n \in [-2147483648, 2147483647]$ ,因此当 $n = -2147483648$ 时执行 $n = -n$ 会因越界而赋值出错。解决方法是先将 $n$ 存入 long 变量 $b$ ,后面用 $b$ 操作即可。

Python
class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0.0: return 0.0
        res = 1
        if n < 0: x, n = 1 / x, -n
        while n:
            if n & 1: res *= x
            x *= x
            n >>= 1
        return res
Java
class Solution {
    public double myPow(double x, int n) {
        if(x == 0.0f) return 0.0d;
        long b = n;
        double res = 1.0;
        if(b < 0) {
            x = 1 / x;
            b = -b;
        }
        while(b > 0) {
            if((b & 1) == 1) res *= x;
            x *= x;
            b >>= 1;
        }
        return res;
    }
}
C++
class Solution {
public:
    double myPow(double x, int n) {
        if(x == 0.0f) return 0.0;
        long b = n;
        double res = 1.0;
        if(b < 0) {
            x = 1 / x;
            b = -b;
        }
        while(b > 0) {
            if((b & 1) == 1) res *= x;
            x *= x;
            b >>= 1;
        }
        return res;
    }
};

复杂度分析:

  • 时间复杂度 $O(\log n)$ : 二分的时间复杂度为对数级别。
  • 空间复杂度 $O(1)$ : $res$, $b$ 等变量占用常数大小额外空间。

MIT License.