剑指 Offer 16-数值的整数次方(数值的整数次方 LCOF)

# 中文题目

输入：x = 2.00000, n = 10
输出：1024.00000

输入：x = 2.10000, n = 3
输出：9.26100

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

# 通过代码

class Solution {
    public double myPow(double x, int n) {
        if(n == 0){
            return 1.0;
        }
        int m = 0;
        if(n < 0){
            m = -(n/2);
            x = 1.0 /x;
        }else{
            m = n/2;
        }
        return (n % 2 == 0) ? Math.pow(x*x, m) :x*Math.pow(x*x, m); 
    }
}

class Solution {
    public double myPow(double x, int n) {
        if(n == 0){
            return 1.0;
        }
        int m = 0;
        if(n < 0){
            m = -(n/2);
            x = 1.0 /x;
        }else{
            m = n/2;
        }
        return (n % 2 == 0) ? Math.pow(x*x, m) :x*Math.pow(x*x, m); 
    }
}

class Solution {
    public double myPow(double x, int n) {
        // 如果x==0，直接返回0，避免后面1/0报错
        if (x == 0) {
            return 0;
        }
        // 乘方次数,注意这里要用long型，因为-2147483648的正数+2147483648没办法用int表示，需要使用long
        long b = n;
        // 结果值
        double res = 1.0;
        // 如果乘方次数小于0，比如2^-2  可以转换为(1/2)^2
        if (b < 0) {
            // 底数取倒
            x = 1 / x;
            // 指数取正
            b = -b;
        }
        // 当指数大于0时
        while (b > 0) {
            // 如果当前指数为奇数的话，将多出一项x，乘入res
            // 最后都会变成 x^n=x^0*res=res
            // 当 b为1时，就会将之前的结果都乘入到res中
            if ((b & 1) == 1)
                res *= x;
            x *= x;
            b >>= 1;
        }
        return res;
    }
}

# 高赞题解

# 解题思路：

求 $x^n$ 最简单的方法是通过循环将 $n$ 个 $x$ 乘起来，依次求 $x^1, x^2, ..., x^{n-1}, x^n$ ，时间复杂度为 $O(n)$ 。 快速幂法 可将时间复杂度降低至 $O(log_2 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}$ 累计相乘即可。

  • 当 $b_i = 0$ 时：$x^{2^{i-1}b_i} = 1$ ；
  • 当 $b_i = 1$ 时：$x^{2^{i-1}b_i} = x^{2^{i-1}}$ ；

{:width=450}

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

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

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

  • 当 $n$ 为偶数： $x^n = (x^2)^{n//2}$ ；
  • 当 $n$ 为奇数： $x^n = x(x^2)^{n//2}$ ，即会多出一项 $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$ （避免后续 $x = 1 / x$ 操作报错）。
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_2 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: return 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) return 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;
    }
}

# 提交历史

# 统计信息