如何快速计算一个实数的整数次幂？

假如现在要计算7的13次方，应该怎么做？

朴素的做法是7连乘13次，得到的结果是96,889,010,407，这个过程做了13次乘法计算。

除了这种朴素做法之外，还有一种方法叫快速幂算法。

我们在小学时候就学过，a^m+n = a^m · aⁿ，(a^m)ⁿ = a^mn。而13的二进制形式是1101₂ = 8 + 4 + 1，由此可知，7¹³就等于7⁸⁺⁴⁺¹。所以我们只需要依次计算7¹、7²、7⁴、7⁸（每一项都是前一项的平方），然后根据指数的二进制位是否为0来决定是否把结果乘入到最后的计算结果中即可。

也就是：

   7¹³

= 7¹⁺⁴⁺⁸

= 1x7¹ * 1x7⁴ * 1x7⁸       # 7²对应的指数二进制位为0，不把它加入结果的计算中

= 1x7¹ * 1x(7²)² * 1x(7⁴)²   # 只需要计算前一项的平方

= 96,889,010,407

通过Python3实现就是：

def fast_pow(base, exp):
    result = 1
    while exp > 0:
        if exp & 1:          # 当前最低二进制位为 1
            result *= base
        base *= base         # 底数平方
        exp >>= 1            # 指数右移一位，即除以 2
    return result

和朴素幂运算的13次乘法比起来，快速幂只进行了4次平方和3次乘法，计算时会快很多。