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

LeetCode 1835 题解所有数对按位与结果的异或和——从逐位计数到 O(mn) 的整体异或推导【免费下载链接】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×(mn)) 的逐位计数实现以及由位运算性质推导出的 O(mn) 整体异或进阶解法。题目描述列表的异或和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 的三条关键规律它们是理解本题的基石任何数和自身异或结果为0a ^ a 0任何数和0异或是它本身a ^ 0 a异或运算满足交换律与结合律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 个 1B 中在第 i 位有 4 个 1那么 AND 后为 1 的只会出现在这3 * 4 12个 AND 结果中笛卡尔积。于是整个算法流程清晰了对每一位 i0 到 30分别统计 A 中该位为 1 的个数ones_a和 B 中该位为 1 的个数ones_b若ones_a * ones_b为奇数则最终结果第 i 位为 1将该位置位遍历完所有位即得到答案。关于位数范围的说明提示中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 ansJavaScript逐位计数版参考实现逐位计数的思路不依赖语言特性可直接翻译为 JSvar 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(mn) 的整体异或进阶解法原题解的逐位计数解法已经足够优秀但基于同样的位运算性质还可以推导出更简洁的结论。回忆逐位计数的判定条件最终结果第 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即先分别求出两个数组各自的整体异或和再做一次按位与。用两个示例验证示例 1xor_a 1 ^ 2 ^ 3 0xor_b 6 ^ 5 30 3 0✓示例 2xor_a 12xor_b 412 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 0problems/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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考