卡在《图灵完备》无符号小于这一关的人绝大多数不是不会接线路而是压根没想清楚两个8位字节凭什么能比出大小。我第一次打这关的时候凭直觉从最低位开始一级一级往上串比较器结果测试用例一跑A128、B127 这种最经典的例子直接翻车。后来把逻辑重新捋一遍才发现二进制比较和十进制比较是同一回事从权重最高的那一位开始谁先分出胜负就听谁的。这篇就把8位无符号数比较大小的两条主流路线完整拆一遍——逐位比较链、加法器借位法——顺带把原码、反码、补码这条线讲透因为等你推进到有符号小于那一关真正卡人的就是这套东西。刚打完8位加法器的新手、想补补码理解的老玩家下面的内容都能直接抄进自己的沙盒。1. 无符号比较的判定标准从最高位开始定胜负1.1 十进制里怎么比二进制就怎么比拿两个四位数举例3721 和 3699。我们会先看千位都是3打平再看百位7 比 6 大到此判定 3721 大后面的十位个位哪怕是 999 也翻不了盘。这个从高位往低位扫第一个不相等的位定胜负的过程就是字典序比较二进制只是把位权从 10 的幂换成 2 的幂规则没有任何变化。换成 8 位字节A 1000 0000B 0111 1111。最高位 a7 1、b7 0第一位就分出胜负了A B。你完全不用管后面 7 位是什么哪怕 A 剩下的全是 0、B 剩下的全是 1。这一点和十进制里千位大的数一定大是同一个道理高位的权重128比所有低位权重之和127还要大 1所以高位一旦领先低位加起来也追不回来。1.2 把比较写成一段能执行的状态机人眼扫一眼就出结果电路不会。我们得把上面那段直觉翻译成一个可以逐位执行的过程。引入两个状态量eq_so_far到目前为止扫过的所有高位是否全部相等初始为 1less当前是否已经判定 A B初始为 0。从最高位 i 7 往下扫到 i 0每一位做两件事less less OR (eq_so_far AND (NOT a_i) AND b_i) eq_so_far eq_so_far AND (a_i b_i)翻译成人话如果前面所有高位都还相等eq_so_far 1那么这一位上 A 是 0、B 是 1就说明 A 小把这个结论记进less同时更新eq_so_far一旦这一位不相等后面所有位的判断全部作废。这里有个细节值得留意less一旦被置 1 就永远保持因为后面eq_so_far已经变成 0后续的 OR 项都是 0不会把结论冲掉。反过来说如果某个高位判定 A B即 a_i1、b_i0eq_so_far变 0 而less保持 0结果就是不小于也是对的。1.3 从最低位开始串为什么必错我用一个反例说明。A 1000 0000128B 0111 1111127。最低位 a0 0、b0 1如果按照从低位开始比的逻辑这一位立刻判定 A B——可事实恰好相反。问题的根源在于低位的信息量根本不足以判断整体大小它只在所有更高位都相等的前提下才有效。而这条前提是级联的、单向传递的只能从高位往低位传。所以电路里比较链的数据流方向必须是 MSB → LSB第一位最高位单元的判断优先级最高越往低位优先级越低。接线时把顺序搞反测试用例里那些高位不同、低位恰好反过来的样本就会集体报错而且错得很隐蔽。1.4 换个视角A B 等价于减法产生借位除了逐位扫描还有一条数学味更浓的路子A B 当且仅当 A − B 的结果是负数。而无符号数在 8 位里没有负这种表示减出来的负结果会体现为借位borrow。只要你能算出 A − B 并观察到借位信号那么借位 1就是 A B。这一条和逐位比较是完全等价的命题只是实现路径不同前者靠逻辑链后者靠加法器。第 3 节会把借位法展开这里先记住这条等价关系——它是把比较问题转化为算术问题的关键也是后面理解有符号比较的基础。提示无符号小于是严格的A B 时输出必须是 0。这一点在两条实现路线上都会埋坑后面会专门讲。2. 逐位比较链把 8 个 1 位比较单元串起来2.1 单个比较单元需要几个信号把 1.2 里的那段代码切成片每一位就是一个独立的小单元。这个小单元需要的输入是a、b当前位参与比较的两个比特in_eq所有更高位是否全相等in_less所有更高位是否已经判定 A B。输出两个out_eq加上当前位之后是否依然全部相等out_less加上当前位之后是否已经判定 A B。六种有效情形列成真值表一目了然in_eqin_lessabout_eqout_less含义00xx00高位已判定 A B低位无需再看01xx01高位已判定 A B结论直接透传100010本位相等继续看低位100101本位 A B在此定胜负101000本位 A B在此定胜负101110本位相等继续看低位表里前两行是最容易被忽略的in_eq 0之后不管你这一位是什么输出都不再受a、b影响。这就是层级优先级的体现——高位的结论一旦产生低位就只剩透传的职责。2.2 从真值表到布尔表达式对着上面的真值表化简两个表达式都很短out_less in_less OR (in_eq AND (NOT a) AND b) out_eq in_eq AND NOT(a XOR b)逐条拆解它的电路构成。out_less由两部分做 OR一部分是in_less直通另一部分是高位全等 本位 A 是 0 本位 B 是 1这三个条件同时成立。out_eq则是高位全等和本位相等两个条件的与而本位相等就是NOT(a XOR b)也就是同或门。映射到基础门电路上NOT a1 个非门NOT a AND b1 个与门in_eq AND (...)1 个与门in_less OR (...)1 个或门a XOR b1 个异或门NOT(a XOR b)1 个非门in_eq AND NOT(a XOR b)1 个与门。满打满算约 7 个基础组件。如果你在搭建时把NOT a的中间结果引出来复用或者游戏里提供了三输入门、同或门能压到 4 到 5 个。8 位级联下来大致是 40 到 55 个组件的量级——心里有这个数遇到关卡限制时才知道该往哪个方向优化。2.3 级联的接法与首尾两端的特殊处理8 个单元从高到低排成一列第 7 位单元吃a7、b7第 6 位吃a6、b6依此类推。接线规则是固定的最高位单元i 7的in_eq接常量 1in_less接常量 0——这是整个链的初始状态目前还没有任何信息默认全部相等、尚未判定小于第 i 位单元的out_eq、out_less分别接到第 i−1 位单元的in_eq、in_less最低位单元i 0的out_less就是整条链的最终答案。中间任何一级接错方向结果都会诡异到让你怀疑元件本身坏了。我建议在搭建时给每一级起名字比如cmp_bit7、cmp_bit6出问题时一眼就能定位是哪一级的输入输出接错。2.4 用或归并替代优先链电路更简单上面这套级联方式需要传递两个信号eq和less连线数量翻倍。有一种更省连线的写法把所有 8 位的判断项直接归并less OR over i in [7..0] of ( prefix_eq(i) AND (NOT a_i) AND b_i )其中prefix_eq(i)表示比 i 更高的所有位全部相等。这样每一级只需要输出一个前缀是否相等的信号往下传最后用一个多输入或门把 8 个判断项汇总。在《图灵完备》里多输入门往往可以直接用所以这种写法在组件数量上通常更划算。两种写法的逻辑等价差别只在连线和门的复用方式。我的经验是第一次做这关用双信号级联版本因为它和 1.2 节的伪代码一一对应调试时心智负担最小等你要控制组件数量了再改成或归并版本。2.5 逐位链的实测细节在游戏里把这条链跑通之后有几个体感值得记下来。第一比较电路的输出完全由输入决定是纯组合逻辑不涉及时钟所以你可以把两个字节输入直接接到链上输出的 1 位信号立刻稳定不需要额外的时序控制。第二级联意味着传播延迟会累加8 级下来延迟比单个门大不少如果这条链后面还接了一堆组合逻辑又放在高频率时钟下用就要留意整条路径的延迟能不能在一个时钟周期内走完。第三逐位链的最大好处是可扩展16 位比较就是把这套单元再串 8 级32 位串 24 级逻辑一个都不用改。3. 加法器借位法元件少但有个必踩的坑3.1 A − B A (~B) 1 是怎么来的8 位加法器只能做加法怎么做减法靠补码。这里提前用一下第 4 节会详细推导的结论按位取反加一等于取相反数。~B 255 - B 因为 B ~B 恒等于 0xFF即 255 ~B 1 256 - B ≡ -B (mod 256) A ~B 1 A - B (mod 256)也就是说把 B 的 8 个比特全部取反再把最低位的进位输入cin拉成 1加法器算出来的就是 A − B 在模 256 意义下的结果。这一步不需要额外理解什么新东西就是把取反加一直接搬过来用。3.2 进位输出代表什么借位的反相关键问题来了加法器的输出里哪一个信号能告诉我们 A 和 B 谁大答案是最高位的进位输出cout而且要反过来看。设 A 和 B 都是 0 到 255 之间的数。我们算的是A (256 - B)如果 A ≥ B那么结果 ≥ 256必然产生进位cout 1如果 A B那么 A − B ∈ [−255, −1]加上 256 之后落在 [1, 255]不到 256cout 0。所以A B ⟺ cout 0 A ≥ B ⟺ cout 1最终输出就是less NOT cout一个非门搞定。这条线路的组件消耗非常低8 个非门把 B 取反一个现成的 8 位加法器一个非门取反进位——比逐位链少了一大截。3.3 忘记加一会错在哪等于情况直接翻车这是借位法最经典的坑我在第一次实现时就踩了。假设你图省事不接那个cin 1直接算A ~B会发生什么取 A B 5 试一试。~5 1111 1010 2505 250 255255 小于 256没有进位cout 0。按照less NOT cout的判据你会得到A B但事实上 A 和 B 相等。再看极端情况 A B 0~0 2550 255 255同样cout 0又误判成 A B。换言之只要两个数相等不加一就会全部误判为小于。加上这个一等于情况就对了5 250 1 256产生进位cout 1判定不小于正确。这个1不只是形式上的补码要求它实打实地承担了把相等从小于里排除出去的职责。3.4 那个 1 从哪里来cin 的三种接法道理清楚了工程上的问题还在1这个 1 接到哪如果你是自己用全加器级联搭的 8 位加法器最低位全加器的cin引脚本来是接地常量 0的那么直接把它改成常量 1 即可最省事。如果加法器已经被你打包成了自定义组件、引脚封死在内部那有三个可选做法在沙盒里另存一个8位减法器组件内部结构照抄加法器只把最低位的cin拉到 1之后比较、减法都复用它放弃cin改成先算A ~B再单独接一个加一的小电路比如把最低位接一个半加器或者用一个带进位的 8 位加法器把第二个操作数设成常数 1直接搭 9 位加法器多出来的那一位专门用来观察进位避免进位信息在别处被吞掉——这种做法最稳但最费组件一般用不上。注意如果你选了另存减法器这条路记得把加法器和减法器命名区分清楚。我见过有人把两个组件混着用测了半天发现是拿加法器当减法器测的。3.5 两条路线怎么选一张表说清对比维度逐位比较链加法器借位法依赖的前置组件只需要基础逻辑门需要现成的 8 位加法器组件数量约 40 到 55 个约 10 到 12 个关键信号每级两个状态位只有进位输出一个相等情况处理天然只判严格小于必须记得接cin 1逻辑直观度高逐位对应中依赖补码理解扩展成 16 位再串 8 级逻辑不变需要 16 位加法器或分段处理常见错误级联方向接反忘记加一、进位取反漏掉我的建议是先把逐位链做一遍因为它能让你彻底理解高位优先这件事再用借位法做一遍体会一下补码带来的组件数量红利。这两条路各自跑通之后你对比较这个操作的理解会比单纯过关深一个层次。4. 顺手把原码、反码、补码捋顺4.1 原码最符合直觉但最难用原码的思路最朴素最高位当符号位0 表示正、1 表示负剩下的位存绝对值。−5 就是1000 0101符号位 1 加上 5 的二进制。人看着舒服电路用起来难受两个致命问题第一零有两个表示。0000 0000是 01000 0000是 −0同一件事占用了两个编码判断是否为零要多做一次比较。第二加减法不能统一。做5 (−3)时电路得先看两个符号位同号做加法、异号做减法还要比较绝对值谁大来决定结果符号。这意味着你得多做一套减法器、多一层判断逻辑硬件开销成倍。4.2 反码取反就能表示负数但还差一口气反码的规则是正数不变负数把绝对值部分按位取反符号位保持 1。−5 的反码就是1111 1010。这一步已经比原码进步了至少取反这个操作可以用一排非门直接实现不用查表。但两个老问题都没彻底解决零依然有两个表示0 是0000 0000−0 是1111 1111加法需要循环进位反码相加时如果最高位产生进位这个进位要绕回来加到最低位end-around carry电路上就得多一根回环线控制起来很别扭。4.3 补码取反加一为什么成立补码在反码的基础上再进一步负数 反码 1。−5 的补码是1111 1011也就是十进制的 251。取反加一这四个字被念了太多次但它的推导其实特别干净。设 x 是一个 8 位数x ~x 1111 1111 255 ~x 255 - x ~x 1 256 - x ≡ -x (mod 256)因为 8 位运算天然是模 256 的运算超过 255 就绕回来所以~x 1和−x在模 256 意义下完全等价。这不是什么约定俗成的技巧而是模运算下的恒等式。取反加一之所以有效是因为它恰好构造出了 256 的补数。补码带来的三个好处零是唯一的0000 0000表示 01111 1111即 −1不再是零天然没有 −0 这个概念减法统一成加法A − B直接算A (~B) 1电路上不需要减法器第 3 节已经用过了范围不对称8 位补码能表示 −128 到 127因为1000 0000被分配给 −128没有对应的 128。顺便把从补码求原码的路径也说清既然−x的补码是~x 1那么对补码再取反加一就回到原数。所以看到1111 1011想还原成十进制先取反得0000 0100加一得0000 0101是 5前面符号位是 1所以是 −5。这套来回转换的路径在调试有符号比较电路时天天要用。4.4 有符号比较的核心技巧把最高位翻过来现在进入真正有意思的部分。有符号小于这一关如果照着无符号的思路硬做会遇到一堆麻烦负数在补码里是看起来很大的数值比如 −1 是 255逐位比较的结果全乱套。但有一个极其优雅的技巧把两个数的最高位都翻转然后按无符号方式比较。signed_less(A, B) unsigned_less(A XOR 0x80, B XOR 0x80)为什么有符号数的顺序是-128, -127, ..., -2, -1, 0, 1, 2, ..., 126, 127给每个数加上 128在 8 位里加 128 等价于翻转最高位顺序变成0, 1, 2, ..., 126, 127, 128, 129, ..., 254, 255正好就是从 0 到 255 的自然顺序。翻转最高位本质上是一次顺序重排把有符号的序映射成无符号的序然后用你已经搭好的无符号比较器就行了。用表格验证几个关键点有符号 AA 的补码A XOR 0x80有符号 BB 的补码B XOR 0x80翻转后比较结论−11111 11110111 111110000 00011000 0001127 129−1 1正确−1281000 00000000 00001270111 11111111 11110 255−128 127正确00000 00001000 0000−11111 11110111 1111128 127 不成立0 −1正确跨越零点、跨到极值、负数之间比较三种情况都对。这个技巧在硬件里实现起来只需要 8 个异或门其中 7 个可以省掉只翻转最高位那一根线。4.5 另一条路符号位异或溢出位如果你执意要走减法判符号这条路线会撞上一个陷阱在有符号运算里减法结果的符号位并不能直接反映大小关系因为结果可能溢出。举个例子A 127B −1。A − B 128超出 8 位有符号范围结果变成1000 0000即 −128符号位是 1看起来像A B但事实是 A B。正确的判据是符号位 SF 与溢出位 OF 的异或signed_less(A, B) ⟺ (SF XOR OF) 1其中溢出位OF可以用最高位的进位来判断OF c7 XOR c8c7是最高位全加器的进位输入c8是它输出的进位。两个不相等就说明发生了有符号溢出。这套判据是通用处理器的标准做法但在《图灵完备》里用 4.4 节的翻转最高位技巧显然更省组件——多搭一条溢出判断链纯粹是给自己找事。5. 在游戏里调通比较器我踩过的几个坑5.1 先确认关卡要的是小于还是小于等于这关的输出定义必须在动手前确认清楚。无符号小于是严格的A 和 B 相等时输出 0。而有些场景比如判断是否需要进位用的是两者差一个非门。我在测试时出过一次乌龙逐位链本身没问题是关卡输出的定义我记错了白调试半小时。判断方法很简单拿两个相等的输入试一次看关卡提示要求的输出应该是什么。这一步花 10 秒钟能省掉半小时。5.2 字节内部的位序要看清楚《图灵完备》里的字节输入通常按低位在右、高位在左排列也就是 bit0 在最右边。级联比较链的时候最左边的位MSB必须接第一个比较单元依次往右传。如果你按直觉把最左边的位接到链条末尾结果会系统性地出错而且只在两个数的高位不同时才暴露低位数相同的用例全是通过的假象。我的做法是先用两根线把最高位单独引出来接到第一个单元确认无误后再批量接剩下的位。5.3 用穷举的思路设计测试用例关卡自带的测试用例覆盖不全我习惯自己过一遍关键样本。下面这张表是我每次做比较电路都会跑的清单AB期望 less考察点000相等情况借位法最易错点011最小值对最小值加一100小于关系反过来的情形121相邻值1271281最高位首次出现差异12812701.3 节的反例检验级联方向2542551接近上界2552550最大值相等25500全 1 对全 002551全 0 对全 1这 10 个样本把相等、相邻、跨界、极值四类边界全盖住了。如果这 10 个都过剩下 6 万多个组合基本不会出问题——因为比较电路是纯组合逻辑没有状态残留不存在跑一会儿才出错这种情况。5.4 组件数量超限时先压非门有些关卡会对组件数量设上限这时候优化顺序很重要。我的优先次序是先去复用。把重复的 1 位比较单元打包成自定义组件8 份实例共用一套定义数量统计通常直接降下来再压非门。逐位链里NOT a、NOT(a XOR b)各用一个非门如果游戏里提供了带反相输出的门或者能把a XOR b换成同或门能省 8 个左右最后考虑换方案。如果数量还是超直接切到加法器借位法那条路天生就省一半以上组件。提示不要在组件数量上死磕到牺牲可读性。电路搭得一团乱后面改 16 位、32 位的时候会付出更大的代价。5.5 组合逻辑的稳定性与看起来像时序问题的假象比较电路本身不涉及时钟但它经常被放进更大的系统里和寄存器、时钟一起工作。这时候出现的偶发错误往往不是比较电路算错了而是整条路径延迟太长数据还没算完就被时钟采样走了。排查方法是把时钟调慢看错误是否消失。如果消失就是时序余量不够需要在比较结果输出后加一级寄存器打拍或者优化关键路径。这个经验在游戏后期搭 CPU 的时候特别有用我在做跳转指令的条件判断时就是靠这个方法定位到问题的。6. 这套比较逻辑还能迁移到哪6.1 日期比较年月日就是多级高位优先日期比较大小是日常开发里的高频需求它的逻辑和 8 位比较一模一样。年月日三个字段的权重依次递减比较规则就是逐级向下先比年 → 年相同再比月 → 月相同再比日发现没有这就是 1.2 节那个状态机的翻版eq_so_far在年是是否同年然后传递到月、传递到日。如果再加上时分秒就是六级级联对应电路里的六级比较单元。很多人在写日期比较时习惯把所有字段转成一个时间戳再比大小从结果上看是对的但从原理上看逐字段比较才是更本源的做法——时间戳只是把逐级比较的结果预先编码成了一个数值。这也解释了为什么时间戳能这么设计它本质上就是把多维的高位优先顺序编码成了一维的数值顺序和补码把有符号顺序映射成无符号顺序是同一种思路。6.2 字符串的字典序字符就是位字符串按字典序比较同样是从第一个字符开始比遇到不相等的就定胜负。C 语言里比较浮点数要用专门的判断方式但字符串比较反而简单因为它天然是逐元素的。这里的元素是字符的编码值两个字符比大小就是两个数值比大小本质上是同一套逻辑换了个容器。有意思的是字符串比较里也有提前终止的概念——一旦某一位分出胜负后面的字符完全不用看。这和电路里in_eq变成 0 之后低位直接透传是同一个优化思路。6.3 浮点数为什么不能直接按位比浮点数是符号 指数 尾数的分段表示不具备高位权重比所有低位之和还大这个性质。指数部分增加 1数值直接翻倍而尾数部分全部拉满也才接近 2 倍。所以浮点数的位序和数值序不对应直接按位比较会得出完全错误的结果。正确的做法是分情况处理先看符号两个都是正数时按指数优先、尾数次之比较两个都是负数时结果要反过来一正一负则正数大。这个流程和 4.4 节里先把有符号序映射成无符号序的思路是一致的——遇到表示形式和数值顺序不一致的情况先做一次映射再比较。顺带一提浮点数里还有个容易被忽略的问题NaN和所有值比较都不相等包括它自己。这也是表示形式决定比较语义的典型例子。6.4 从 8 位扩到 16 位、32 位游戏里的16位无符号小于关卡其实就是把 8 位比较器当成一个单元再往上搭一层逐位链的方案直接再串两个 8 位单元把低 8 位的in_eq、in_less接到高 8 位对应输出上逻辑一行不改借位法方案需要 16 位加法器或者把高 8 位和低 8 位分开算低 8 位的进位输出接到高 8 位的cin上再取最高位的进位取反。两种扩展路径的共同点是分层复用先把 8 位做扎实再用它拼更大的。这也是《图灵完备》这款游戏真正想教的东西——从与非门开始一层一层往上抽象最后搭出一个能跑程序的处理器。8 位比较器只是这条路上的一小步但高位优先、一旦决定就锁死这个思想会一直跟着你走到指令译码、跳转判断、甚至操作系统的调度逻辑里。提示如果你打算继续往 CPU 方向搭建议把比较器封装成带明确命名引脚A、B、Less的独立组件后面写条件跳转指令时直接拖进来用别再重搭一遍。我个人的习惯是每做完一个组件就在沙盒里存一份起个能一眼看懂的名字。因为等你搭到十几层抽象的时候回头翻这个模块到底是干嘛的所花的时间往往比重新搭一个还长。比较器这种基础件值得在最开始就把它做干净。