刷题群里有朋友甩了一道题过来LeetCode 2657中文名“找到两个数组的前缀公共数组”标签写着“位运算·基础”。说实话位运算题对很多人来说一直有种“看得懂代码、轮到自己写就卡壳”的别扭感而这题恰恰是那种能把位运算的套路讲明白的入门题。它不考什么花哨技巧核心就一句话把一个数组前缀里“出现过哪些数”这个集合用整数的二进制位装起来然后该求交集就 AND该数个数就 bit count。先给没做过的人交代清楚它能干什么给定两个长度相同的排列 A 和 B里面是 1 到 n 各出现一次要输出数组 C其中 C[i] 等于 A 的前 i1 个数和 B 的前 i1 个数里共同出现过的数字个数。注意是统计“两边前缀集合的交集大小”不是统计下标相等的位置。适合谁来读如果你正在刷题准备面试或者刚学完 | ^ ~ 和移位想找一道不难的题把“集合状态压缩”这个概念落地这篇应该能帮上忙。我会从最暴力的写法一路拆到位运算写法把每一步为什么这么写讲清楚。1. 先把题意嚼碎C[i] 到底在数什么1.1 一个例子胜过千言万语光看定义容易绕直接走一个例子。假设A [1, 3, 2, 4]B [3, 1, 2, 4]逐个位置看前缀集合和它们的交集iA[0..i]B[0..i]两边共同的数字C[i]0{1}{3}无01{1, 3}{3, 1}{1, 3}22{1, 3, 2}{3, 1, 2}{1, 2, 3}33{1, 3, 2, 4}{3, 1, 2, 4}{1, 2, 3, 4}4所以答案应该是 [0, 2, 3, 4]。这里要特意澄清一个经典误区有人会把 C[i] 理解成“前 i1 个位置里 A[j] B[j] 的下标个数”。在这个例子里那种算法会得到 [0, 0, 1, 2]跟正确答案差很远。题目统计的是值不是位置。A 的第 0 个元素是 1B 的第 0 个元素是 3虽然位置对不上但第 1 步时 1 已经出现在 B 的头部、3 已经出现在 A 的前缀里所以交集立刻变成 2 个。理解到这一层后面所有解法都不会跑偏。1.2 两个关键性质直接推导出数学模型这题能有好几种漂亮解法的根本原因是题目给了一个很强的条件A 和 B 都是排列。也就是说每个数字在 A 里恰好出现一次在 B 里也恰好出现一次。那么一个数字 x 什么时候进入“公共集合”很简单当它在这两个数组里的两个出现位置都被扫描过的时候。设 posA[x] 是 x 在 A 里的下标posB[x] 是 x 在 B 里的下标那么到第 i 步为止x 能算作公共元素当且仅当posA[x] ≤ i 且 posB[x] ≤ i等价于max(posA[x], posB[x]) ≤ i这个式子非常值钱。它告诉我们 C[i] 其实就是“所有满足阈值 max(posA[x], posB[x]) 不超过 i 的数字个数”。基于这个模型可以写出一个不太为人提、但极其干净的 O(n) 解法vectorint ans(n); vectorint bucket(n, 0); for (int v 1; v n; v) { bucket[max(posA[v], posB[v])]; } int common 0; for (int i 0; i n; i) { common bucket[i]; ans[i] common; }用刚才的例子验证posA {1:0, 3:1, 2:2, 4:3}posB {3:0, 1:1, 2:2, 4:3}算出的阈值分别是 M[1]1、M[3]1、M[2]2、M[4]3bucket 前缀和累加得到 [0, 2, 3, 4]完全一致。这个“先把每个元素的两个位置取最大再按阈值求前缀和”的思路其实是频率计数法和位运算法的共同内核后面你看完另外两种解法会更容易串起来。2. 三层解法暴力 → 计数 → 位运算2.1 暴力解法每走一步重新开集合最容易想到的做法当然是每个 i 都把两边的前缀重新收集一遍vectorint solve(vectorint A, vectorint B) { int n A.size(); vectorint ans(n); for (int i 0; i n; i) { unordered_setint sa, sb; for (int j 0; j i; j) { sa.insert(A[j]); sb.insert(B[j]); } int cnt 0; for (int v 1; v n; v) { if (sa.count(v) sb.count(v)) cnt; } ans[i] cnt; } return ans; }这个写法适合拿去验证思路但复杂度是 O(n²)如果 n 能到 10^5 级别就完全没法用。而且它每次都把前面的元素重新扫一遍明显做了大量重复劳动。作为初学者先写出暴力再优化是正常的路径但别在面试里止步于此。2.2 频率计数法把“出现两次”当成“双方都见过”暴力的问题在于重复构建集合。能不能一边前进一边维护“当前公共元素个数”可以而且代码短到让人不敢相信。核心观察还是基于排列性质每个数字 x 总共会出现两次一次在 A、一次在 B。如果我们用一个 freq 数组记录扫描过程中见过的次数那么“freq[x] 从 1 变成 2”的那一刻就意味着 x 在 A 和 B 里各自已经见过一次也就是它正式成为“前缀公共元素”。class Solution { public: vectorint findThePrefixCommonArray(vectorint A, vectorint B) { int n A.size(); vectorint ans(n), freq(n 1, 0); int common 0; for (int i 0; i n; i) { if (freq[A[i]] 2) common; if (freq[B[i]] 2) common; ans[i] common; } return ans; } };可能有细心的读者会问如果 A[i] 和 B[i] 刚好是同一个数 x那这一轮里 freq[x] 可能被连续加两次会不会把 common 加重复不会。因为 x 总共只有两次出现机会freq[x] 从 0 到 2 只会“穿越”一次 2。就算同一轮内连续加两次要么第一次从 1 到 2 触发一次 common第二次从 2 到 3 不再触发要么第一次 0 到 1 不触发第二次 1 到 2 触发一次。总之同一轮至多触发一次不存在重复计数。这个解法的时间复杂度 O(n)空间 O(n)。它足够通过题目也是很多官方题解里的标准答案。它不需要任何位运算知识但对理解“什么时候一个元素进入公共集合”这个语义特别有帮助。2.3 位运算解法一个整数装下整个集合接下来就是正题。既然每个数字只有“出现过/没出现过”两种状态那为什么不直接用二进制位来表示思路是这样开两个 64 位整数 maskA 和 maskB把数字 v 映射到第 v 个二进制位。扫描到 A[i] 时把 maskA 的第 A[i] 位设为 1扫描到 B[i] 时同理。因为前缀只会扩张、不会收缩所以用按位或 | 累积即可。两边都扫完当前元素后maskA maskB 的每一个置 1 位就代表一个“两边都出现过”的数字统计这个 AND 结果里有几个 1就是 C[i]。class Solution { public: vectorint findThePrefixCommonArray(vectorint A, vectorint B) { int n A.size(); vectorint ans(n); unsigned long long maskA 0, maskB 0; for (int i 0; i n; i) { maskA | 1ULL A[i]; maskB | 1ULL B[i]; ans[i] __builtin_popcountll(maskA maskB); } return ans; } };对照之前的例子用二进制看每一步发生了什么位从低位开始编号编号就是元素值imaskAmaskBmaskA maskBpopcountC[i]00b00100b10000b00000010b10100b10100b10102220b11100b11100b11103330b11110b11110b111144我第一眼看到这种写法的时候最惊讶的点在于一个集合运算被压缩成了两次 OR、一次 AND、一次 popcount全是 O(1) 的机器指令。集合操作的复杂度从“取决于集合大小”直接降成常数这种压缩感就是位运算最大的魅力。3. 手写实现核心代码之外的细节3.1 为什么必须是 unsigned long long 和 1ULL写 C 版本时有一个容易翻车的点位移运算符的左操作数类型。如果不小心写成1 A[i]这里的 1 是 int而 A[i] 最大可以到 50。在主流平台上 int 是 32 位左移 50 位属于未定义行为轻则结果诡异重则直接错得一塌糊涂。所以必须写成1ULL A[i]让整个表达式基于 64 位无符号整数运算。用 unsigned 而不是 signed long long 也有讲究。signed 类型左移把符号位移进去同样是未定义行为而无符号整数的移位语义完全由标准定义用起来没有坑。理论上这题 n ≤ 5064 位完全够用实际上你会希望养成这个习惯以后遇到 n 在 60 左右的问题也不会踩雷。3.2 Python 和 Java 的对照写法Python 版最简洁因为 Python 的 int 是无限精度的根本不用担心溢出class Solution: def findThePrefixCommonArray(self, A: List[int], B: List[int]) - List[int]: ans [] mask_a mask_b 0 for a, b in zip(A, B): mask_a | 1 a mask_b | 1 b ans.append((mask_a mask_b).bit_count()) return ans注意int.bit_count()是 Python 3.10 才引入的如果你还在用老版本环境可以退而求其次用bin(mask_a mask_b).count(1)不过那样常数会大一些LeetCode 上一般两种都能过。Java 版则要记得在1后面加 L否则1 A[i]在 A[i] ≥ 31 时就会溢出class Solution { public int[] findThePrefixCommonArray(int[] A, int[] B) { int n A.length; int[] ans new int[n]; long maskA 0, maskB 0; for (int i 0; i n; i) { maskA | 1L A[i]; maskB | 1L B[i]; ans[i] Long.bitCount(maskA maskB); } return ans; } }3.3 popcount 到底是怎么数出 1 的个数的__builtin_popcountll是 GCC/Clang 提供的内建函数在支持 POPCNT 指令的 CPU 上编译器会直接把它换成一条硬件指令所以速度极快。在不太老的 x86 和 ARM 处理器上这基本就是 O(1)。Java 的Long.bitCount走的是另一条路用一组精心设计的掩码把 64 位整数的二进制位并行分组相加也就是常说的 SWAR 技巧。这个算法不需要任何特殊硬件支持纯位运算就能在常数时间内算出结果是位运算入门的进阶读物值得以后单独研究。Python 的bit_count底层也是类似的思路只不过由 C 实现对使用者透明。搞清楚 popcount 的底层逻辑有个实际好处以后你在面试里手写位运算时如果面试官不允许用内置函数你也知道可以用循环一位一位数或者写出 SWAR 那套四行代码。多数情况下直接用内置函数就够但知道原理会让你更有底气。4. 什么时候该想到位运算三个信号4.1 从 2657 反推出来的判断清单很多人刷题时想不到用位运算不是不会语法而是缺少“触发条件”。我做完这道题后总结出三个信号以后遇到类似的题目可以先对照一下信号一值域是小范围整数。元素是 1 到 n 的排列或者 0 到 n-1 的排列每个值都能唯一对应一个二进制位。这是位图bitmap最理想的使用场景因为“值 → 位”的映射是天然的一对一。信号二要反复求两个集合的交集、并集、差集而且集合是单调变化的。这道题里的前缀集合只增不减所以 OR 累积就够了不需要考虑清位的问题。如果你遇到动态增删元素的状态维护位运算也同样能做只是还要配合按位取反和按位与来“删除”稍微复杂一点点。信号三每个元素只需要记录“有/无”这种布尔状态。不需要计数、不需要顺序、不需要重复次数那就该考虑压缩。一个 64 位整数可以装下 64 个布尔值这比开一个 bool 数组更省空间bool 数组在 C 里通常是 1 字节一个而且操作从“遍历数组”变成“一条指令”。这三个信号同时满足时位运算基本就是最优解之一。即使不满足位运算也常常能给出一个巧妙的替代思路比如很多题目里的异或去重、状态压缩 DP本质都是在利用“二进制位天然表达布尔集合”这个特性。4.2 顺着 2657 往外延伸的练习方向如果你吃透了这道题接下来可以练几个同类型题目巩固手感LeetCode 349两个数组的交集把一个数组塞进 mask再遍历另一个数组查位最后把命中的位还原成数字。LeetCode 136只出现一次的数字所有数异或一遍成对的元素全部抵消落单的自然留下。这是异或最经典的出场方式。LeetCode 268丢失的数字异或或者数学求和都能 O(1) 额外空间解决。状态压缩类题目比如图论里的“访问所有节点的最短路径”用一个 mask 表示哪些节点已经访问过这是位运算从“工具”升级为“算法核心”的分水岭。练的时候有个技巧先把每个题用 set / bool 数组写一遍再用位运算重写一遍对比两版代码的差异。你会发现很多“用集合表达”的逻辑翻译成位运算后都变成同一套模式——OR 加元素、AND 求交集、取反加 AND 求差集、popcount 数个数。这个模式一旦刻进脑子里以后遇到集合类问题第一反应就会多一个选项。5. 常见错误与调试实录5.1 三个最容易翻车的类型陷阱把我在评论区、代码评审和日常刷题里见过的高频错误整理一下基本都集中在类型上第一C 里1 A[i]的 int 溢出。前面说过A[i] 50 时 1 是 32 位 int左移 50 是未定义行为必须写成1ULL。我亲眼见过有人本地跑小数据全对一提交到极端用例就 WA查了半天发现是位移越界。第二C 里__builtin_popcount和__builtin_popcountll用混。前者只接受 int你把 unsigned long long 传进去高位会被截断位运算的结果自然不对。64 位 mask 一律用 popcountll没有例外。第三Java 里1 A[i]写成 int 版本。Java 的 int 也是 32 位A[i] 到 31 就开始出问题必须1L A[i]。Python 用户没有这种烦恼但也别因此忽略其他语言里的类型问题。另外还有一类逻辑错误值域映射不一致。比如 A 那边用1ULL A[i]直接用元素值作为位编号B 那边却用1ULL (B[i] - 1)减一映射两边口径不同AND 出来全是 0排查时很容易忽略。我的建议是统一用元素值本身作为位编号宁可浪费第 0 位也别在减一映射上给自己添麻烦。5.2 边界用例自测清单写完代码别急着提交先拿几个能覆盖边界的用例过一遍用例AB期望输出说明最小规模[1][1][1]同一个值同位置出现顺序完全一致[1,2,3][1,2,3][1,2,3]每步公共数递增 1完全逆序[1,2,3][3,2,1][0,1,3]检查前缀交集不对称中间错开[1,2,3,4][3,2,1,4][0,1,3,4]末尾元素最后补齐这些用例跑通后再补两个随机生成的排列用暴力解法当“对拍器”比一下结果基本就稳了。我在本地练习的时候习惯写个几十行的小脚本随机生成排列后同时跑暴力版和位运算版一键比对。对拍是排查边界问题最有效的手段比肉眼盯着代码看强太多。5.3 如果 n 变大位运算还适用吗2657 的 n 上限是 50这也是这道题能用一个 64 位整数解决的前提。如果以后遇到类似的题但 n 到了几百甚至几千C/Java 里一个整数装不下可以退而求其次用std::bitsetC、BitSetJava或者自己用vectorunsigned long long手写一个分段位图把 64 位切成 64 个一组每个元素对应到 (所在组, 组内偏移)。Python 则一般不用慌因为它的 int 无缝扩展哪怕值到 1000 也照样1 1000只是位运算内部会变成多字运算常数略大。如果 n 到了 10^5 这种量级位运算就不再是首选了老老实实回到频率计数法O(n) 时间和 O(n) 空间已经足够优雅。这也是为什么写题解时不能只看“位运算写法很酷”就无脑用而要说清楚它的适用范围值域小到能压进一两个机器字时它是最优解值域一大它就得让位给常规计数方案。最后说点个人体会。我第一次完整跑通这道题的位运算解法时有一种“原来集合还能这么玩”的开窍感。后来很长一段时间我遇到任何“只需要知道元素出现过没有”的题目都会先想想能不能用 mask 表达练得多了位运算就不再是一堆零散的语法点而是一套随时能调用的思维方式。2657 好就好在它够简单、够典型把“状态压缩”的动机和收益摊开给你看。如果你也想把位运算这块短板补上我建议从这道题开始把三种解法都写一遍再自己试着把 349 题用 mask 解一次那种“一通百通”的感觉很快就来了。