例：求$a^b$的值，$0<=a,b<=2^{31}$;

快速幂原理：

(1)如果将$a$自乘一次，就会变成$a^2$。再把$a^2$自乘一次就会变成。然后是$a^8$ ……自乘$n$次的结果是$a^{2^n}$。

(2)$a^x+a^y=a^{x+y}$

(3)将$b$转化为二进制：比如$b=(11)_{10}$，转换为二进制就是$(1011)_2$。从左到右，这些1分别代表十进制的8,2,1。可以把快速幂理解成模拟这个过程。

快速幂可以把原本要算b次的方法，缩减成$log_2(b)$次。

代码：

int quickPower(int a, int b){//是求a的b次方
	int ans=1,base=a;//ans为答案，base为a^(2^n)
	while(b>0){//b是一个变化的二进制数，如果还没有用完
		if(b&1)//&是位运算，b&1表示b在二进制下最后一位是不是1，如果是：
		ans*=base;//把ans乘上对应的a^(2^n)
		base*=base;//base自乘，由a^(2^n)变成a^(2^(n+1))
		b>>=1;//位运算，b右移一位，如101变成10（把最右边的1移掉了），10010变成1001。现在b在二进制下最后一位是刚刚的倒数第二位。结合上面b & 1食用更佳
	}
	return ans;
}