刷过某大厂 OD 机考 C 卷的人十有八九会撞见“出错的或电路”这道题。我第一次看到这个题名第一反应是又要画门电路图、找短路点结果把题读完之后发现核心还是老熟人位运算和集合判断。这篇文章不打算给你贴一堆官方题解我想说的是我是怎么把它从一个“电路题”翻译成“数组题”的以及 Java 实现里哪些地方容易翻车。准备过 OD 机考、或者想系统补一下位运算套路的朋友可以认真看看这部分内容。1. 剥掉“电路”外壳先看题面模型1.1 一张图理解或门的“一票通过”或门在数字电路里的规则很简单只要有一个输入是 1输出就是 1。你可以把它理解成一群人在投票只要有一个人举手主持人就记录“有人举手”。它对应到算法里就是对一堆整数做按位或运算得到的结果里每一个二进制位都反映着“这一位上有没有任何一个数贡献了 1”。这个特性非常重要因为按位或对“重复的 1”完全不敏感。举个例子数组[1, 2, 3]里1 是0012 是0103 是011它们的或结果是011。你如果偷偷把 3 改成 0结果还是011因为最后一位和倒数第二位分别有 1 和 2 顶着。换句话说一个输入出错后如果某个二进制位本来就有多个数同时贡献 1那么这一个数无论怎么变输出位的值都不会变。所以真正能被“错误输出”暴露出来的问题往往发生在那些只有一个数独占的二进制位上。只要独占位一变输出立刻跟着变。这也是整个题目的破局点。1.2 能被定位的错误藏在“独占位”里假设题目给你一个正确输出correct也就是把所有输入整数按位或之后的结果又给你一个实际观测到的错误输出wrong。现在告诉你输入数组里恰好有一个元素在参与或运算之前发生了错误它可能变大也可能变小问你哪些下标可能出错。我们逐位对比correct和wrong如果某个位从 1 变成了 0说明正确结果里这个位原本有 1但现在丢了。要丢掉这个 1必须是所有贡献这个 1 的元素都变成了 0。可错误元素只有一个所以这个位在正确数组里必须是“独占位”也就是说只有一个元素持有它。如果某个位从 0 变成了 1说明正确结果里这个位原本全是 0但错误后多出来一个 1。这只能解释成某个原本该位为 0 的元素被错误地变成了 1。因为原本所有元素该位都是 0所以这一条对任何元素都没有筛选能力。因此真正能帮我们锁定嫌疑人的是那些“从 1 变 0”的位。它们要求唯一的持有者必须就是出错的元素。而那些“从 0 变 1”的位只是告诉我们出错元素确实把某个原本不要的位带进来了但它没法缩小候选范围。这样翻译之后问题就清爽了统计每一个二进制位在数组里出现的次数再用正确输出和错误输出的差异去压缩候选集合。2. 核心解题思路位频统计 候选集合压缩2.1 统计每个 bit 出现的次数先做一个基本功统计所有整数在 31 个二进制位上分别出现了多少次。这里的 31 是因为普通int的最高位是符号位题目里输入通常是非负整数所以我们最多只需要关心bit 0到bit 30。int[] cnt new int[31]; for (int v : a) { for (int bit 0; bit 31; bit) { if (((v bit) 1) 1) { cnt[bit]; } } }有人可能习惯写if ((v (1 bit)) ! 0)这样也不是不行但v bit的写法更不容易被1 bit的最高位处理搞晕尤其当bit走到 30 附近时1 31在 Java 里会变成负数一不留神就出现诡异的判断结果。统计完频率之后cnt[bit]就告诉了我们这个位在数组中到底有没有人持有、有多少人持有。如果cnt[bit] 0说明正确输出这一位一定是 0如果cnt[bit] 1说明这一位是某个输入的独占位如果cnt[bit] 2说明这一位非常“安全”一个输入发生变化根本撼动不了输出。2.2 用 correct 和 wrong 的差异反推候选接下来初始化一个boolean[] possible数组长度是n全部置为true。它的含义是当前认为每一个下标都可能是错误元素。然后从低位到高位遍历所有 bit把correct和wrong对应的位取出来做比较。如果两个值相同说明这一位没有暴露出任何信息直接跳过。如果correct这一位是 1、wrong这一位是 0就要小心了。先把cnt[bit]拿出来检查如果cnt[bit] ! 1说明有多个人同时持有这个位一个人出错不可能让这一位从 1 变成 0所以直接判定无解。如果cnt[bit] 1说明这一位是独占位找到那个唯一持有者的下标holder然后把possible数组里所有不等于holder的位置全部置为false。如果correct这一位是 0、wrong这一位是 1说明错误元素引入了一个原本不存在的 1。由于correct这一位是 0意味着所有输入元素在这一位上原本都是 0所以任何元素都满足“把这一位从 0 变 1”的嫌疑不需要缩小候选集。多轮遍历之后所有possible[i]仍然为true的下标就是可能出错的位置。这个方法本质上是在做集合交集每一个“从 1 变 0”的位都把候选集合压缩到它的独占持有者身上连续多个这样的位会不断取交集直到剩下唯一一个或者无解。2.3 三个小例子把方法走一遍举个直观的例子。假设有数组a [1, 4, 2]它们转换成二进制分别是001、100、010正确输出correct 7也就是111。如果实际输出wrong 3也就是011说明第 2 位二进制的第 2 位权重是 4从 1 变 0 了。统计之后发现这一位只有下标 1 的那个元素4持有所以候选就是下标 1输出[1]。再看另一个情况如果wrong 6也就是110那么第 0 位从 1 变 0。这一位只有下标 0 的元素1持有候选就是下标 0。此时错误元素从1变成了0输出自然从111变成了110。再制造一个无解的情况把数组改成[3, 4]也就是011 | 100 111如果wrong 011则第 2 位从 1 变 0但这一位的 1 在数组里只有4一个持有者不这里3011没有第 2 位4100有所以cnt[2] 1候选下标 1。这个例子不算无解。无解的例子是[5, 6]也就是101 | 110 111如果wrong 011第 2 位从 1 变 0但5和6都持有第 2 位cnt[2] 2一个元素不可能同时让两个 1 消失直接返回空集合。通过这几个例子你应该能感受到这个方法不是靠猜而是靠“位级别的因果分析”一步步锁死嫌疑范围。3. Java 实现完整代码与边界说明3.1 可直接运行的 solve 代码把上面的思路落成 Java 代码核心方法如下。我习惯把所有位运算的判断都加上括号避免 Java 运算符优先级导致莫名其妙的问题。import java.util.*; public class FaultOrCircuit { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] a new int[n]; for (int i 0; i n; i) { a[i] sc.nextInt(); } int correct sc.nextInt(); int wrong sc.nextInt(); ListInteger ans findFaultIndex(a, correct, wrong); if (ans.isEmpty()) { System.out.println(-1); } else { StringBuilder sb new StringBuilder(); for (int i 0; i ans.size(); i) { if (i 0) sb.append( ); sb.append(ans.get(i)); } System.out.println(sb.toString()); } } static ListInteger findFaultIndex(int[] a, int correct, int wrong) { ListInteger res new ArrayList(); if (correct wrong) { return res; } int n a.length; int[] cnt new int[31]; for (int v : a) { for (int bit 0; bit 31; bit) { if (((v bit) 1) 1) { cnt[bit]; } } } boolean[] possible new boolean[n]; Arrays.fill(possible, true); for (int bit 0; bit 31; bit) { int c (correct bit) 1; int w (wrong bit) 1; if (c w) { continue; } if (c 1 w 0) { if (cnt[bit] ! 1) { return res; } int holder -1; for (int i 0; i n; i) { if (((a[i] bit) 1) 1) { holder i; break; } } if (holder -1) { return res; } for (int i 0; i n; i) { if (i ! holder) { possible[i] false; } } } } for (int i 0; i n; i) { if (possible[i]) { res.add(i); } } return res; } }这里我把无解情况统一返回空集合然后在main里输出-1。但不同题目对无解的要求可能不一样有的要求输出空行有的要求输出-1有的要求输出全部下标。所以代码里的输出格式只是参考真正考试时一定要先看题目要求。3.2 边界条件全一样、n1、数据范围边界条件最容易翻车必须单独测试。第一个边界是correct wrong。这时候说明虽然有一个元素变了但它变的位没有对或结果产生任何影响我们无法通过输出反推是谁。按照当前代码会返回空集合。因为确实没有足够信息定位输出空或-1是合理的。第二个边界是n 1。只有一个元素时correct就是这个元素本身wrong是它出错后的值。如果wrong ! correct那么这个唯一元素必然就是错误源。跑一下代码会发现假设wrong比correct多了一个位此时所有位都是0 - 1候选不会被压缩最终possible[0]为true正确假设wrong比correct少了一个位那么那个位必定是独占位持有者也是下标 0结果仍然正确。第三个边界是数组里有大量 0。如果数组是[0, 0, 0]正确输出是 0错误输出只要不是 0就一定是有个 0 被错改成了非 0。因为每个位都是0 - 1候选集合不会被压缩三个下标全部输出。这符合逻辑因为确实任何一个 0 都可能变成那个非 0 值。第四个边界是 int 最大值。比如数组里存在2147483647它的低 31 位全是 1统计频率时cnt会有一堆位变成 1。如果它出错多个独占位会同时从 1 变 0代码会把候选压缩到它自己。但如果这个数组里还有另一个数也持有某些位那些位就不是独占位可能直接导致无解。所以别小看数据范围该用long的题目一定用long该开 64 位的频数数组就开 64 位。3.3 时间与空间复杂度时间复杂度是O(31 * n)外层 31 个 bit内层遍历所有元素一次最后再遍历一次possible收集答案整体可以看作线性复杂度。对于n在十万甚至百万级别的输入这个性能完全扛得住。空间复杂度是O(n)主要花在possible数组上。如果你不想开这个数组也可以用整数位掩码来存候选集合但n超过 31 就无能为力了所以工程上还是老老实实用布尔数组最稳妥。4. 变体思路除自身外的或记住前缀后缀4.1 为什么变体题更常见有些批次的“出错的或电路”不会直接给你correct和wrong而是给你一个数组b其中b[i]表示“把数组a中第i个元素临时去掉之后剩余所有元素的按位或”。如果题目要求你根据这个b来反推错误或者让你输出这个b那就和我们前面讲的位频统计法不完全一样了。这种变体题的核心变成了高频地计算“除自己以外全部元素的或”。如果你傻乎乎地对每个下标i都重新遍历一次数组时间复杂度就是O(n^2)一旦n超过一万基本上就会超时。这时候需要使用经典的“前缀后缀”预处理技巧。我在机考和平时训练里都反复用到这个套路它和“除自身外数组的乘积”那类题非常像。你只需要提前把前缀或和后缀或都算出来后面每个位置的答案就能在O(1)时间内拿到。4.2 前缀后缀数组的构造前缀或数组pre[i]表示从a[0]到a[i]的按位或后缀或数组suf[i]表示从a[i]到a[n-1]的按位或。int n a.length; int[] pre new int[n]; int[] suf new int[n]; pre[0] a[0]; for (int i 1; i n; i) { pre[i] pre[i - 1] | a[i]; } suf[n - 1] a[n - 1]; for (int i n - 2; i 0; i--) { suf[i] a[i] | suf[i 1]; }构造完成之后如果要计算“除掉下标i之外所有元素的或”只需要取左边的前缀pre[i-1]和右边的后缀suf[i1]两者再按位或。注意处理i 0和i n-1的越界情况左边没有元素就视为 0右边没有元素也视为 0。for (int i 0; i n; i) { int left (i 0) ? 0 : pre[i - 1]; int right (i n - 1) ? 0 : suf[i 1]; int removeIResult left | right; System.out.println(removeIResult); }这个removeIResult就是去掉a[i]后的或。如果有人把这个结果存在数组里再和预期值比较那基本上就是在考这个知识点。4.3 用前缀后缀做“删除任意元素后的或”自测拿一个具体例子验算。假设a [1, 4, 2]前缀或数组是pre[0] 1 pre[1] 1 | 4 5 pre[2] 5 | 2 7后缀或数组是suf[2] 2 suf[1] 4 | 2 6 suf[0] 1 | 6 7去掉下标 0 的结果是suf[1] 6也就是4 | 2 6正确。 去掉下标 1 的结果是pre[0] | suf[2] 1 | 2 3正确。 去掉下标 2 的结果是pre[1] 5也就是1 | 4 5正确。你可以在本地上跑一遍这个用例如果发现输出和你手算的不一致多半是前缀后缀数组的下标搞混了。特别是后缀数组循环时从n-2开始很多人会写成n-1然后整个数组就废了。5. 双机位机考实战先保证环境再谈 AC5.1 双机位摄像头怎么摆既然题目强调“双机位”说明考试环境和普通刷题不太一样。正面机位一般要求拍到你的脸和屏幕侧后方机位要求拍到你的手部、桌面和屏幕显示器。说白了就是要证明没有人在屏幕外搞小动作。我的建议是提前开一个模拟环境把两个画面都调出来看一眼。侧后方机位特别容易把桌面边缘切出去等考试时你低头打草稿就会被判定为人脸离开画面。草稿纸不要用太厚太光滑的本子提前在镜头前举起正反面展示一下然后放在侧后方机位能拍到的区域。考试过程中尽量不要频繁低头看键盘哪怕你打字不熟也尽量保持头部在正面机位画面里。这些小细节看起来和算法无关但真要是因为机位不合格被判定成绩无效那比题目没写出来更冤。5.2 输入输出规范和自测清单双机位机考的代码评测和平时刷题平台没有本质区别一样要严格按输入格式读、按输出格式写。但考试时人会紧张容易忽略这些约定俗成的东西。我给自己定过一个自测清单每次提交前快速过一遍数组长度n是否为 0虽然多数题目不会给空数组但n 1的情况一定要测。题目说输出下标从 0 开始还是从 1 开始如果是下标从 1 开始最后收集答案时记得加 1。无解时输出空行还是-1不同批次要求不一样不能凭经验。如果有多个候选输出顺序是升序还是任意顺序尽量养成sort一下的习惯。使用Scanner会不会因为数据量大而变慢如果发现超时换成BufferedReader往往有奇效。所有数都是非负整数吗如果出现负数位运算的符号位问题会让31位统计失效需要特别小心。这些项目在提交前花两分钟自查一遍能避免大量因为格式或边界问题造成的罚时。6. 常见问题与排查实录6.1 位运算优先级和写法Java 里有一个很经典的坑运算符的优先级比低。如果你写if (correct (1 bit) 1) // 错误这行代码会先算(1 bit) 1再算correct boolean编译都过不了或者出现极其隐蔽的逻辑错误。正确写法是if (((correct bit) 1) 1)或者if ((correct (1 bit)) ! 0)记住位运算的每个操作数都要单独用括号包起来不要怕括号多代码可读性和正确性优先。另外右移对负数会把符号位带过来如果你需要用(v bit) 1来判断某一位最好确认数组里全部是非负整数。如果题目输入可能为负数那就要用(v bit) 1也就是无符号右移。不同题目对输入数据范围的描述不同我一般会直接看约束范围凡是没有明确说非负的我都会多留一个心眼。6.2 候选集合交集的处理坑我在第一次实现时曾经用int mask来存候选下标因为最多 31 位嘛还觉得自己挺聪明。结果题目里n可以到一万完全不是用整数位能解决的。后来改成布尔数组才稳妥。更隐蔽的一个问题是如果你发现某个1 - 0的位cnt[bit] ! 1应该直接返回空而不是继续循环。因为单个错误元素不可能同时让多个持有者的 1 全部消失哪怕后续碰到其它位也不能挽救这个矛盾。我一开始就是没有立刻返回继续走完所有 bit 后输出了一堆乱七八糟的候选样例都过不去。还有一点要注意如果correct和wrong只在0 - 1的位上有差异代码最终会输出所有下标。这可能让人疑惑但逻辑上是正确的因为确实无法区分是哪一个元素从 0 变成了 1。有的题目在这种情况会要求输出所有下标有的要求输出特殊值以题面为准。6.3 输出格式和超时隐患如果收集到的候选数量很大千万不要在循环里不断System.out.printlnIO 会成为瓶颈。哪怕n只有十万也建议用StringBuilder拼接完再一次性输出。格式方面行尾要不要加空格也要注意机考通常不检查行尾空格但为了稳妥我在输出时会在相邻元素之间加空格末尾不保留多余空格。如果题目要求无解输出空行那就在ans.isEmpty()时直接System.out.println()。如果要求输出-1就输出-1。这个看起来简单却是最容易因为惯性出错的地方。7. 从这道题延伸出去位运算题型的共同套路7.1 位运算题型速查“出错的或电路”表面上是个电路题实际就是一个位运算应用题。我在复盘时把常见的位运算题型整理了一个速查表每次遇到类似题目先往这些方向靠题目特征常用套路典型场景找唯一出现奇数次的元素异或抵消一个数组里只有一个数出现奇数次按位统计出现次数遍历每个 bit 记cnt判断某一位是否被多个元素持有删除一个元素后的聚合值前缀 后缀除自身外的乘积、或、与、异或子数组异或和前缀异或 哈希表统计异或为 0 的子数组数量子数组按位或结果去重集合滚动合并枚举所有子数组的或值位运算题最大的优点是状态空间有限最多也就 64 个 bit所以很多看似复杂的电路故障题拆到二进制位之后就变成了“找唯一持有者”的简单逻辑。只要把位频率统计和前缀后缀这两个基本功练熟大部分题都能很快有思路。7.2 一点个人体会我自己刷题有个习惯凡是题面里出现“电路、门、信号、短路”这类词都会先想想能不能抽成位运算问题。或者说只要看到“按位或、与、异或”这几个关键词就应该立刻警惕前缀后缀、频率统计这些套路。这道“出错的或电路”就是非常典型的代表外壳是硬件内核是数组和位运算。还有个小技巧考试时如果时间充裕建议在草稿纸上先把correct和wrong的二进制展开写出来一个位一个位对比。很多错误思考都是在脑子里想太久了落到纸上其实几秒钟就能看清楚。这也是我在双机位考试环境下最推荐的检查方式。