介紹
累加器是CPU中獨(dú)立的寄存器，運(yùn)算速度非臣鞠＃快褪那。因此幽纷，乘法如果能表示成加法，也會(huì)大大提高執(zhí)行效率博敬。"快速乘"算法友浸，就是這種通過(guò)加法來(lái)模擬乘法運(yùn)算。
快速冪背景相似偏窝，2^4冪運(yùn)算執(zhí)行了4次乘法運(yùn)算收恢，我們希望通過(guò)"快速冪"算法，把乘法運(yùn)算縮減到lg(n)次
代碼與原理
def quick_multi(a, b):
"""
快速乘
b用二進(jìn)制表示 使用乘法分配率
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用二進(jìn)制表示 使用冪的運(yùn)算規(guī)則
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
