Binary Expansion

快速幂算法的原理及实现

先放代码实现

public int pow(int a, int b) {
    int res = 1;
    while (b > 0) {
        if (b & 1 == 1) {
            res *= a;
        }
        a *= a;
        b >>= 1;
    }
    return res;
}

快速幂算法的原理是通过将指数拆分成几个因数相乘的形式，来简化幂运算。在我们计算$3^{13}$的时候，普通的幂运算算法需要计算13次，但是如果我们将它拆分成$3^{8+4+1}$，再进一步拆分成 $3^{8}*3^{4}*3^{1}$只需要计算4次。嗯？哪来的4次？，别急，接着看。

这种拆分思想其实就是借鉴了二进制与十进制转换的算法思想，我们知道13的二进制是1101，可以知道：

$13 = 1 * 2^{3} + 1 * 2^{2} + 0 * 2^{1} + 1 * 2^{0} = 8 + 4 + 1$

实现的代码已经给出，原理就是利用位运算里的位移>>和按位与&运算，代码中b & 1其实就是取b二进制的最低位，用来判断最低位是0还是1，再根据是0还是1决定乘不乘，不理解的话联系一下二进制转换的过程。b >>= 1其实就是将b的二进制向右移动一位，就这样位移、取最低位、位移、取最低位，这样循环计算，直到指数b为0为止，整个过程和我们手动将二进制转换成十进制是非常相似的。普通幂算法是需要循环指数次，也就是指数是多少就要循环计算多少次，而快速幂因为利用了位移运算，只需要算“指数二进制位的位数”次，对于13来说，二进制是1101，有4位，就只需要计算4次，快速幂算法时间复杂度是O(logn)级别，对于普通幂需要计算一百万次的$10^{10^{6}}$来说，快速幂只需要计算6次，这是速度上质的飞跃，但是需要多注意溢出的问题。

转载: 快速幂算法的原理及实现