快速幂算法

快速幂就是快速算底数的 n n n 次幂，是一种简单而有效的算法，它的时间复杂度为 O ( log ⁡ 2 n ) O(\log_2 n) O(log2​n)，与一般的幂运算的 O ( n ) O(n) O(n) 的时间复杂度相比效率有极大的提高，它的基本原理是二进制。
一般地，对于任何一个整数 n n n，都能用二进制来表示。那么对于 a n a^n an， n n n 一定可以用二进制表示。
例如 a 156 a^{156} a156，而 15 6 ( 10 ) = 1001110 0 ( 2 ) 156_{(10)}=10011100_{(2)} 156(10)​=10011100(2)​。
于是，
a 156 = a 10011100 = a 2 7 ∗ 1 + 2 6 ∗ 0 + 2 5 ∗ 0 + 2 4 ∗ 1 + 2 3 ∗ 1 + 2 2 ∗ 1 + 2 1 ∗ 0 + 2 0 ∗ 0 = ( a 2 7 ∗ 1 ) ∗ ( a 2 6 ∗ 0 ) ∗ ( a 2 5 ∗ 0 ) ∗ ( a 2 4 ∗ 1 ) ∗ ( a 2 3 ∗ 1 ) ∗ ( a 2 2 ∗ 1 ) ∗ ( a 2 1 ∗ 0 ) ∗ ( a 2 0 ∗ 0 ) \begin{aligned} a^{156}&=a^{10011100} \ &= a^{2^{7}*1+2^{6}*0+2^{5}*0+2^{4}*1+2^{3}*1+2^{2}*1+2^{1}*0+2^{0}*0} \ &=(a^{2^{7}}*1)*(a^{2^{6}}*0)*(a^{2^{5}}*0)*(a^{2^{4}}*1)*(a^{2^{3}}*1)*(a^{2^{2}}*1)*(a^{2^{1}}*0)*(a^{2^{0}}*0) \end{aligned} a156​=a10011100=a27∗1+26∗0+25∗0+24∗1+23∗1+22∗1+21∗0+20∗0=(a27∗1)∗(a26∗0)∗(a25∗0)∗(a24∗1)∗(a23∗1)∗(a22∗1)∗(a21∗0)∗(a20∗0)​
按照以上这个式子来求解 a 156 a^{156} a156，原来要进行 156 − 1 = 155 156-1=155 156−1=155 次乘法运算，现在的运算次数是 n n n 的二进制的长度 * 二进制中 1 1 1 的个数 = 8 ∗ 4 = 24 =8*4=24 =8∗4=24 次。
下面是快速幂的 Java 实现：

//快速幂
public int quickPow(int a, int n) {
    int ans = 1;
    while (n > 0) {
    	// 如果 n 的当前末位为 1
        if ((n & 1) == 1) {
        	// ans 乘上当前的 a
            ans *= a;  
        }
        // a 自乘
        a *= a;
        // n 往右移一位,表示除以 2
        n >>= 1; 
    }
    return ans;
}

参考