位运算技巧

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;
}

8.子集的异或总和再求和（给定一个数组，求数组每一个子集内所有元素异或结果的总和）

大小为n的集合共有2的n次个子集，n位二进制数可表示0 – 2的n次方-1种状态，刚好对应。对于｛x1,x2,x3｝,010表示｛x2｝,101表示{x1,x3}….
可遍历0 – 2的n次方-1来遍历所有集合，对每个集合，找到其为1的位并异或

(i & (1 << j)) != 0 检查i的第j位是否为1

class Solution 
{
    public int subsetXORSum(int[] nums) 
    {
        //0 - 2^n - 1枚举子集
        int ans = 0;
        for(int i = 0;i < (1 << nums.length);i++)
        {
            int sum = 0;
            for(int j = 0;j < nums.length;j++)
            {
                if((i & (1 << j)) != 0)
                    sum ^= nums[j];
            }
            ans += sum;
        }
        return ans;
    }
}

9.不用+/-实现a+b

异或可以等效于无进位的加法，而加法的进位可以看a & b 是否为0（只有11相与才会为1使结果不为0，其他使得结果为0的情况必没有进位）
因此结果 = 异或结果 + 进位 加完之后还要判断异或的结果和进位相加会不会有进位，如果有，要继续加
使用递归解决：

class Solution 
{
    public int getSum(int a, int b) 
    {
        return b == 0 ? a : getSum(a ^ b,(a & b) << 1);
    }
}

10.给定N，M，i，j，要求把N的二进制第i-j位替换为M

首先先将N的第i-j位替换为0，方法：依次将N与1111101111这样的子串相与（第i-j位依次为0，其余为1），依次将第i-j位变成0
使用取反简化操作：N & ~（1 << k）(i<=k<=j)
再将N与左移后的M进行或运算

for(int k = i;k <= j;k++)
{
  N &= ~(i << k);
}
return N | (M << i);