学习一波 快速幂

背景

计算类似于 \(a^n\) 这样的式子的时候，如果采用循环将n个a乘起来，这样的时间复杂度将会是O(n)，然而当a, n太大的时侯，这种方法就不太适用了。

但是呢，我们可以知道\(a^{b+c} = a^b \times a^c\)，\(a^{2b} = a^b \times a^b = (a^b)^2\)。快速幂的思想就是将取幂的过程按照指数的二进制表示来分割成更小的任务。

也可以通过二分的角度理解，可以看参考文章。

简介

快速幂，二进制取幂（Binary Exponentiation，也称平方法），是一个在 O(logn)的时间内计算\(a^n\)的小技巧，而暴力的计算需要O(n)的时间。

实现

首先我们需要将n表示为2进制，举一个例子：

\(5^{13} = 5^{(1101)_2} = 5^8 \times 5^4 \times 5^1\)

n有\(\lfloor log_2n \rfloor + 1\)个二进制位，因此当得到了\(a^1, a^2, a^4, ... , a^{2\lfloor log_2n\rfloor}\)之后，就可以计算O(logn)次乘法就可以计算出\(a^n\)。

由此对于任何十进制正整数n，假设其二进制为 \(b_m...b_3b_2b_1\)（\(b_i\)为二进制某一位的值），则可以推导出：

二进制 => 十进制：\(n = 1b_1 + 2b_2 + 4b_3 + ... + 2^{m-1}b_m\)
幂的二进制展开：\(a^n = a^{1b_1 + 2b_2 + 4b_3 + ... + 2^{m-1}b_m} = a^{1b_1}a^{2b_2}a^{4b_3}...a^{2^{m-1}b_m}\)

根据上述的推导，可以把计算\(a^n\)转化为下面两个问题：

计算\(a^1, a^2, a^4, ... , a^{2^{m-1}}\)的值，这一步只需要循环赋值操作 \(a = a^2\)即可
获取二进制各个位\(b_m,...,b_3,b_2,b_1\)的值，这一步需要循环执行下述操作：
1. n&1：判断n的二进制最右一位是否为1
2. n>>1：n右移一位，即删除最右一位

=> 因此，执行上述操作，可以在循环中依次计算\(a^{2^0b_1},a^{2^1b_2},...,a^{2^{m-1}b_m}\)的值，并将所有的\(a^{2^{i-1}b_i}\)累计相乘即可，其中：

\(a^{2^{i-1}b_i} = \begin{cases} 1, & b_i = 0 \\ a^{2^{i-1}}, & b_i = 1 \end{cases}\)

代码实现

Java 模板
Python 模板

public double binpow(double a, int n) {
    double res = 1.0;
    while(n > 0) {
        if((n & 1) == 1) res *= a;
        a *= a;
        n >>= 1;
    }
    return res;
}

def bin_pow(a: float, n: int) -> float:
    res = 1.0
    while n:
        if n & 1:
            res *= a
        a *= a
        n >>= 1
    return res

实战

50. Pow(x, n)

Java
Python

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

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

https://leetcode.cn/problems/powx-n/solutions/241471/50-powx-n-kuai-su-mi-qing-xi-tu-jie-by-jyd/
https://oi-wiki.org/math/binary-exponentiation

youyichannel

学习一波快速幂

背景

简介

实现

实战