class Solution {
public:
int getXORSum(vector<int>& arr1, vector<int>& arr2) {
}
};
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原站题解
golang 解法, 执行用时: 112 ms, 内存消耗: 9.2 MB, 提交时间: 2023-09-21 23:36:41
func getXORSum(arr1 []int, arr2 []int) int {
c := 0
for _, i := range arr2 {
c ^= i
}
r := 0
for _, i := range arr1 {
r ^= i & c
}
return r
}
java 解法, 执行用时: 0 ms, 内存消耗: 54.8 MB, 提交时间: 2023-09-21 23:35:52
class Solution {
public int getXORSum(int[] arr1, int[] arr2) {
return xor(arr1)&xor(arr2);
}
public int xor(int num[]){
int ans=0;
for(int i=0;i<num.length;i++){ans^=num[i];}
return ans;
}
}
cpp 解法, 执行用时: 140 ms, 内存消耗: 91.6 MB, 提交时间: 2023-09-21 23:35:12
class Solution {
public:
int getXORSum(vector<int>& arr1, vector<int>& arr2) {
int m = arr1.size();
int n = arr2.size();
int ans = 0;
// 依次确定答案二进制表示中的每一位
for (int k = 30; k >= 0; --k) {
int cnt1 = 0;
for (int num: arr1) {
if (num & (1 << k)) {
++cnt1;
}
}
int cnt2 = 0;
for (int num: arr2) {
if (num & (1 << k)) {
++cnt2;
}
}
// 如果 cnt1 和 cnt2 都是奇数，那么答案的第 k 位为 1
if (cnt1 % 2 == 1 && cnt2 % 2 == 1) {
ans |= (1 << k);
}
}
return ans;
}
int getXORSum2(vector<int>& arr1, vector<int>& arr2) {
int tot1 = accumulate(arr1.begin(), arr1.end(), 0, bit_xor<int>());
int tot2 = accumulate(arr2.begin(), arr2.end(), 0, bit_xor<int>());
return tot1 & tot2;
}
};
python3 解法, 执行用时: 1416 ms, 内存消耗: 31.4 MB, 提交时间: 2023-09-21 23:34:41
class Solution:
def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:
m, n = len(arr1), len(arr2)
ans = 0
# 依次确定答案二进制表示中的每一位
for k in range(30, -1, -1):
cnt1 = sum(1 for num in arr1 if num & (1 << k))
cnt2 = sum(1 for num in arr2 if num & (1 << k))
# 如果 cnt1 和 cnt2 都是奇数，那么答案的第 k 位为 1
if cnt1 % 2 == 1 and cnt2 % 2 == 1:
ans |= (1 << k)
return ans
# 位运算
def getXORSum2(self, arr1: List[int], arr2: List[int]) -> int:
tot1 = reduce(xor, arr1)
tot2 = reduce(xor, arr2)
return tot1 & tot2
python3 解法, 执行用时: 72 ms, 内存消耗: 31.4 MB, 提交时间: 2023-09-21 23:33:57
'''
由于 (a&b)^(a&c) == a&(b^c)，将两个数组的异或和求出，两个异或和的与就是答案。
'''
class Solution:
def getXORSum(self, a: List[int], b: List[int]) -> int:
return reduce(xor, a, 0) & reduce(xor, b, 0)