位运算技巧

1.求一个数是否是2的幂

一个数是2的幂，其二进制必定为1000（若干个0，1个1）的形式，将其减一即为0111，相与必为0

判断n是否是2的幂，只需要判断n > 0 以及n & n - 1是否为0

2.求一个数是否是4的幂

4的幂一定是2的幂，2的幂不一定是4的幂

2的偶数次幂模3为1，奇数次幂模3为2，即4的幂模3为1

判断n是否是4的幂，只需要判断n是否是2的幂且模3为1 n > 0 && n & (n - 1) == 0 && n % 3 == 1

3.求一个数中位1的个数

如果某个数表示成...1000的形式，这里展示的是其最低位的1，只需要与n - 1相与，即可消除掉最低位的1

在n > 0的条件下不断将n & n - 1，记录消除1的次数即可

4.不用临时变量交换两数

任何数和0异或结果为其本身，任何数和自身异或结果必定为0。
异或满足交换律和结合律

5.寻找只出现1次的数字

在数组中除了一个数，其他的数都出现两次，找这个数

将所有的数异或，出现两次的数两两异或为0，最终剩只出现一次的数与0异或，结果为其本身

6.汉明距离

汉明距离：求两个数中对应二进制位不相同的数目

两个数异或，其二进制位不同的位置必定为1，因此问题转换为求两数异或的结果中位1的个数，与第3题相同

7.判断一个数二进制是不是由交替的01组成（不能出现00或11）

任何数与全1相与值为本身，对于每两位与11（十进制为3）相与进行检查，出现00或11则为false

while(n)
{
if((n & 3) == 0 || (n & 3) == 3)
  return false;
n >>= 1;
}