刷题碰到“2657. 找到两个数组的前缀公共数组”这道题时，我第一反应是哈希表计数，扫一遍就能出答案。但它被归在“位运算-基础”分类里，我就坐下来认真研究了一遍位掩码解法。研究完才发现，这道题看起来简单，实际上非常合适用来理解“用二进制位表示集合”这个核心思维，因为题目本身就是让你反复求两个前缀集合的交集大小。我会从题目语义讲起，把暴力法、哈希计数、位掩码三种方案都过一遍，然后重点拆解位运算的关键步骤和容易踩的坑。如果你正在刷题、准备面试，或者想把位运算基础彻底弄明白，这篇文章应该能帮你省不少时间。
1. 先看懂题目：两个前缀数组到底在求什么
1.1 题目原文与输入输出形态
题目给两个长度相同的数组A和B，长度记为n，并且A、B都是0到n-1的一个排列。排列的意思就是：每个数字出现且只出现一次，两个数组内容相同，只是顺序可能不同。
要求你返回一个同样长度为n的答案数组ans。对于每个下标i，ans[i]表示：A[0]到A[i]这一段数字，和B[0]到B[i]这一段数字，公共元素的个数。
注意“公共元素”是按值算的，不是按下标算。也就是说只要数字x同时出现在两个前缀段里，不管它分别在什么位置，都算一个公共元素。
举个例子，A = [1, 3, 2, 4]，B = [3, 1, 2, 4]，正确答案是[0, 2, 3, 4]。我后面会一步步手动推演这个例子，你会很清楚它为什么不是[1, 2, 3, 4]这种无脑递增的结果。
1.2 从样例手推一遍，确认语义
先看i = 0。此时只看A[0] = 1和B[0] = 3，两个前缀集合分别是{1}和{3}，交集为空，所以ans[0] = 0。
再看i = 1。A的前缀是[1, 3]，对应集合{1, 3}；B的前缀是[3, 1]，对应集合{3, 1}。两个集合完全一样，公共元素有1和3两个，所以ans[1] = 2。
到i = 2。A前缀为[1, 3, 2]，B前缀为[3, 1, 2]，集合分别是{1, 3, 2}和{3, 1, 2}，公共元素三个，ans[2] = 3。
到i = 3，两个数组整个拿出来都是{1, 2, 3, 4}，交集就是四个，ans[3] = 4。
这个例子想说明一件事：前缀公共数组不是单调地从某个起点累加，而是每走一步都把两个集合重新求一次交集。只是因为前缀只会越来越长，所以答案一定是不递减的。
1.3 这个题为什么天生适合位运算
如果只看数据范围，n最大是1000，数字范围也被限制在0到n-1，这意味着每个数字都能对应到一个唯一的二进制位。一个集合是否包含数字x，完全可以用“第x位是否为1”来表示。
这种“数字范围连续且有限”的条件，就是位掩码的最佳使用场景。0到1000的连续数字，用1001个二进制位就能装下所有可能的集合状态。而两个集合的交集大小，直接等于两个位掩码做按位与之后，数一下结果里有几个1。
哈希表当然也能做，但位运算把“集合交集”这个看起来需要遍历的操作，压缩成了几个极快的底层指令。这也是为什么 LeetCode 会把这道题放在位运算分类里。
2. 三种解法：暴力、哈希计数、位掩码的取舍
2.1 暴力法：思路最简单，但复杂度不够优雅
暴力做法是：对于每个下标i，先把A[0..i]的所有数字放进一个集合，然后遍历B[0..i]，数一数有多少个数字已经在集合里。
def findThePrefixCommonArray(A, B): n = len(A) ans = [] for i in range(n): seen_a = set(A[:i + 1]) cnt = sum(1 for x in B[:i + 1] if x in seen_a) ans.append(cnt) return ans这个写法在n = 1000时不会超时，但每轮都要构建新集合、遍历一遍前缀，总复杂度是O(n^2)。如果n变成10^5，就完全跑不动了。作为热身可以，作为正解有点浪费。
2.2 哈希计数法：把“公共”翻译成“出现次数达到 2”
因为A和B都是排列，每个数字在A中出现一次，在B中出现一次。从全局角度看，一个数字x如果是当前前缀的公共元素，那么它到目前为止，在A和B中被访问到的总次数恰好是2。
所以可以用一个长度为n + 1的计数数组cnt，遍历过程中同时处理A[i]和B[i]两个数字。每次让对应计数加一，如果加完之后计数等于2，说明这个数字第一次同时出现在两个前缀里，公共计数加一。
def findThePrefixCommonArray(A, B): n = len(A) ans = [] cnt = [0] * (n + 1) common = 0 for i in range(n): cnt[A[i]] += 1 if cnt[A[i]] == 2: common += 1 cnt[B[i]] += 1 if cnt[B[i]] == 2: common += 1 ans.append(common) return ans这里有个隐藏细节：如果A[i] == B[i]，同一个数字会被连续加两次。第一次从1变2，触发common += 1；第二次从2变3，等于2的判断不成立，不会重复计数。所以不需要特判。
这个解法时间复杂度O(n)，空间复杂度O(n)，是这道题最稳妥的正解。
2.3 位掩码视角：集合就是位图，交集就是按位与
位掩码解法不关心某个数字到底出现了几次，只关心它“有没有出现过”。维护两个掩码变量maskA和maskB：
maskA的第x位为1，表示数字x已经在A的前缀中出现过；maskB同理。
每走一步，把A[i]对应位置为1，再把B[i]对应位置为1。此时，maskA & maskB中为1的位，就是两个前缀都出现过的数字；统计这个结果里1的个数，就是当前答案。
以A = [1, 3, 2, 4]、B = [3, 1, 2, 4]为例，逐步看掩码变化：
| i | maskA | maskB | maskA & maskB | 1的个数 |
|---|---|---|---|---|
| 0 | 第1位=1 | 第3位=1 | 0 | 0 |
| 1 | 第1,3位=1 | 第1,3位=1 | 第1,3位=1 | 2 |
| 2 | 第1,2,3位=1 | 第1,2,3位=1 | 第1,2,3位=1 | 3 |
| 3 | 第1,2,3,4位=1 | 第1,2,3,4位=1 | 第1,2,3,4位=1 | 4 |
可以清楚看到，每一步的答案就是(maskA & maskB)的二进制中1的个数，也就是popcount。这种写法把“集合求交”变成一条指令，非常直观。
3. 位运算核心知识点拆解
3.1 用二进制位表示一个集合
位掩码的核心思想：一个整数本身是很多二进制位的组合，每一个位都可以代表一个独立状态。比如数字5的二进制是101，可以认为它同时拥有“第 0 位”和“第 2 位”。
放到集合场景里，就是约定第x位表示数字x是否在集合中。数字x对应的位是1 << x，把x加入集合就是mask | (1 << x)。因为1 << x得到的是一个只有第x位为1的整数，与mask做按位或，只会让第x位变成1，不会影响其他位。
判断x是否在集合中，就是看mask & (1 << x)是否不为0，这也是位运算中最常用的技巧之一。
3.2 左移、或运算、按位与、popcount 四件套
做这道题只需要四个位运算操作：
- 左移：
1 << x，得到一个“只有第 x 位是 1”的数。 - 按位或：
mask |= 1 << x，把x加入集合。 - 按位与：
maskA & maskB，得到两个集合的交集。 - 统计 1 的个数：
popcount，也就是数交集大小。
如果觉得抽象，可以想象成影厅座位表。电影院里座位编号从 0 开始，有人坐就是 1，没人坐就是 0。maskA是 A 队坐过的座位，maskB是 B 队坐过的座位。maskA & maskB就是找出两边都坐过的座位，数一遍就是公共人数。
3.3 不同语言怎么取二进制中 1 的个数
统计1的个数在不同语言里方法不太一样，写题时最容易卡在这一步。
| 语言 | 方法 | 说明 |
|---|---|---|
| Python 3.10+ | x.bit_count() | 直接统计二进制中 1 的个数 |
| Python 旧版本 | bin(x).count("1") | 先转成二进制字符串再数 |
| Java | Integer.bitCount(x)/Long.bitCount(x) | 基础库自带，按 int 或 long 范围统计 |
| C++ | __builtin_popcount(x) | GCC 内置函数，int 版本 |
| C++ | std::bitset<N>::count() | 位集对象直接统计 |
| Go | bits.OnesCount64(x) | math/bits 包 |
bit_count这类函数底层通常有硬件指令加速，性能很高，但要注意它统计的位数上限和变量的位宽一致。比如 Java 的Integer.bitCount只能统计int的 32 位，Long.bitCount只能统计 64 位。
3.4 位宽到底够不够：int、long、大整数怎么选
这道题的n最大是 1000，所以你立刻会遇到一个问题：int只有 32 位，long只有 64 位，装不下 1000 个状态。这时候有三种选择：
- 如果
n <= 31，一个int足够； - 如果
n <= 63，一个long足够； - 如果
n更大，就需要用long[]、BitSet、std::bitset或者 Python 的大整数。
Python 在这种题里有个天然优势：int是任意精度，1 << 1000根本不会溢出，所以你可以直接用一个整数当位集，不需要额外的数据结构。Java 和 C++ 则需要选择合适的大位集容器。
4. 手把手实现：从把样例跑通到处理边界
4.1 Python：几行代码搞定，适合用来理解思路
如果环境是 Python 3.10 及以上，用大整数配合bit_count，代码可以写得非常简洁：
class Solution: def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]: mask_a = 0 mask_b = 0 ans = [] for x, y in zip(A, B): mask_a |= 1 << x mask_b |= 1 << y ans.append((mask_a & mask_b).bit_count()) return ans这段代码的每一行都值得说清楚。
mask_a = 0初始集合为空。循环里mask_a |= 1 << x，意思是把数字x对应的二进制位置为 1。mask_b同理。然后(mask_a & mask_b)得到两个集合的交集，bit_count()统计这个交集中有多少个 1，也就是公共元素个数。
如果 Python 版本比较旧，没有bit_count，可以改成：
ans.append(bin(mask_a & mask_b).count("1"))功能一样，但性能略慢。
4.2 Java：用 long[] 模拟“大位集”的完整实现
Java 没有 Python 那样无限大的整数，但可以把多个long拼成一个位集。每个long是 64 位，n = 1000时只需要(1000 + 63) / 64 = 16个long。
class Solution { public int[] findThePrefixCommonArray(int[] A, int[] B) { int n = A.length; int wordSize = (n + 63) >> 6; long[] maskA = new long[wordSize]; long[] maskB = new long[wordSize]; int[] ans = new int[n]; for (int i = 0; i < n; i++) { setBit(maskA, A[i]); setBit(maskB, B[i]); int common = 0; for (int j = 0; j < wordSize; j++) { common += Long.bitCount(maskA[j] & maskB[j]); } ans[i] = common; } return ans; } private void setBit(long[] mask, int x) { mask[x >> 6] |= 1L << (x & 63); } }这里x >> 6相当于x / 64，算出数字x落在第几个long桶里；x & 63相当于x % 64，算出在桶内的第几位。1L << (x & 63)必须带后缀L，否则 Java 会按int运算。
这段代码每次循环都要扫描全部 16 个桶，总操作量大约是16 * 1000次，对n = 1000来说完全没问题。如果n更大，比如10^5，就不推荐这种写法了，因为扫描成本会变成O(n^2 / 64)。
Java 还有一种更省事的写法：直接用java.util.BitSet。
import java.util.BitSet; class Solution { public int[] findThePrefixCommonArray(int[] A, int[] B) { int n = A.length; BitSet maskA = new BitSet(n); BitSet maskB = new BitSet(n); int[] ans = new int[n]; for (int i = 0; i < n; i++) { maskA.set(A[i]); maskB.set(B[i]); BitSet tmp = (BitSet) maskA.clone(); tmp.and(maskB); ans[i] = tmp.cardinality(); } return ans; } }BitSet的好处是自动扩容，不需要手动算桶。clone()会做深拷贝，不会影响原来的maskA。cardinality()返回置位个数，等价于popcount。
4.3 C++：std::bitset 的可读写法
C++ 的std::bitset在编译期就要确定大小。这道题n <= 1000，可以直接把大小设为 1000，非常省事：
class Solution { public: vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) { int n = A.size(); vector<int> ans(n); bitset<1000> bsA, bsB; for (int i = 0; i < n; ++i) { bsA[A[i]] = 1; bsB[B[i]] = 1; ans[i] = (bsA & bsB).count(); } return ans; } };bitset支持下标赋值和按位与，count()直接返回 1 的个数，可读性非常好。需要注意bitset<1000>是编译期固定的，如果题目数据范围改了，要记得同步调整。
4.4 复杂度与适用场景对比
三种方案各有适用场景，放在一起对比更清楚：
| 方案 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 暴力法 | O(n^2) | O(n) | 只求理解题意，不推荐提交 |
| 哈希计数法 | O(n) | O(n) | 通用性最强，n 很大也稳 |
| 位掩码法（Python 大整数） | O(n)（位宽受限于 n/字长） | O(1) 概念上可视为整数字长 | 数字范围连续，用大整数语言最爽 |
| 位掩码法（Java long[]/BitSet） | 每步要扫描位集，总约 O(n^2 / 64) | O(n) | n 在几千以内，常数极小 |
哈希计数法在理论上是最优的，时间复杂度稳定在O(n)，所以面试时如果只要求写出正解，哈希计数是最安全的。位运算的价值更多在于锻炼“状态压缩”的思维，以及在某些特定场景下让你不需要维护频次数组，直接一个整数搞定问题。
5. 我踩过的坑和排查技巧
5.1 左移溢出：1 << x 不是你以为的那样
Java 中int左移只取低 5 位作为移动位数，long左移只取低 6 位。也就是说，1 << 32在 Java 中等于1 << 0，1L << 64等于1L << 0。如果你写了1L << 64，你并没有得到第 64 位是 1 的结果，而是原地打转，位集状态会错乱。
C++ 中1 << 100则是未定义行为，可能得到任何值。我最初在本地测试时用了个超过位宽的数字，结果答案飞到了天边，排查了半天才发现是左移越界。
所以用固定位宽语言时，要么先用x >> 6分桶，再用x & 63限制桶内偏移；要么直接用官方封装的BitSet。不要手写越界左移。
5.2 & 的优先级坑：maskA & maskB == 0 会出问题
很多需要写判断的地方，按位与&的优先级比等于号==低。比如想判断两个位集交集是否为空，直觉上写成：
if (maskA & maskB == 0) { ... }实际上会先计算maskB == 0，再与maskA做按位与，结果完全不对。正确写法是：
if ((maskA & maskB) == 0) { ... }这个坑不只影响这道题，很多位运算题目里都会出现。规则很简单：位运算里除了~比较高，&、|、^的优先级都比比较运算符低，所以只要混合使用，就老老实实加括号。
5.3 A[i] == B[i] 时的重复计数问题
哈希计数法里有一个细节：如果A[i]和B[i]是同一个数字，先++cnt[A[i]]触发== 2，common加一；再++cnt[B[i]]变成 3，不会触发。这正好保证了只计一次。
但如果你改成“cnt[x] >= 2就加一”，遇到A[i] == B[i]时就会重复计数，结果偏大。所以判断条件写== 2还是>= 2要想清楚。在这个题目约束下，== 2是最精确的。
5.4 什么时候别用位运算
位运算不是万能的。如果题目不保证数组是0..n-1的排列，数字范围可能很大，比如10^9，用位掩码表示集合就完全不现实了，因为一个整数装不下那么大的位宽。
另外如果n特别大，Java 里每步扫描整个long[]会让复杂度退化到O(n^2 / 64)。虽然常数小，但遇到n = 10^5级别的数据，还是应该老老实实回到哈希计数。
有一类通用性更好的哈希做法：维护两个频次数组分别记录A前缀和B前缀中每个数字的出现次数，每次更新后如果某个数字在两个频次数组里都大于 0，则公共计数加一。这样即使数组不是排列，也不会出错。不过对这道题而言，用单数组cnt等于2的判断就已经充分且正确了。
5.5 快速自测清单
写完代码后，我一般会跑这几组数据验证：
A = [0],B = [0]，期望输出[1]。A = [0, 1],B = [1, 0]，期望输出[0, 2]。A = [0, 1, 2],B = [0, 1, 2]，期望输出[1, 2, 3]。A = [0, 1, 2],B = [2, 1, 0]，期望输出[0, 1, 3]。
如果你实现的位运算版本这四个都对，基本可以放心提交了。特别是第一组n = 1的边界情况，很多代码在其他用例没问题，到最小输入上反而容易出错。
我个人在实际刷题中的体会是：先用哈希计数法快速拿到 AC，再用位运算重写一遍，对比两种实现，收益远大于死记硬背某一套解法。位运算的熟练度，本质上就是“能不能把一个集合塞进一个数里”的意识。以后遇到权限位、布隆过滤器雏形、状态压缩 DP、甚至简单的用户标签交集统计，你都能用上这套思维。如果想进一步练手，可以把这道题扩展到“三个数组的前缀公共数组”，这时位运算的优势会更明显，因为多维护一个maskC就行了，而哈希计数法则要多维护一个频次状态。
