位运算技巧

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