LeetCode 1835 题解：所有数对按位与结果的异或和——从逐位计数到 O(m+n) 的整体异或推导

LeetCode 1835 题解：所有数对按位与结果的异或和——从逐位计数到 O(m+n) 的整体异或推导

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

本篇是 LeetCode 题解仓库中第 1835 题「所有数对按位与结果的异或和」的完整技术解析。题目要求对两个数组中所有arr1[i] AND arr2[j]的结果再做异或求和，核心难点在于理解 AND 与 XOR 在二进制位上的独立性与奇偶性规律。读完本文，你将掌握"从位视角分解复合位运算"的通用套路、O(32×(m+n)) 的逐位计数实现，以及由位运算性质推导出的 O(m+n) 整体异或进阶解法。

题目描述

列表的异或和（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 <= 10^5 0 <= arr1[i], arr2[j] <= 10^9

前置知识：位运算基础

• 按位异或（XOR）：同一位数字相同则为 0，不同则为 1；
• 按位与（AND）：两个 1 相与结果为 1，否则为 0。

本仓库的位运算专题文章 thinkings/bit.md 系统总结了 XOR 的三条关键规律，它们是理解本题的基石：

1. 任何数和自身异或结果为0（a ^ a = 0）；
2. 任何数和0异或是它本身（a ^ 0 = a）；
3. 异或运算满足交换律与结合律（a ^ b ^ c = a ^ c ^ b）。

另外需要说明一个关键事实：XOR 和 AND 都是逐位独立运算——结果中的某一位只取决于参与运算各数的同一位，与其他位无关。这正是"从位视角拆解问题"的依据。

思路：从朴素模拟到逐位计数

第一步：先想最直接的解法

按题目字面意思，我们可以先生成一个长度为m * n的数组（其中 m 和 n 分别为 A 和 B 的长度），再对这m * n个数做全员异或。

以题目的例子来说：

输入：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 最大均可达到 10^5，构造m * n长度的数组在时空上都无法承受，因此必须优化。

第二步：从"位"的视角看最终结果

题目要求返回一个 32 位的整数，本质上是问：最终结果的 32 个位上，每一位分别是 0 还是 1？

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

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

• 如果 1 的个数是奇数，那么异或结果一定是 1；
• 否则异或结果一定是 0。

这是因为 XOR 本质上是二进制下的"不进位加法"：所有 1 两两抵消，剩下奇数个 1 时该位即为 1。这也是 thinkings/bit.md 中"任何数和本身异或则为 0"这一规律的直接推论。

第三步：用 AND 的特性统计 1 的个数

那么如何确定这m * n个数的第 i 位 1 的个数呢？这就需要用到 AND 的特性了：1 只有和 1 结合才能产出 1。

因此我们只需要分别计算出 A 和 B 在第 i 位的 1 的个数即可，答案就是 A 和 B 在这一位的 1 的个数乘积。比如 A 中在第 i 位有 3 个 1，B 中在第 i 位有 4 个 1，那么 AND 后为 1 的只会出现在这3 * 4 = 12个 AND 结果中（笛卡尔积）。

于是整个算法流程清晰了：

1. 对每一位 i（0 到 30），分别统计 A 中该位为 1 的个数ones_a和 B 中该位为 1 的个数ones_b；
2. 若ones_a * ones_b为奇数，则最终结果第 i 位为 1，将该位置位；
3. 遍历完所有位即得到答案。

关于位数范围的说明：提示中arr1[i], arr2[j] <= 10^9，而10^9 < 2^30，因此遍历第 0 到第 30 位共 31 位即可覆盖所有取值；用range(31)或range(32)均安全。

关键点

• 从位的角度思考问题：把 32 位整数的每一位当作独立的子问题分别求解；
• 位运算（这里是 AND 和 XOR）的基本特性：AND 用于统计"1 的个数乘积"，XOR 用于判断"1 的个数奇偶"；
• 两个计数器的乘积取代了暴力枚举m * n个数对，是复杂度优化的核心。

代码实现

Python3（逐位计数版）

以下实现与仓库原题解 problems/1835.find-xor-sum-of-all-pairs-bitwise-and.md 中的逻辑一致，并补充了详细注释：

