幂运算是非常常见的一种运算,求最容易想到的方法便是通过循环逐个累乘,其复杂度为
,这在很多时候是不够的,所以我们需要一种算法来优化幂运算的过程
快速幂这个东西比较好理解,今天把它系统的总结一下防止忘记.
首先,快速幂的目的就是做到快速求幂,假设我们要求,按照朴素算法就是把a连乘b次,这样一来时间复杂度是
,即是
级别,快速幂能做到
,快了好多好多.
它的原理如下:
假设我们要求,将
写为二进制的形式,该二进制数第
位的权为
.
e.g. 时,
11的二进制是1011,,因此,我们将
转化为算
,也就是
.原来算11次,现在算三次,但是这三项貌似不好求.
不急,下面会有详细解释.
由于是二进制,很自然地想到用位运算这个强大的工具:&(按位与)和>>(右移运算符). &运算通常用于二进制取位操作,例如一个数& 1 的结果就是取二进制的最末位。还可以判断奇偶,e.g.
&1==0为偶,
&1==1为奇。 >>
运算比较单纯,将数字写成二进制形式,右移
位,即将二进制数去掉最后
位.
int binaryPow(int a, int b) { int ans = 1, base = a; while (b != 0) { if (b & 1 != 0) ans *= base; base *= base; b >>= 1; } return ans; }
代码很短,也很好理解,以为例,
,二进制从右向左算,但乘出来的顺序是
,是从左向右的.我们不断的让
目的即是累乘,以便随时对
做出贡献.
其中要理解这一步:因为
,下一步再乘,就是
,然后同理
,由此可以做到
指数正是
,再看上面的例子,
,这三项就可以完美解决了.
如果需要取模的话,直接在每一步运算中对base和ans取模即可.
我居然看懂啦~!给可爱的小黑特送小花花 ❀.(*´▽`*)❀.~~