快速幂算法

快速幂是一种简单而有效的小算法，它可以以$O(logn)$的时间复杂度计算幂。

以$6^5$为例，我们将幂转换为二进制$(101{)}_2$，$6^5=6^{(101{)}_2}$。

所以我们只需看101中的每一个1都代表是多少即可。

• 我们首先看最后一个1，表示$6^1$;
• 中间的0，如果这里是个1则表示$6^2$,上一位表示数值的平方，即$(6^1{)}^2$
• 第一个1，表示$6^4$，也就是上一位表示数值的平方，即$(6^2{)}^2$

知道了每一位代表多少数值，然后我们将上述结果相乘即可。

现在就有2个问题摆在面前，

1. 我们怎么区分当前位是0还是1呢？
2. 我们怎么获取每一位的数值呢？

为了解决上述问题，对于幂101，可以使用这样一套操作：

1. 与1进行按位与& ，即$101\&1=101\&001=001$，说明最后一位是1
2. 然后幂 右移1，即$101>>1=010$;
3. 按位与，$010\&1=010\&001=000$，说明第二位是0；
4. 右移1，$010>>1=001$;
5. 按位与；$001\&1=001\&001=001$，说明第一位是1；

至此全部问题都解决了，代码如下：

def fastPower(base, n):
    # &按位与运算，举例101&011= 001,就是在二进制下，都是1才是1
    ans = 1

    while n:
        if n & 1:
            ans *= base
        base *= base  # 平方
        n >>= 1

    return ans
1
2
3
4
5
6
7
8
9
10
11