学步园

naive版的求幂函数很单纯，复杂度O(N)。

能否简化计算呢？我们来分析一哈~

求m^n，假设 n = 13。n表示成2进制为1101，即13 = 1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0

m ^ n = m ^ (8 + 4 + 1) = m ^ 8 * m ^ 4 * m^ 1

here it is ！

m^n可以拆分成最多log(n)个数相乘，且这些数的关系为：相邻两数前者是后者的平方。

且由于每次res去乘以的数(如果该位为0则不乘)都是上一次那个数的平方， 所以，这个数我用完一次，

就对它取平方，准备下一次的使用即可。

code如下：

int myPow(int m, int n)
{
	int res = 1;
	while(n)
	{
		if(n & 1)
			res *= m;
		m *= m;
		n >>= 1;
	}
	return res;
}