【leetcode】快速幂

问题：

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

示例 1:

输入: 2.00000, 10
输出: 1024.00000
示例 2:

输入: 2.10000, 3
输出: 9.26100
示例 3:

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

解决方法：

这道题需要使用快速幂求解，时间复杂度为 O( $\log_{2} (n)$ ) 。

如果我们按照常规思路，令 $x = x * x$ ，重复 $n$ 次，时间复杂度为 O( $n$ )，会超时。

快速幂是将 $n$ 变成二进制数，如 $n = 9 = (1001)$ ，求解 $2$ 的 $9$ 次方就变成：

$2^{9} = 2^{2^{0} \times 1 + 2^{1} \times 0 + 2^{2} \times 0 + 2^{3} \times 1} = 2^{2^{0} \times 1} \times 2^{2^{1} \times 0} \times 2^{2^{2} \times 0} \times 2^{2^{3} \times 1} = 2^{2^{0} \times 1} \times 1 \times 1 \times 2^{2^{3} \times 1} = 2^{2^{0}} \times 2^{2^{3}}$

由此可见，我们只需要将 $n$ 二进制数位上为 $1$ 对应的数相乘即可。至于这些数是怎么来的，是按照 $x = x \times x$ 依次得到：

$x = 2 \Rightarrow 2^{2^{0}}$

$x = x \times x = 4 \Rightarrow 2^{2^{1}}$

$x = x \times x = 16 \Rightarrow 2^{2^{2}}$

$x = x \times x = 16 \times 16 \Rightarrow 2^{2^{3}}$

我们依次得到对应的 $x$ ，然后当 $x$ 对应 $n$ 的二进制数位是 $1$ 时 $r e s u l t = r e s u l t \times x$ 。在循环的过程中，我们通过 n & 1来判断 $x$ 对应 $n$ 的二进制数位， n >>= 1, x = x * x 对应着下次循环中的 $x$ 和 $n$ 。

当 $n$ 小于 $0$ 时，我们令 $x = \frac{1}{x}$ , $n = - n$ . 代码如下

Python

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0: return 0
        if n == 0: return 1
        if n < 0:
            n = -n
            x = 1/x
        ans  = 1
        while n > 0:
            if n & 1 == 1: ans *= x
            x *= x
            n >>= 1
        return ans

C++

class Solution {
public:
    double myPow(double x, int n) {
        if (x==0) return 0;
        if (n==0) return 1;
        long pow  = n;
        if (pow < 0){
            x = 1/x;
            pow = -pow;
        }
        double ans = 1;
        while (pow > 0){
            if (pow&1 == 1) ans *= x;
            x *= x;
            pow >>= 1;
        } 
        return ans;
    }
};