1835. 所有数对按位与结果的异或和¶
难度：困难
题目¶
列表的 异或和（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 。
返回上述列表的 异或和 。
示例 1：
输入：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 。
示例 2：
输入：arr1 = [12], arr2 = [4]
输出：4
解释：列表 = [12 AND 4] = [4] ，异或和 = 4 。
提示：
1 <= arr1.length, arr2.length <= 1050 <= arr1[i], arr2[j] <= 109
题解¶
设两个数列\(A=\{a_i\}_m\)与\(B=\{b_j\}_n\)，并使用运算符\(\otimes\)表示 异或 操作，使用运算符\(\land\)表示 与 操作，则本题的结果为：
\[
f(A, B) = \bigotimes_{i=1}^{m} \bigotimes_{j=1}^n a_i\land b_j
\]
考虑表达式\((a\otimes b) \land (a \otimes c)\)：
\[
\begin{aligned}
& (a\otimes b) \land (a \otimes c) \\
\Leftrightarrow & ((a\lor b)\land (\lnot a\lor\lnot b)) \land ((a\lor c)\land (\lnot a\lor\lnot c)) \\
\Leftrightarrow & (a\lor b)\land (\lnot a\lor\lnot b) \land (a\lor c)\land (\lnot a\lor\lnot c) \\
\Leftrightarrow & (a\land (b\lor c)) \land (a\land (\lnot b\lor\lnot c)) \\
\Leftrightarrow & a\land (b\otimes c)
\end{aligned}
\]
因此，\(\otimes\)运算对\(\land\)运算满足分配律，有：
\[
\begin{aligned}
f(A, B) &= \bigotimes_{i=1}^{m} \bigotimes_{j=1}^n a_i\land b_j \\
&= \bigotimes_{i=1}^{m} \left(a_{i}\land\bigotimes_{j=1}^n b_j\right) \\
&= \left(\bigotimes_{i=1}^{m} a_i\right)\land\left(\bigotimes_{j=1}^n b_j\right)
\end{aligned}
\]
int getXORSum(int* arr1, int arr1Size, int* arr2, int arr2Size){
int a = 0, b = 0, i = 0;
for (i = 0; i < arr1Size; i++)
a ^= arr1[i];
for (i = 0; i < arr2Size; i++)
b ^= arr2[i];
return a & b;
}