50. Pow(x, n)

Leetcode Math Binary Search

题目

Implement $\text{pow}(x, n)$, which calculates $x$ raised to the power $n$($x^n$).

Example 1:

Input: 2.00000, 10
Output: 1024.00000

Example 2:

Input: 2.10000, 3
Output: 9.26100

Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Note:

• $-100.0 < x < 100.0$
• $n$ is a 32-bit signed integer, within the range [−$2^{31}$, $2^{31}$ − 1]

分析

最直接的方式当然是$O(n)$的算法，将$x$乘以或者除以$n$次，

double myPow(double x, int n) {
    if (x == 0) return x;
    x = x > 0 ? x : 1.0/x;
    double res = x;
    for (int i = 1; i < n; i++) res *= x;
    return res;
}

可惜的这种方法超时了，稍微想一想就知道当$n$很大的时候，这种解法肯定是不行的。

另一种方法是使用分治算法，在这里，分治算法的递归公式为

$$x^n = x^{(n/2)} \times x^{(n/2)} \times x^{(n\%2)}$$

最差运行时间$T(n)$用递归表达式表达为

$$T(n) = T(n/2)\times T(n/2) \times T(n\%2)$$

因为$n/2$和$n%2$的最终结果只有0，-1，1三种，所以只考虑这三种base case.

public double myPow(double x, int n) {
    if (n == 0) return 1;
    if (n == 1) return x;
    if (n == -1) return 1.0 / x;
    double y = myPow(x, n / 2);
    return y * y * myPow(x, n % 2);
}

下面用位操作来计算。考虑$n$的二进制表示. 例如, 如果$n$是 "10001011", 则 $x^n = x^{1+2+8+128} = x^{1} \times x^{2} \times x^{8} \times x^{128}$. 因此, 我们不用循环$n$次来计算$x^n$. 为了加快计算, 我们遍历$n$中的每一位, 如果第$i$位是1, 我们把结果乘以$x^{2^i} = x^{(1 << i)}$. 既然 $(1 << i)$是2的指数, $x^{(1<<(i+1))}$ = square($x^{(1<<i)}$). 这个循环最多执行$\log(n)$次, i.e.$n$的二进制表示中最多有$\log(n)-1$位1).

public double myPow(double x, int n) {
    if (n == 0) return 1;
    if (n == 1) return x;
    if (n < 0) {
        // 不能直接 n = -n, 当n = -2147483648
        if (n == Integer.MIN_VALUE) {
            return 1 / myPow(x, Integer.MAX_VALUE) / x;
        } else {
            x = 1.0/x;
            n = -n; //防止溢出
        }
    }

    double res = 1;
    while (n > 0) {
        // n的第i位是1
        if ((n & 1) > 0)
            // res *= x^(1 << i)
            res *= x;
        // n 右移一位
        n >>= 1;
        x = x*x;
    }
    return res;
}