2425-所有数对的异或和

给你两个下标从 0 开始的数组 nums1 和 nums2 ，两个数组都只包含非负整数。请你求出另外一个数组 nums3 ，包含
nums1 和 nums2 中 所有数对 的异或和（nums1 中每个整数都跟 nums2 中每个整数 恰好
匹配一次）。

请你返回 nums3 中所有整数的 异或和 。

示例 1：

**输入：** nums1 = [2,1,3], nums2 = [10,2,5,0]
**输出：** 13
**解释：**
一个可能的 nums3 数组是 [8,0,7,2,11,3,4,1,9,1,6,3] 。
所有这些数字的异或和是 13 ，所以我们返回 13 。

示例 2：

**输入：** nums1 = [1,2], nums2 = [3,4]
**输出：** 0
**解释：**
所有数对异或和的结果分别为 nums1[0] ^ nums2[0] ，nums1[0] ^ nums2[1] ，nums1[1] ^ nums2[0] 和 nums1[1] ^ nums2[1] 。
所以，一个可能的 nums3 数组是 [2,5,1,6] 。
2 ^ 5 ^ 1 ^ 6 = 0 ，所以我们返回 0 。

提示：

• 1 <= nums1.length, nums2.length <= 105
• 0 <= nums1[i], nums2[j] <= 109

题意分析

---

对于给定的两个数字，返回其所有数对的异或之和

面对位运算的题目，我们不要慌，把运算过程写出来，答案自然就在眼前

下面以nums1:[a,b], nums2:[c,d,e], m=len(nums1), n=len(nums2)举例

思路分析

---

1. 对于此题目的暴力解法为

   ans = (a ^ c) ^ (a ^ d) ^ (a ^ e) ^ (b ^ c) ^ (b ^ d) ^ (b ^ e)

   a,b为nums1元素，c,d,e为nums2元素

2. 根据交换律可知，原式可变为 （这里是最重要的）

   ans = (a ^ a ^ a) ^ (b ^ b ^ b) ^ (c ^ c) ^ (d ^ d) ^ (e ^ e)

   由异或操作，相同为0，不同为1可得(a ^ a ^ a) = a, (c ^ c）= 0 （注意a 和 c分别属于哪个数组）

3. a属于nums1，而式子中a的数量取决于len(nums2)；同理c的数量取决于len(nums1)

   由此我们按照如下思路得出结论

   • 计算出nums1, nums2数组的异或和
   • 若len(nums2) % 2 == 0则nums1数组的n个异或和为0，否则为1
   • nums2同理

4. 根据以上思路即可得出答案

参考代码

---

[]

#define sz(a) a.size()

class Solution {
public:
    int xorAllNums(vector<int>& nums1, vector<int>& nums2) {
        int a=0,b=0,m=sz(nums1),n=sz(nums2);
        //计算出`nums1`, `nums2`数组的异或和
        for(int &v:nums2)b^=v;
        for(int &v:nums1)a^=v;
        //若`len(nums2) % 2 == 0`则`nums1`数组的`n`个异或和为0，否则为1，`nums2`同理
        if(n%2==0)a=0;
        if(m%2==0)b=0;
        //答案
        return a^b;
    }
};

[]

class Solution {
    public int xorAllNums(int[] nums1, int[] nums2) {
        int a=0,b=0,m=nums1.length,n=nums2.length;
        //计算出`nums1`, `nums2`数组的异或和
        for(int v:nums2)b^=v;
        for(int v:nums1)a^=v;
        //若`len(nums2) % 2 == 0`则`nums1`数组的`n`个异或和为0，否则为1，`nums2`同理
        if(n%2==0)a=0;
        if(m%2==0)b=0;
        //答案
        return a^b;
    }
}

[]

class Solution:
    def xorAllNums(self, nums1: List[int], nums2: List[int]) -> int:
        a,b,m,n=0,0,len(nums1),len(nums2);
        # 计算出`nums1`, `nums2`数组的异或和
        for v in nums2:b^=v;
        for v in nums1:a^=v;
        # 若`len(nums2) % 2 == 0`则`nums1`数组的`n`个异或和为0，否则为1，`nums2`同理
        if n%2==0:a=0;
        if m%2==0:b=0;
        # 答案
        return a^b;

[]

public class Solution {
    public int XorAllNums(int[] nums1, int[] nums2) {
        int a=0,b=0,m=nums1.Length,n=nums2.Length;
        //计算出`nums1`, `nums2`数组的异或和
        for(int i=0; i<n; ++i)b^=nums2[i];
        for(int i=0; i<m; ++i)a^=nums1[i];
        //若`len(nums2) % 2 == 0`则`nums1`数组的`n`个异或和为0，否则为1，`nums2`同理
        if(n%2==0)a=0;
        if(m%2==0)b=0;
        //答案
        return a^b;
    }
}