快速幂
顾名思义，快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高。

问题引入：如何最快的算出 8^45 ？
用最常规的方法，也就是 8×8×......×8×8 需要进行44次运算，显然是非常慢的，那么如何更快呢？
我刚开始想到用二分法来算，这种方法的确可以减少一些运算次数，但显然还不够。
我们需要的是：快速幂
快速幂的核心思想是将指数转为二进制数，然后根据基础的数学知识进行化简，得到最终的结果。
如刚才所说的 8^45 ，按照快速幂算法，将指数 45 转换为 101101 ，根据二进制的知识：

45 = 2^5 * 1 +2^4 * 0 + 2^3 * 1 + 2^2 * 1 + 2^1 * 0 + 2^0 * 1

而数学基础知识告诉我们：a^(b+c) = a^b * a^c
所以

8^45 = 8^(2^5 * 1 +2^4 * 0 + 2^3 * 1 + 2^2 * 1 + 2^1 * 0 + 2^0 * 1)
     = 8^(2^5 * 1) * 8^(2^4 * 0) * 8^(2^3 * 1) * 8^(2^2 * 1) + 8^(2^1 * 0) * 8^(2^0 * 1) 
     = 8^(2^5) * 8^(2^3) * 8^(2^2) * 8^(2^0) 

而另一个数学基础知识告诉我们：a^(2^i) = {a^[2^(i-1)]}^2

所以

8^(2^2) = 8^2 * 8^2
8^(2^3) = 8^(2^2) * 8^(2^2)
8^(2^4) = 8^(2^3) * 8^(2^3)
8^(2^5) = 8^(2^4) * 8^(2^4)

于是总结得：

总共进行6次运算，极大的缩减了运算量，提高运算速度。

知道思路后，再从代码层面实现一下。从代码层面实现还需要学习一种运算：位运算
我们知道程序中的所有数在计算机内存中都是以二进制的形式储存的，位运算就是直接对二进制数进行操作。符号是 >> 和 << 。
比如我们刚才说的 45 ，它是一个 int ，那么它在计算机中的储存形式就是：

00000000 00000000 00000000 00101101

把 45 >> 1 就是把这个二进制 int 右移 1 ，最高位用符号位补齐（这是算术右移，如果是逻辑右移，则用0补齐）得到

00000000 00000000 00000000 00010110

知道位运算之后，还需要知道一个布尔运算符：&
& 的中文名称叫做合取，合取中，有一个值为 false ，则合取结果为 false ，如：

1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0

所以，如何取到一个二进制数的最低位呢？答案很简单： b & 1 即可
为什么呢？
就以45的二进制数 101101 为例，合取 1 ，实际上是：

00000000 00000000 00000000 00101101 
&
00000000 00000000 00000000 00000001

自然就会发现输出的只能是 1 或 0 咯，由最后一位合取 1 来决定，最后一位为 1 则输出 1 ，为 0 则输出 0

这些东西都学习之后，就可以从代码层面实现快速幂啦！
JAVA 实现如下：

public static int power(int a, int b) {
        int ans = 1;
        while (b > 0) {
            if ((b & 1) == 1) {
                ans = ans * a;
            }
            a = a * a;
            b >>= 1;
        }
        return ans;
    }

如果是一个超出 int 承受范围的数怎么办呢？比如上文提到的 8^45
那么只需要使用 JAVA 的 Math 库里的 BigInteger 即可，同样我也实现了一遍：

public static BigInteger power(int a, int b) {
        BigInteger ans = new BigInteger("1");
        BigInteger biga = BigInteger.valueOf(a);
        while (b > 0) {
            if ((b & 1) == 1) {
                ans = ans.multiply(biga);
            }
            biga = biga.multiply(biga);
            b >>= 1;
        }
        return ans;
    }

试运行一下上文提到的 8^45 吧：

运行起来也是非常正常，这个数肯定是爆 long 了，必须要用 BigInteger 来实现
结语：
快速幂只是一个非常基础的算法，主要是为了之后学习快速幂取余做一个小小的铺垫，过几天会写一篇快速幂取余的博文~（咕咕咕

转载本博客所有内容均需遵守《知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议》，详细信息访问本博客的关于页面查看