本文涉及知识点
位运算 拆位法
LeetCode1835. 所有数对按位与结果的异或和
列表的 异或和（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 <= 105
0 <= arr1[i], arr2[j] <= 109
拆位法
代码
核心代码
class Solution { public: int getXORSum(vector<int>& arr1, vector<int>& arr2) { const int iBitCnt = 31; int iRet = 0; for (int i = 0; i < iBitCnt; i++) { int cnt1 = 0, cnt2 = 0; for (const auto& n : arr1) { cnt1 += bool(n & (1 << i)); } for (const auto& n : arr2) { cnt2 += bool(n & (1 << i)); } if ((1 & cnt1) && (1 & cnt2)) { iRet |= (1 << i); } } return iRet; } };
测试用例
template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector<int> arr1, arr2; { Solution sln; arr1 = { 1, 2, 3 }, arr2 = { 6, 5 }; auto res = sln.getXORSum(arr1, arr2); Assert(0, res); } { Solution sln; arr1 = { 12 }, arr2 = { 4}; auto res = sln.getXORSum(arr1, arr2); Assert(4, res); } }
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