class Solution: def getXORSum(self, A: List[int], B: List[int]) -> int: ans = 0 # 遍历第 0 ~ 30 位（10^9 < 2^30） for i in range(31): ones_a = ones_b = 0 # 统计 A 中第 i 位为 1 的个数 for a in A: if a & (1 << i): ones_a += 1 # 统计 B 中第 i 位为 1 的个数 for b in B: if b & (1 << i): ones_b += 1 # AND 后第 i 位为 1 的个数 = ones_a * ones_b（笛卡尔积） # 异或后第 i 位为 1 当且仅当该乘积为奇数 if ones_a * ones_b & 1: ans |= 1 << i return ans

JavaScript（逐位计数版参考实现）

逐位计数的思路不依赖语言特性，可直接翻译为 JS：

var getXORSum = function (A, B) { let ans = 0; for (let i = 0; i < 31; i++) { let onesA = 0, onesB = 0; for (const a of A) if (a & (1 << i)) onesA++; for (const b of B) if (b & (1 << i)) onesB++; if ((onesA * onesB) & 1) ans |= 1 << i; } return ans; };

复杂度分析

令 m 为 arr1 的长度，n 为 arr2 的长度（原文档写作"令 n 为数组长度"，此处更精确地区分两个数组）：

• 时间复杂度：$O(32 \times (m + n))$，外层固定遍历 31 位，内层分别遍历 A 与 B 各一次；
• 空间复杂度：$O(1)$，只使用了常数个变量。

相比暴力构造m * n长度列表再异或的 $O(m \times n)$ 方案，逐位计数已将复杂度降到线性，在m, n <= 10^5的约束下可以轻松通过。

深入推导：O(m+n) 的整体异或进阶解法

原题解的逐位计数解法已经足够优秀，但基于同样的位运算性质，还可以推导出更简洁的结论。

回忆逐位计数的判定条件：最终结果第 i 位为 1，当且仅当ones_a[i] * ones_b[i]为奇数，即ones_a[i]与ones_b[i]均为奇数。

而另一方面，考察arr1全体的异或和xor_a = A[0] ^ A[1] ^ ...：

• xor_a的第 i 位为 1，当且仅当ones_a[i]为奇数（同样由 XOR 的奇偶性判定得出）。

同理，xor_b = B[0] ^ B[1] ^ ...的第 i 位为 1，当且仅当ones_b[i]为奇数。

于是：最终结果第 i 位为 1 ⟺xor_a与xor_b的第 i 位同时为 1，这恰好就是按位与运算的定义。因此可以直接得出：

answer = xor_a & xor_b

即：先分别求出两个数组各自的整体异或和，再做一次按位与。用两个示例验证：

• 示例 1：xor_a = 1 ^ 2 ^ 3 = 0，xor_b = 6 ^ 5 = 3，0 & 3 = 0✓
• 示例 2：xor_a = 12，xor_b = 4，12 & 4 = 4✓

对应实现为：

class Solution: def getXORSum(self, A: List[int], B: List[int]) -> int: xor_a = 0 for a in A: xor_a ^= a xor_b = 0 for b in B: xor_b ^= b return xor_a & xor_b

此版本的时间复杂度为 $O(m + n)$，比逐位计数更进一步（少了一个 32 的常数因子），且代码更短。它本质上是利用"AND 对 XOR 满足分配律"（对每一位而言，AND 相当于乘法、XOR 相当于不进位加法）将双重遍历压缩为两次单数组遍历。这一结论是对原文档思路的延伸推导，适合作为面试中的加分项展示。

仓库内的同类题目与延伸阅读

本题属于"逐位分析 + 奇偶性判定"的典型位运算题型，本仓库中还有一系列同主题题解可以对照学习：

• thinkings/bit.md：仓库位运算专题，系统梳理 XOR 性质，并详解 136、137、260、645 等经典题目；
• problems/136.single-number.md：只出现一次的数字，全员异或的经典应用（a ^ a = 0）；
• problems/191.number-of-1-bits.md：位 1 的个数，练习"统计某一位上 1 的个数"这一本题的核心操作；
• problems/371.sum-of-two-integers.md：两整数之和，展示 AND 与 XOR 组合完成加法（不进位加法的实现）；
• problems/190.reverse-bits.md：颠倒二进制位，训练对每一位的独立读写；
• problems/1371.find-the-longest-substring-containing-vowels-in-even-counts.md：元音字母偶数次的最长子串，用 XOR 做状态压缩的进阶应用。

建议按"先专题文章建立位运算直觉，再逐题练习统计 1 的个数与奇偶性判定"的顺序学习，位运算类题目大多可以归结为：把每一位当作独立子问题，用 AND/OR/XOR 的性质找出每一位的判定条件，最后按位拼回答案。

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode