取模运算的运算法则

1. (a + b) % p = (a % p + b % p) % p （1）
2. (a - b) % p = (a % p - b % p ) % p （2）
3. (a * b) % p = (a % p * b % p) % p （3）

背景：

求一个数的指数，如果指数很大，根据”指数爆炸递增“的常识，计算结果会造成内存溢出

比如，求2的10000此方结果的最后三位，如果直接循环乘，一定会造成内存溢出

根据取模运算的运算法则，可以对每一次循环的结果取模，返回结果取模

问题思考：

该算法的时间复杂度是O(1)，如果求2的1000000000次方，用时可能较长，写一个程序来测试一下算出结果到底用时多少

最后结果为17.61，将近18秒，18秒才算出结果，该算法无法投入实际中使用

快速幂算法初步

如果求指数很大的幂，快速幂算法可以很快的求出结果

例如我们求3的十次方

如果用循环，需要十次运算

我们可以对3的十次方进行拆分，将3的十次方拆分为3*3的5次方，那么这样我们只需要多一次乘法，就可以减少一半的循环次数，如果指数比较大，减少一半的循环次数节约的时间很多

同理，我们可以对9的5次方再进行拆分，因为5是计数，我们无法对它进行折半拆分，这时可以先分出一个9，变为9*9^4，再对9的4次方进行拆分

最后拆分为

最后，我们的算式其实就变为

最后求出的幂结果实际上就是在变化过程中所有当指数为奇数时底数的乘积。

代码

用这个算法对上述的数据运算，时间为0.002秒，时间节约很大

快速幂算法”压榨性能优化“

可见上述代码有重复操作

且根据整数除法，奇数/2会向下取整

优化后算法

位运算继续优化

判断奇偶，因为二进制奇数最后一位为1，偶数最后一位为0，所以可以用该数&1是否为1判断是否为奇数

同理，除以2，也能用位运算向右移动一位来运算

代码