1835. 所有数对按位与结果的异或和

题目地址(1835. 所有数对按位与结果的异或和)

https://leetcode-cn.com/problems/find-xor-sum-of-all-pairs-bitwise-and/

题目描述

列表的 异或和（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

前置知识

• 位运算

公司

• 暂无

思路

异或的性质：相同的位异或结果为 0 ，否则为 1。 AND 的性质：两个 1 AND 结果为 1，否则为 0

这道题需要我们返回 and 后异或的结果。更本质地，我们需要返回一个 32 bit 的数字。那么 32 位上分别是 0 还是 1 呢？这就是我们需要解决的问题。

而两个数组的异或和，实际上可以 先 生成一个长度为 m * n 的数组，其中 m 和 n 分别为 A 和 B 的长度。

以题目的例子来说：

输入：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] ，

列表长度就是 3 * 2 = 6。

我们需要将这 m _ n 个数的 逐位 进行一次 XOR 操作，一共 XOR 32 次即可。每次 XOR 我们都需要将 m _ n 个数的 一共 m * n 位参与运算。

具体来说，我们现在想确定最终结果的第 i 位是 0 还是 1。由异或的性质，实际上只需要确定 m * n 个数中第 i 位是 1 的个数即可。

• 如果 1 的个数是奇数，那么异或结果一定是 1

• 否则异或结果一定是 0

那么如果确定这 m _ n 个数的 1 的个数呢？这就需要用到上面提到的 AND 特性了。 1 只有和 1 结合才能搞出 1，因此我们只需要分别计算出 A 和 B 在这一位的 1 的个数即可，答案就是 A 和 B 在这一位的个数 乘积 。 比如 A 中在第 i 位 有 3 个 1，B 中在第 i 位有 4 个 1，那么 AND 后为 1 ，只能在这 3 _ 4 = 12 个 AND 中产生（笛卡尔积）。

关键点

• 从位的角度思考问题

• 位运算（这里是 AND 和 XOR）的基本特性

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def getXORSum(self, A: List[int], B: List[int]) -> int:
        ans = 0
        for i in range(31):
            ones_a = ones_b = 0
            for a in A:
                if a & (1 << i):
                    ones_a += 1
            for b in B:
                if b & (1 << i):
                    ones_b += 1
            if ones_a * ones_b & 1:
                ans |= 1 << i
        return ans

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(32 * n)$

• 空间复杂度：$O(1)$

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。