50. Pow(X, N)

解题思路：

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

快速幂解析（二进制角度）：

利用十进制数字 $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} $$

{:width=450}

快速幂解析（分治法角度）：

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

• $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$ 即可。

{:width=450}

• 转化为位运算：
  • 向下整除 $n // 2$ 等价于 右移一位 $n >> 1$ ；
  • 取余数 $n % 2$ 等价于 判断二进制最右位 $n & 1$ ；

算法流程：

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$ 。

复杂度分析：

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

代码：

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

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

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;
    }
}