快速幂

快速幂用于加快幂运算的速度。计算 \( a^n \)，如果直接循环做 n 次乘法，需要的时间复杂度是 \( O(n) \)，而快速幂可以把这个时间复杂度降低为 \( O(\log n) \)。

基本思路其实是把 n 拆分成 2 的幂次方。

比如要计算 \( a^{11} \)，11 的二进制是 1011，也就是：\( 11 = 2^0 + 2^1 + 2^3 \)，

那么 \( a^{11} = a^{2^0} \times a^{2^1} \times a^{2^3} \)，

只要从低位开始逐位运算就可以了：

int poww(int base, int index)
{
    int result = 1;
    while (index) {
        if (index & 1) {
            result *= base;
        }
        base *= base;
        index >>= 1;
    }
    return result;
}

代码里用到了一些技巧：

1. 从低位开始处理，每次处理完一位就右移一次。这样每次都只要处理最低位。
2. base *= base 的目的是每次右移一位，相当于指数除以 2，那么基数就要取平方。即 \( base^{index} = {(base^2)}^{index / 2} \)