题目描述

列表的 异或和（XOR sum）指对所有元素进行按位 XOR 运算的结果。如果列表中仅有一个元素，那么其 异或和 就等于该元素。

• 例如，[1,2,3,4] 的 异或和 等于 1 XOR 2 XOR 3 XOR 4 = 4，而 [3] 的 异或和 等于 3。

给你两个下标 从 0 开始 计数的数组 arr1 和 arr2，两数组均由非负整数组成。

根据每个 (i, j) 数对，构造一个由 arr1[i] AND arr2[j]（按位 AND 运算）结果组成的列表。其中 0 <= i < arr1.length 且 0 <= j < arr2.length。

返回上述列表的 异或和。

样例

输入：arr1 = [1,2,3], arr2 = [6,5]
输出：0
解释：列表 = [1 AND 6, 1 AND 5, 2 AND 6, 2 AND 5, 3 AND 6, 3 AND 5] = [0,1,2,0,2,1]，
异或和 = 0 XOR 1 XOR 2 XOR 0 XOR 2 XOR 1 = 0。

输入：arr1 = [12], arr2 = [4]
输出：4
解释：列表 = [12 AND 4] = [4] ，异或和 = 4。

限制

• 1 <= arr1.length, arr2.length <= 10^5
• 0 <= arr1[i], arr2[j] <= 10^9

算法1

(按位分解) $O(n \log S)$

1. 按位计算，对于每一位来说，假设 arr1 中有 o1 个 1，arr2 中有 o2 个 1。
2. 如果 o1 * o2 为奇数，则最终答案上这一位也是 1。这是因为 o1 * o2 为最终 AND 结果中该位 1 的个数，如果有奇数个，则异或结果为 1。

时间复杂度

• 每个二进制为都需要 $O(n)$ 的时间，故总时间复杂度为 $O(n \log S)$，其中 $S$ 为最大可能的数字。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int getXORSum(vector<int>& arr1, vector<int>& arr2) {
        const int n = arr1.size(), m = arr2.size();

        int ans = 0;
        for (int bit = 0; bit < 30; bit++) {
            int o1 = 0, o2 = 0;
            for (int i = 0; i < n; i++)
                if ((arr1[i] >> bit) & 1)
                    o1++;

            for (int i = 0; i < m; i++)
                if ((arr2[i] >> bit) & 1)
                    o2++;

            if ((o1 & o2) & 1)
                ans |= 1 << bit;
        }

        return ans;
    }
};

算法2

(按位分解) $O(n)$

1. 在算法 1 的基础上，可以不必进行显式分解，直接求出 arr1 的所有异或和 o1，和 arr2 的所以异或和 o2。
2. 最终 o1 & o2 就是答案，原理和算法 1 一样，都是分解来看，把以上过程通过位运算进行简化：累加后做乘法判奇偶，就相当于两个数提前判奇偶（累加过程变为异或）然后再 AND，只不过这里把所有位的运算过程重新组合到了一起。

时间复杂度

• 遍历数组各一次，故总时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int getXORSum(vector<int>& arr1, vector<int>& arr2) {
        int o1 = 0, o2 = 0;
        for (int a : arr1) o1 ^= a;
        for (int a : arr2) o2 ^= a;
        return o1 & o2;
    }
};