快速乘与快速幂

介绍

累加器是CPU中独立的寄存器，运算速度非常快。因此，乘法如果能表示成加法，也会大大提高执行效率。"快速乘"算法，就是这种通过加法来模拟乘法运算。

快速幂背景相似，2^4幂运算执行了4次乘法运算，我们希望通过"快速幂"算法，把乘法运算缩减到lg(n)次

代码与原理

def quick_multi(a, b):
    """
    快速乘
    b用二进制表示 使用乘法分配率 
    2*5 = 2*(101)2 = 2^3 * 1 + 2^2 * 0 + 2^1 * 1
    """
    result = 0
    while b:
        if b & 1:
            result += a
        a += a
        b >>= 1
    return result


def quick_power(a, b):
    """
    快速幂
    b用二进制表示 使用幂的运算规则
    2^5 = 2^(101)2 = (2^1 * 1) * (2^4 * 1)
    (2^1 * 1) 
    (2^2 * 0)
    (2^4 * 1)
    """
    result = 1
    while b:
        if b & 1:
            result *= a
        a *= a
        b >>= 1
    return result