[C++知识库]C语言用位运算提高效率的一些方法

NO.1 判断一个数是否为2的正整数次幂

由于2的正整数次幂的二进制数是由1后面加若干个0；将其减一后就是把原来的1变成0，1后面的0全都变成1，因此将n和n-1相&，结果全都是0，对应十进制数0.

bool IsPowerOfTwo(int n){
  return (n>0)&&(n&(n-1)==0);
}

NO.2一个数乘2的正整数次幂

由于一个数乘2的n次幂等同于把该数每位的权值增加n，因此可以使用左移运算

int mulPowerOfTwo(int n,int m){
  return n<<m;
}

NO.3一个数除以2的正整数次幂

对应于NO.2，一个数除以2的n次幂等同于把该数每位的权值减去n，因此可以使用右移运算

int divPowerOfTwo(int n,int m){
  return n>>m;
}

NO.4一个数对2的非负整数次幂求模

2的非负整数次幂由1和若干个0构成，例如1000，一个数对其求模，就是要求整除1000后的余数，

因此结果必定是在0000到0111之间，由于2的n次方的特殊性，减一之后就变成了0111，后三位111就是要找的余数位；因此将1000减去1之后，再与原先那个数相&，就得到了那个数的最后三位，这就是我们要求的模。

int modPowerOfTwo(int n,int m){
  return n&(m-1);
}

总结：位运算对于初学者经常是一个盲点，合理地使用位运算，可以简化算术运算中较为复杂的问题。