LeetCode 1835. 所有数对按位与结果的异或和（位运算 (a&b)^(a&c) = a&(b^c) ）

Michael阿明

发布于 2021-09-06 10:55:56

6720

发布于 2021-09-06 10:55:56

文章被收录于专栏：Michael阿明学习之路

文章目录

- 1. 题目
- 2. 解题

1. 题目

列表的异或和（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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

有公式：

(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)
上式写n项再求异或，然后把右边一项提出来有 (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++