# 1835. 所有数对按位与结果的异或和
### 题目地址(1835. 所有数对按位与结果的异或和)
### 题目描述
```
列表的 异或和（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:
```python
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)$
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/1835.find-xor-sum-of-all-pairs-bitwise-and.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.