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-1startWords[j]转换过来
4.我们可以枚举每个targetWords[i],再枚举某个targetWords[i]中可删除的字母,每当删除一个字母后假若在长度为len-1startWords[j]中找到相同掩膜的说明这个targetWords[i]可以完成转换,res++然后直接下一个;当枚举完后都不能转换就说明不能完成转换
5.预处理:求出按照长度分组的startWords[j]的占位掩膜,这里可以用HashMap映射,由于长度在[1,26]用数组可以更快
时间复杂度:O(C*N);空间复杂度:O(N)

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©

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)

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