LeetCode 1835 所有数对按位与结果的异或和题目理解给定两个数组 arr1 、 arr2 求出每一个 arr1 元素 每一个 arr2 元素的结果再把所有这些结果做异或和。暴力枚举双重循环会超时需要按位统计 位运算规律优化。核心结论数学规律对于某一个二进制第 k 位1. 只有当 a[i] 的第 k 位 为1 且 b[j] 的第 k 位 为1 时 a[i] b[j] 的第 k 位才是 12. 设- cnt1 arr1 中第 k 位为 1 的数字个数cnt2 arr2 中第 k 位为 1 的数字个数3. 该位总共有 cnt1 * cnt2 个 14. 异或性质偶数个1异或为0奇数个1异或为1。- 若 cnt1 * cnt2 是奇数最终结果第k位为1否则第k位为0Java 代码javapublic class Solution {public int getXORSum(int[] arr1, int[] arr2) {int res 0;// 遍历每一位 0~30int 最高有效位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;}}// 乘积为奇数该位贡献1if ((long) cnt1 * cnt2 % 2 1) {res | (1 k);}}return res;}}极简推论版一行思路最终答案 (arr1所有元素异或和) (arr2所有元素异或和)极简代码javapublic 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(nm)。