列表的 异或和(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 <= 10^5
0 <= arr1[i], arr2[j] <= 10^9
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/find-xor-sum-of-all-pairs-bitwise-and 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
有公式:
(a&b)^(a&c) = a&(b^c)
用程序测试:
#include<bits/stdc++.h>
using namespace std;
int main(){
for(int a = 0; a < 2; a++){
for(int b = 0; b < 2; b++){
for(int c = 0; c < 2; c++)
{
cout << "a = " << a << " b = " << b << " c = " << c;
cout << " (a&b)^(a&c) = " << ((a&b)^(a&c));
cout << " a&(b^c) = " << (a&(b^c)) << endl;
}
}
}
}
a = 0 b = 0 c = 0 (a&b)^(a&c) = 0 a&(b^c) = 0
a = 0 b = 0 c = 1 (a&b)^(a&c) = 0 a&(b^c) = 0
a = 0 b = 1 c = 0 (a&b)^(a&c) = 0 a&(b^c) = 0
a = 0 b = 1 c = 1 (a&b)^(a&c) = 0 a&(b^c) = 0
a = 1 b = 0 c = 0 (a&b)^(a&c) = 0 a&(b^c) = 0
a = 1 b = 0 c = 1 (a&b)^(a&c) = 1 a&(b^c) = 1
a = 1 b = 1 c = 0 (a&b)^(a&c) = 1 a&(b^c) = 1
a = 1 b = 1 c = 1 (a&b)^(a&c) = 0 a&(b^c) = 0
arr1
每个 元素求的结果为 a1 & (b1^...^bn), a2 & (b1^...^bn), ... an & (b1^...^bn)
(a1^a2...^an) & (b1^...^bn)
class Solution {
public:
int getXORSum(vector<int>& arr1, vector<int>& arr2) {
int xor1 = 0, xor2 = 0;
for(auto a : arr1)
xor1 ^= a;
for(auto a : arr2)
xor2 ^= a;
return xor1 & xor2;
}
};
140 ms 91.2 MB C++
比赛时候按位猜的答案,两边的位必须都有奇数个1答案才为1
class Solution {
public:
int getXORSum(vector<int>& arr1, vector<int>& arr2) {
int n1 = arr1.size(), n2 = arr2.size();
int ans = 0;
vector<int> ct1(32), ct2(32);
for(int i = 0 ;i < n1 ; i++)
{
for(int j = 0; j < 32; j++)
{
if((arr1[i]>>j) & 1)
ct1[j]++;
}
}
for(int i = 0 ;i < n2 ; i++)
{
for(int j = 0; j < 32; j++)
{
if((arr2[i]>>j) & 1)
ct2[j]++;
}
}
for(int i = 0; i < 32; ++i)
{
if(ct1[i]%2 && ct2[i]%2)
ans |= 1<<i;
}
return ans;
}
};
296 ms 91.4 MB C++
我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号(Michael阿明),一起加油、一起学习进步!