m的n次方

      如果让你求解 2 的 n 次方，并且不能使用系统自带的 pow 函数，你会怎么做呢？这还不简单，连续让 n 个 m 相乘就行了，代码如下：

int pow(int n)
{
	int tmp = 1;
	for (int i = 1; i <= n; i++)
	{
		tmp = tmp * m;
	}
	return tmp;
}

      不过你要是这样做的话，我只能呵呵，时间复杂度为 O(n) 了，怕是小学生都会！如果让你用位运算来做，你会怎么做呢？
      我举个例子吧，例如 n = 13，则 n 的二进制表示为 1101, 那么 m 的 13 次方可以拆解为:
      m^1101 = m^0001 * m^0100 * m^1000。
      我们可以通过 & 1和 >>1 来逐位读取 1101，为1时将该位代表的乘数累乘到最终结果。直接看代码吧，反而容易理解：

int pow(int n)
{
	int sum = 1; 
	int tmp = m;
	while (n != 0)
	{
		if (n & 1 == 1)
		{
			sum *= tmp;
		}
		tmp *= tmp; 
		n = n >> 1; 
	} 
	return sum; 
}

      时间复杂度近为 O(logn)，而且看起来很牛逼。
注意：这里说一下，位运算很多情况下都是很二进制扯上关系的，所以我们要判断是否是否位运算，很多情况下都会把他们拆分成二进制，然后观察特性，或者就是利用与，或，异或的特性来观察，总之，我觉得多看一些例子，加上自己多动手，就比较容易上手了。