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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

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

最后更新于