快速幂运算

直接举例说明！计算2^9,从9的二进制1001可以将式子化简为2^9 = 2^8 * 2^1，我们按照这个思路进行计算。也就是说我们每一次都计算并保存2^x，这个x的取值为1,2,4,8……，然后我们的答案ans每次都判断是否乘上这个数。第一次运算2^1,而9的二进制1001最后一位为1，所以ans * 2^1；第二、三次运算2^2、2^3, 1001的倒数第二、三位为0，所以直接跳过；第四次运算2^4，1001的倒数第四位（第一位）为1，ans * 2^4,得到最终答案。正常的幂运算需要计算9次，而快速幂运算只需要计算4次，当幂越大，差距越明显。（幂为64时，只需要计算6次）

c++

//base 表示底数，k 表示幂，mod 表示模
int quick_pow(int base, int k, int mod) {
    int ans = 1;
    while(k) {
        if(k & 1)//用位运算与判断k二进制最后一位是否为1，为1时才计算ans
            ans = ans * base % mod;
        base = base * base % MOD;//base每次都运算    
        k >>= 1;//相当于k /= 2, 移位运算效率较高
    }
    return ans;
}