1.位运算常见技巧总结

1.n&(n-1) 将n的最低位 1置0。例如:11011000&1010111=11010000

2.获取二进制中最右边的1，且其它位置为0: n & (-n) 。例如:n=01011000，-n=11011000(原)=10100111(反)=10101000(补)

n&(-n)=01011000&10101000=00001000，相当于提取了最右边的1其余位为0（树状数组会用到）

3.任何数和0做异或运算，结果仍然是原来的数，即 a^0=a。 例如:11011000^00000000=11011000

4.任何数和其自身做异或运算，结果是 0，即 a^a=0。例如:11011000^11011000=00000000

5.异或运算满足交换律和结合律，a^b^a=b^a^a=b^(a^a)=b^0=b

6.将某一位0或1取反：x^1=~x，例如：0^1=1，1^1=0

7.Integer.numberOfTrailingZeros(int i) 返回指定int值的二进制补码二进制表示形式中最低位1之后的0的数目。

8.Integer.numberOfLeadingZeros(int i) 返回这个数据的二进制串中从最左边算起连续的“0”的总数量。因为int类型的数据长度为32所以高位不足的地方会以“0”填充。

Integer.numberOfTrailingZeros(10); // 10=1010(2) -> 输出结果为1(最低位1尾随0个数) Integer.numberOfLeadingZeros(2); // 2=10(2) -> 输出结果为30(不足前面补0) // 那么求二级制表示一共有多少位就有一个技巧 32 - Integer.numberOfLeadingZeros(2); // 返回2

详细参考：位运算操作常见技巧

2.位运算题目的常见出题形式

LC2135. 统计追加字母可以获得的单词数

总体方法：位运算掩膜计数+HashMap(数组)+HashSet
1.我们要求的是targetWords中能够由startWords转化过来的数目，那么以targetWords为主体进行求解会比较简单
2.我们都知道startWords只能追加一个字母变成targetWords，那么我们可以以字符串长度分组进行计算
3.假设targetWords[i]的长度为len，那么只有可能从长度为len-1的startWords[j]转换过来
4.我们可以枚举每个targetWords[i]，再枚举某个targetWords[i]中可删除的字母，每当删除一个字母后假若在长度为len-1的startWords[j]中找到相同掩膜的说明这个targetWords[i]可以完成转换，res++然后直接下一个；当枚举完后都不能转换就说明不能完成转换
5.预处理：求出按照长度分组的startWords[j]的占位掩膜，这里可以用HashMap映射，由于长度在[1,26]用数组可以更快
时间复杂度：O(C*N)；空间复杂度：O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public int wordCount(String[] startWords, String[] targetWords) {
        // 预处理出按长度分组的startWords的占位掩膜
        HashMap<Integer, HashSet<Integer>> map = new HashMap<>();
        for (String s : startWords) {
            int len = s.length();
            if (!map.containsKey(len)) {
                map.put(len, new HashSet<>());
            }
            // 求出掩膜
            int mask = 0;
            for (char c : s.toCharArray()) {
                mask |= (1 << (c - 'a'));
            }
            map.get(len).add(mask);
        }
        int res = 0;
        // 枚举目标字符串
        for (String s : targetWords) {
            int len = s.length();
            if (len == 1) continue; // 长度为1不可能可以生成
            // 求出掩膜
            int mask = 0;
            for (char c : s.toCharArray()) {
                mask |= (1 << (c - 'a'));
            }
            // 枚举可以删除的单个字母
            for (char c : s.toCharArray()) {
                int newMask = mask - (1 << (c - 'a'));   // 删除单个字母后的掩膜
                if (map.containsKey(len - 1) && map.get(len - 1).contains(newMask)) {   // 该字符串可以被转化过来
                    res++;  // 结果+1
                    break;  // 退出
                }
            }
        }
        return res;
    }
}

这类掩膜匹配的题目关注的是有哪些字母，只关心有没有而不关心数目多少与顺序是什么，看看不同字符串之间是否由相同的字母组成，这类只关注组分是否完全一致的就可以用位运算十分高效地以O(1)时间复杂度内得出组分是否一致。若只有小写字母：int掩膜；其他更长的可以考虑用long掩膜等…

1835. 所有数对按位与结果的异或和

初始代码 42ms

逐位分析+统计:
设arr1长度为m，arr2长度为n
要求arr1与arr2之间的每一个(i,j)数对组合，我们专注于某一位
1.当arr1[i]该位为0时，arr2[j]该位无论为什么最后AND的结果必然为0，因此贡献了0个1
2.当arr1[i]该位为1时，AND的结果与arr2[j]该位相同，因此贡献了对应arr2[j]对应这么多个1(可进行预处理)
3.统计该位AND之后1的个数一共有多少个
4.由异或的性质可知:1^1^1^…^1，奇数个为1，0^0^0^…^0 为0，无论0有多少个，因此统计1的个数会比较快
5.该位所有这么多1与0异或出来的就是该位异或和结果，其他位以此类推
时间复杂度:O(C*N) 空间复杂度:O©

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int getXORSum(int[] arr1, int[] arr2) {

        // 统计arr2每一位的1有多少个
        int[] cntMap1 = new int[32];
        for (int num : arr2) {
            for (int i = 0; i < 32; i++) {
                if (((num >> i) & 1) == 1) cntMap1[i]++;
            }
        }
        // 统计arr1[i]与arr2[j]组合之后每一位的1的数目(可能很大)
        long[] cntMap2 = new long[32];
        for (int num : arr1) {
            for (int i = 0; i < 32; i++) {
                // 当arr1[i]该位为1
                if (((num >> i) & 1) == 1) {
                    cntMap2[i] += cntMap1[i];
                }
            }
        }
        int res = 0;
        for (int i = 0; i < 32; i++) {
            res += (cntMap2[i] % 2) * (1 << i);
        }
        return res;
    }
}

优化后代码 1ms
优化思路:
1.mask1的位x标记arr2中位x中1的个数奇偶性，为1有奇数个1，为0有偶数个1
2.mask2的位x标记arr1[i]与arr2[j]组合之后的数字位x中1的个数，为1说明有奇数个1，为0说明有偶数个1
3.具体求法可参考原始代码：
3.1 逐位扫描arr1[i]的每一位x，如果该位为0的话AND之后对1的贡献为0；
该位为1AND之后对1的奇偶性贡献恰好是^mask1对应位(异或1之后摆动特性)
3.2 arr1[i]的位x是1利用mask1进行^=即可；但是对应位为0就行是不变的
因此要把arr1[i]对应位为0的屏蔽掉，可以用num&mask1使得arr1[i]为0的位最后异或0，结果不变；
而arr1[i]为1的位保持异或mask1的对应位，记录该位的奇偶性特性变化
4.最后返回mask2就是答案，因为已经是异或之后对应位的组装结果
时间复杂度:O(N) 空间复杂度:O(1)

1
2
3
4
5
6
7
8
class Solution {
    public int getXORSum(int[] arr1, int[] arr2) {
        int mask1 = 0, mask2 = 0;
        for (int num : arr2) mask1 ^= num;
        for (int num : arr1) mask2 ^= num & mask1;
        return mask2;
    }
}