Fork me on GitHub

算法里面快速幂的操作

做个记录,防止以后忘记。这玩意儿挺好用的。(逃

首先,介绍一下快速幂吧。正如其名字所表示的含义一样。快速幂的目的就是让我们做到快速求出某个数的幂次。

比如我们要求的是a^b,如果按照最正常的计算方法。就相当于要把a相互乘,乘b次就可以出来我们的结果。可这样一来如果遇见大的数字很容易会出现时间复杂度GG。要花费很多时间。这个时候快速幂能把这个变快好多好多。

举个例子而言 假设我们计算a^b,那么我们可以利用程序里面的位运算符号来把,b拆分成一个二进制数,for instance,b==11的话。那么11拆成二进制就是1011,11=2^31+2^20+2^11+2^0+1,那么a的11次方就被我们转换成a^1a^2*a^8。可以看出以前要计算11次的,但现在却只用计算三次就OK了。那么怎么求这三项?后面将会带来讲解。

由于是二进制运算,我们很自然而言的想到要用 位运算操作:&和>>

to be continued…..

-------------本文结束感谢您的阅读-------------