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

题目理解

给定两个数组  arr1 、 arr2 ，求出每一个 arr1 元素 & 每一个 arr2 元素的结果，再把所有这些结果做异或和。

暴力枚举双重循环会超时，需要按位统计 + 位运算规律优化。

核心结论（数学规律）

对于某一个二进制第 k 位：

1. 只有当  a[i]  的第 k 位 为1 且  b[j]  的第 k 位 为1 时， a[i] & b[j]  的第 k 位才是 1；
2. 设：-  cnt1 ：arr1 中第 k 位为 1 的数字个数

• cnt2 ：arr2 中第 k 位为 1 的数字个数
  3. 该位总共有  cnt1 * cnt2  个 1；
  4. 异或性质：偶数个1异或为0，奇数个1异或为1。- 若  cnt1 * cnt2  是奇数：最终结果第k位为1
• 否则：第k位为0

Java 代码

java

public class Solution {
public int getXORSum(int[] arr1, int[] arr2) {
int res = 0;
// 遍历每一位 0~30（int 最高有效位）
for (int k = 0; k < 31; k++) {
int cnt1 = 0, cnt2 = 0;
// 统计arr1第k位为1的数量
for (int num : arr1) {
if ((num >> k & 1) == 1) {
cnt1++;
}
}
// 统计arr2第k位为1的数量
for (int num : arr2) {
if ((num >> k & 1) == 1) {
cnt2++;
}
}
// 乘积为奇数，该位贡献1
if ((long) cnt1 * cnt2 % 2 == 1) {
res |= (1 << k);
}
}
return res;
}
}

极简推论版（一行思路）

最终答案 = (arr1所有元素异或和) & (arr2所有元素异或和)

极简代码

java

public int getXORSum(int[] arr1, int[] arr2) {
int xor1 = 0, xor2 = 0;
for (int x : arr1) xor1 ^= x;
for (int x : arr2) xor2 ^= x;
return xor1 & xor2;
}

原理

按位推导可证明：原式等价于  (xor(arr1)) & (xor(arr2)) ，时间复杂度直接降到 O(n+m)。