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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
最近更新 4mo ago