众所周知，pow函数是最简单，也是效率最低的求幂函数。如果不对其进行相应的优化，很多算法题光是从运行时间上就无法通过。

我相信大家不是不想用更高效的求幂算法，但苦于不知道。那就不妨继续读下去，我来教大家一个更高效的求幂运算

让我们有请——快速幂！！！

假设我们求3的5次方，即底数是3，指数是5

首先，我们将5转化为二进制，即101

其次，按位将二进制的指数拆解，写成101=20+22

所以35=32的0次方+2的2次方=31*34

也就是说快速幂就是将指数转化为二进制，然后观察哪个位是1，二进制第一位是1就乘上1个底数，二进制第二位是1就乘上2个底数依次类推

所以对于35，将5转化为二进制101，那么最后的结果就是1（20）个3乘上4（22）个3

先上代码：

还是拿35举例

第6行中的if(b&1)是按位相与的意思，不知道&即按位相与是什么意思的同学可以先跳转到下面这篇文章学习一下再回来继续理解

还没搞懂&与&&在c语言中的区别？快点进来看看！

b&1j就是看最低位是否为1，如果是1就进行乘上对应权重个底数

而第7行base*=base;的意思就是使base与对应二进制的位数相匹配，即从右往左第一位是1个a，第二位是2个a，第3位是4个a

最后，第八行b>>=1;就是将指数b的二进制数向右移动1位，类似于求各位数字时n=n/10的操作

如果想更为详细地了解快速幂，可以参考这篇文章 https://blog.csdn.net/iwts_24/article/details/79780596