快速幂是利用二进制的特性来求一个数的N次方的算法

比如一个数 5^18
正常来说 要算18个5相乘
但是我们看看18这个数写成2进制10010
那我们可以把5^18看成

int quick_pow(int a, int b) {
	int ans = 1;
	int base = a;
	while (b) {
		if (b & 1) {
			ans *= base;
		}
		base *= base;
		b >>= 1;
	}
	return ans;
}

看下代码 base是5 如果18的二进制的最后一位是1 那么ans就变第一次变化是ans=1*25
第二变化是
ans=25*5^16
你看 是不是运算次数少了很多