【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\times1+2^1\times0+2^2\times0+2^3\times1}= 2^{2^0\times1}\times2^{2^1\times0}\times2^{2^2\times0}\times2^{2^3\times1} = 2^{2^0\times1}\times1\times1\times2^{2^3\times1} = 2^{2^0}\times2^{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$ 时 $result = result \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;
    }
};