快速幂

快速幂，就是幂运算的一种快速算法，它的时间复杂度为，相较于传统计算方式的有很大的提升。 在了解快速幂之前，我们需要先了解一下传说中的二进制。

浅谈二进制

要知道，这个世界上只有10种人，一种是懂二进制的人，另一种是不懂二进制的人。（滑稽） 相对于十进制， 我们生活中所用的是十进制，满十进一。那么二进制，顾名思义，就是满二进一。 就像上上段的那个笑话一样，10（读作：一零）它其实是2，依此类推，100它是4,1000它是8,10000它就是16，而1它还是1。 看着上面的二进制与十进制的对照我们可以发现，二进制的第i位它其实对应的就是十进制中的。

如何快速幂

当我们知道了二进制的第i位它其实对应的就是之后，我们就可以开始快速幂的运算了。 下面以为例。 首先我们要把x转换为二进制数。 例如,11的二进制是1011，根据前文提到的二进制与十进制的对应关系可得。 化简可得 根据以上的证明，再加上c++中的位运算符我们就可以以一种很简洁的代码完成快速幂。

位运算

&与运算，它是一个二元运算符，只有当两个输入的条件都为真，在二进制中也就是都为1的时候才返回真（对应二进制中的1）。 利用这个特性，我们可以判断一个整数的奇偶性。比如9和1，1001和0001分别对应9和1的二进制，当他们进行与运算之后的结果显然为0001，返回真，表示9是一个奇数。显然，奇数二进制的最后一位都是1，偶数二进制的最后一位都是0，把它们同1进行与运算就能判断它们的奇偶性。   >>i右移运算，注意与cin输入的>>重载运算符区别！！！，它的含义是小数点不动，在二进制下将数整体右移i位。 利用这个运算符，我们就可以用“>>1”实现去掉某个二进制数的最后一位。

---

这时，我们再联系上前文所提到的知识，就可以写出下面函数来进行幂运算： int pow(int a,int x) { int r=1; while(x) { if(x&1) r*=a; a*=a; x>>=1; } return r; }

在快速幂中进行取模运算

在一些题目，我们通常要对一些数据较大的结果进行取模运算。但是如果数据过大的话，就会超过变量的储存范围。但是我们根据下面一个公式就可以很好的解决这个问题。 公式： 显然，这个公式是成立的（手动滑稽），咳。 根据上面的公式我们可以得出 于是乎我们就可以针对上面的代码进行优化，如下： int pow(int a,int x,int c) { int r=1; while(x) { if(x&1) r=r*a%c; a=a*a%c; x>>=1; } return r; }  

以上均属个人现阶段的观点，本人是蒟蒻一枚，水平有限，如有不足请各位神犇指出。

版权申明：欢迎转载，转载请注明出处！