在《图灵完备》Turing Complete里一路搭到算术章节你大概率会撞上8 位无符号数比较大小这一关给你两个 8 位输入 A 和 B要求输出一个 1 位信号告诉后面的电路 A 到底是不是比 B 小。刚看到题面的时候我心想这不是送分题吗比较大小而已日常生活里一天要做几百次。结果真到了画布上才发现手边只有逻辑门、加法器、取反器和大把的导线没有任何一个现成的 或者 符号可以拖。这一关真正难的地方不在于比较这个词本身而在于你必须用二进制运算的视角把谁大谁小翻译成电路能算出来的东西。顺带说一句这一关也是整个游戏里第一次逼着你去认真理解补码、反码和原码到底是怎么回事——前面加减法你可能靠直觉就蒙过去了到了比较大小不理解补码就真的寸步难行。这篇东西我打算按我自己的实操顺序写先把关卡要求拆干净再把补码这一套底层逻辑讲透然后一步一步在游戏里把电路搭出来最后把我踩过的坑和测试用例整理成表。不管你是刚玩到这一关的新手还是老朋友想回来复习一下补码应该都能捞到点东西。整篇不涉及具体版本的界面细节核心逻辑在任何一个版本里都通用。1. 关卡拆解8 位无符号数比较到底难在哪1.1 先把输入输出和语义定清楚动手之前一定要先把题目到底要什么写清楚这一步偷懒后面全是返工。这一关的接口通常是这样两个 8 位输入端口我习惯叫 A 和 B一个 1 位输出端口叫小于或者 out。语义是当 A 的数值小于 B 的数值时输出 1否则输出 0。重点在于无符号这三个字——8 位全 1 也就是 255 是最大的数不存在负数的概念比特串1111 1111就是 255不是 -1。很多人第一次卡住就是因为脑子里默认了最高位是符号位看到1000 0000就下意识觉得是 -128。在这个关卡里它是 128。是不是无符号直接决定了最高位的角色无符号数里最高位只是一个普通的数值位权重是 2 的 7 次方即 128到了有符号数里它才变成符号位权重是负的 -128。这个差别后面会反复出现现在先记住就行。还有一个容易忽略的点输出要求是小于而不是大于等于或不等于。这几个条件之间是可以互相推导的但输出极性的细节抄错一位整个电路就会全反。我的习惯是先在纸上写一行注释out 1 当且仅当 A B。1.2 三条可行路线为什么我选了减法借位理论上这一关至少有三条路能走通我把它们摆在一起对比一下你就明白为什么大多数人的最优解都是减法。第一条是逐位比较。从最高位开始一位一位比过去如果 A 的这一位是 0、B 的这一位是 1那不管低位是什么A 一定小于 B直接定结果如果这一位 A 是 1、B 是 0那 A 一定大于 B只有两位相同才继续往下看。这个思路特别符合人的直觉逻辑上也完全正确但落到电路上就是一个 8 级串联的状态机需要维护目前是否已经分出胜负和当前结论两个状态门数和连线复杂度都不低。它最大的价值是在理解层面实操层面不划算。第二条是桶形移位或者查表。思路是把 B 的每一位挪到特定位置去和 A 做与运算然后压缩出一堆标志位。这种做法在特定场景下很省门但在《图灵完备》里你需要搭一堆移位器反而更啰嗦。第三条就是减法借位算 A - B看有没有借位。有借位说明 A 不够减也就是 A B没借位说明 A ≥ B。这条路线的电路成本极低——你只需要一个 8 位减法器然后把它的借位输出取反或者直接用。这也是游戏提示里委婉暗示的方向。我实测下来的结论很明确减法借位是这一关性价比最高的方案门数少、延迟低、逻辑清晰而且这个用减法判断大小的思想在后面很多关卡和真实的 CPU 设计里都会反复用到。逐位比较值得你手推一遍加深理解但不必真的搭出来。1.3 判断借位这件事比想象中容易搞反这里先埋一个雷后面第 3 章会详细拆。减法器的输出标志位在不同元件、不同版本里可能叫法不同有的叫借位borrow有的叫进位carry而这两者的极性恰好是反的。借位为 1 表示 A B进位为 1 表示 A ≥ B。如果你接上之后发现结果整个反了九成不是你的电路错了而是你把这两种命名混了。稳妥的做法是搭完先别急着交卷喂两组数用探针看一眼确认极性再往下走。2. 从原码、反码到补码把减法变成加法的整套逻辑这一章是整篇的核心。你可能会问一个无符号数比较的关卡为什么要扯补码因为减法借位这条路本质上是把减法当成加法来算的而把减法变成加法的那套数学工具就是补码。不理解补码你就只能死记接上取反器再加个 1一旦遇到有符号比较、溢出判断就彻底懵了。2.1 原码人脑最舒服电路最难受原码是最朴素的表示法最高位当符号位0 表示正、1 表示负剩下 7 位存绝对值。比如 5 是0000 0101-5 是1000 0101正负只差最高位那一个比特。人看着舒服但电路用起来很难受主要是两个问题。第一加法规则要分情况讨论。同号相加直接加数值位异号相加就得先比大小、用大减小、再决定符号。这意味着电路里得塞一个比较器、一个减法器、一个符号判决逻辑一下就膨胀了。第二零有两个表示。0000 0000是正零1000 0000是负零。虽然数值上都是零但电路判断相等时得额外处理极其别扭。这两个毛病决定了原码基本只适合用在某些浮点数的阶码和尾数表示里不适合做通用整数运算。2.2 反码把减法拐了个弯但零的尴尬还在反码针对原码的第一个毛病做了改良负数的表示改成正数的所有位不含符号位按位取反。5 还是0000 0101-5 变成1111 1010。这样做的好处是负数参与加法时不用再单独设计一套减法规则加法器的行为更统一了。不过反码没解决问题只是缓解了问题。它最大的坑是循环进位用反码做加法时如果最高位产生了进位这个进位不能丢得绕回到最低位再加一次也就是所谓 end-around carry。电路上多一条反馈线时序上还容易出问题delay 会变长。更烦的是零还是有两个表示0000 0000和1111 1111判断等于零依然要处理两种编码。反码基本只作为理解补码的中间跳板而存在实际电路里没什么人用它。2.3 补码模运算视角下减法正式变成加法补码是全篇最重要的一环。它的定义特别简单负数的补码等于它的反码末位加 1。注意这里的末位进 1就是热搜里常说的那个说法——反码的最低位加 1而且这个 1 会沿着进位链一路传播。拿 -5 举例5 是0000 0101反码是1111 1010末位加 1 得到1111 1011这就是 -5 的补码。再看 -11 是0000 0001反码1111 1110末位加 1 一路进位1111 1110 1 1111 1111所以 8 位里全 1 就是 -1 的补码这个结论记熟特别有用。那补码为什么能省掉减法核心是模运算。你可以这样想一个 8 位寄存器就是一个容量 256 的时钟表盘指针走到 255 再往前走一格就回到 0。这个绕一圈的规则就叫模 256。在这个表盘上-5 和 251 走出来的位置完全一样因为 251 5 256正好绕满一圈。所以 A - B 在这个表盘上等价于 A (256 - B)写成 8 位就是 A 加上 B 的补码。于是减法器根本不用单独存在A - B A (~B) 1其中~B是 B 按位取反这一步就是反码那个 1 就是补码的末位进 1。你只需要一个 8 位加法器把 B 全部取反再把进位输入拉到 1减法就完成了。这就是电路设计的精妙之处——用一个加法器干了两件事。补码还顺手解决了双零问题0000 0000是唯一的零1111 1111现在被占用成了 -1。整个 8 位补码的范围是 -128 到 127一共 256 个数一个不多一个不少编码利用率是 100%。原码和反码都浪费了一个编码去表示重复的零这就是它们的硬伤。2.4 补码求原码两种手算姿势调试时用得上在游戏里用探针看到一串1111 1011的时候你得能瞬间判断它到底是 251 还是 -5这取决于你按无符号读还是有符号读。如果是有符号读法怎么从补码还原出真值有两个方法。方法一减一取反先减 1 得到1111 1010再把数值位取反得到0000 0101也就是 5符号位是 1所以是 -5。方法二取反加一对整串补码按位取反得到0000 0100再加 1 得到0000 0101同样是 5。两种方法结果一样本质是因为取反加一这个操作做两次就回到原点——求补和还原补其实是同一个运算这也是它优雅的地方。我个人的习惯是记一组锚点1000 0000是 -1281111 1111是 -11111 1110是 -2。有这三个点到手其他数在脑子里顺着排就行比每次减一取反快得多尤其在调试有符号比较的时候能省下不少时间。2.5 同一串比特两种读法这是理解比较的关键写到这里必须把这一章最重要的结论点出来同一串 8 位比特按无符号读和按有符号补码读得到的是两个不同的数值但它们共用同一套加法电路。1111 1111按无符号是 255按有符号是 -11000 0000按无符号是 128按有符号是 -128。这意味着什么呢意味着你在这一关搭出来的减法器到了有符号比较那一关几乎可以原封不动地复用只是读取结果标志位的方式变了。无符号比较只看借位有符号比较还要加上符号位和溢出的判断。两关的硬件骨架是同一个差别只在最后几根导线——先理解这一点第 5 章你会轻松很多。3. 在《图灵完备》里把比较器真正搭出来原理讲完开始撸线。这一章我按实际动手顺序走一遍你可以对着抄。3.1 元件清单和布局规划先列一下用到的东西两个 8 位输入端口一个 8 位加法器有进位输入和进位输出引脚一个 8 位取反器如果没有就用 8 个单比特非门或者直接用按位取反元件一个进位常量若干导线最后是一个 1 位输出端口。有探针的话强烈建议放两个一个盯减法结果一个盯标志位。布局上我建议从左到右一条流水线输入 A 走上方总线直接进加法器的 A 端输入 B 走下方先过取反器再进加法器的 B 端加法器的进位输入接一个恒为 1 的常量进位输出接出来做判断。这样走线最干净后面调试也容易一眼看清信号流向。别小看布局我第一版把 B 的取反和 A 的走线绕在一起找错找了很久血的教训。3.2 从 8 位加法器改出减法器具体动作是这样把 B 的 8 位全部引到取反器上得到~B。如果你的元件栏里有8 位非门或者按位取反芯片直接用省 8 个门的位置。把~B接到加法器的 B 输入端。把加法器的进位输入Carry In接到一个恒定的 1。有些版本里这个引脚标着 Ci有的画在加法器底部位置不同但功能一样。加法器的 S 输出就是 A - B 的低 8 位结果进位输出Carry Out就是我们要用的标志位。这四步做完你其实已经把A - B A (~B) 1这条公式一条不差地实现了。这里有个小细节值得注意取反器必须是 8 位全取反一个都不能漏。我见过有人只取了低 4 位结果小数值测试全对、一到 128 以上就开始出错排查了半天才发现是漏了两个门。3.3 借位位的正确读法以及输出整形减法完成之后判断逻辑就在那一根进位线上。推导一下如果 A ≥ B那么 A - B 是个非负数8 位结果没有绕圈进位输出是 1。如果 A BA - B 会绕圈进位输出是 0。所以结论是进位输出为 0 就是 A B为 1 就是 A ≥ B。而我们要的输出是 1 表示 A B所以最终的输出逻辑就是取反out NOT CarryOut。如果你的元件库里减法器直接给的是借位信号那极性正好相反借位为 1 就是 A B直接接输出即可不用取反。这里就是第 1 章埋雷的地方。稳妥的验证方法是先接上探针喂 A 0、B 1看看标志位是 0 还是 1再喂 A 1、B 0看标志位有没有反转。只要两组数据对比一下极性立刻就清楚了。养成先小样本验证极性的习惯能帮你省掉大量整个电路全反了的调试时间。3.4 顺手加一个相等判断和结果整形如果你想让电路更完整一点可以从加法器的结果字节里再拉出是否为零的判断。结果为零说明 A 恰好等于 B。把小于和等于两个信号组合一下就能顺带得到小于等于大于等一连串条件后面写条件跳转指令的时候特别有用。判断一个 8 位字节是否为零标准做法是把 8 位全部或起来再取反或者用 8 输入或非门。在《图灵完备》里通常有现成的元件可用。这个小扩展不是本关的硬性要求但它是从会过关到会设计的分水岭——因为真实的 CPU 里比较单元从来不是只输出一个小于标志而是同时输出一堆条件码供后续指令挑选。4. 测试、验证与常见坑实录4.1 边界测试用例表这几组数一定要跑电路搭完别急着交先把下面这张表喂一遍。我把它整理成了 A、B、结果、进位、输出五列你对着探针看就行。ABA - B 的 8 位结果进位输出期望输出AB0001001255011011055010127128255011281271102550255100255101这张表覆盖了相等、相邻、跨界127/128 这条最容易暴露无符号和有符号混淆的问题、以及两端极值。特别说一下 127 和 128 这一组0111 1111和1000 0000它们在无符号读法下是 127 和 128正好一个卡在最高位翻转的边界上。如果这一组错了基本可以断定你是把最高位当符号位处理了。4.2 常见问题速查表现象最可能的原因排查动作结果整体反向把借位当成进位或漏了一个取反用 0 和 1 两组数验证标志位极性小数值对、大数值错取反器只覆盖了低位或位宽接错检查取反器是否是 8 位全接相等时输出 1输出条件写成了小于等于确认最终门是纯非门没混入其它项结果一直是 0进位常量没接到 1减法退化成加法检查 Carry In 引脚电平结果一直是 1输出端接了取反但标志位本身极性就是对的去掉最终取反再看偶发闪烁或时序异常组合逻辑里混入了未稳定的反馈线检查有没有意外的环回连线这张表是我自己踩坑踩出来的尤其是第一条和第四条几乎每个新手都会中一次。第四条特别隐蔽因为 Carry In 没接的时候电路照样能跑只是算出来的是 A ~B 而不是 A - B结果会错得很有规律容易让人以为是别的地方出了问题。4.3 几条不值钱但很省时间的经验第一永远先验证极性再验证数值。极性错了整个电路全反你会怀疑人生先确认标志位极性后面就只剩数值正确性的问题思路清晰很多。第二探针是你的好朋友。搭这种组合逻辑我习惯在关键节点都放一个探针尤其是加法器的输出字节和进位位。看一眼比在脑子里推十分钟快。第三从简单到复杂。别一上来就跑 255 这种极值先用 0 和 1 把通路跑通再逐级放大数值。极值出错往往是位宽或进位的问题先跑通基础通路能帮你快速定位问题到底在逻辑层还是在实现层。第四把这一关的减法器存下来。游戏里很多关卡都允许你复用之前做过的元件这个 8 位减法器在后面有符号比较、乘法、除法里都会用到存好能省不少重复劳动。5. 从无符号到有符号补码真正发力的一关5.1 有符号比较为什么不能只看符号位通关无符号比较之后下一个关卡大概率是有符号比较题目变成把两个输入当作补码有符号数来比较大小。这时候很多人第一反应是看结果的最高位不就行了最高位是 1 就说明结果是负数说明 A B。这个直觉在大部分情况下是对的但会在特定情况翻车。翻车的场景叫溢出。举个极端例子A -128B 127正确的结论是 A B。但如果直接算 A - B结果是 -255超出了 8 位补码能表示的范围硬件里实际算出来是0000 0001也就是 1最高位是 0。如果你只看符号位会得出A 不小于 B的错误结论。反过来的情况同样存在。所以有符号比较必须额外考虑溢出这就是它比无符号比较多出来的那一层复杂度。5.2 溢出标志的两种算法判断有符号溢出教科书上有两个公式我都可以给你。第一个是进位法溢出等于进入最高位的进位异或从最高位出去的进位。用符号记就是 V C7 XOR C8。落到电路中你需要一个 7 位加法器提供 C7再加上 8 位加法器给的 C8两个异或一下。这个方法严谨但多一个加法器稍微费点事。第二个是符号法我更推荐溢出等于两个加数符号相同、但结果符号与它们不同。用逻辑门写就是 V (A7 同或 B7) AND (S7 异或 A7)。对减法来说因为要处理取反公式稍有变形但思路一样。这个方法只需要几个逻辑门就能实现在《图灵完备》里非常划算。5.3 无符号和有符号只差一个多路选择器讲一个我自己觉得最优雅的实现方式。有符号比较其实可以这样拆先算符号差异标志signDiff A7 XOR B7。如果这个标志是 1说明两个数一正一负那谁小一目了然——A 的符号位是 1A 是负数就说明 A 小直接输出 A7 就行结果和数值部分完全无关。如果这个标志是 0说明两个数同号同号相减绝对不会溢出所以这时直接看减法结果的符号位 S7 就行了S7 为 1 就代表 A B。把这两条合起来就是一个多路选择器out signDiff ? A7 : S7。是不是特别干净注意这里完全没有显式地算溢出因为同号看结果符号、异号看 A 的符号这个分支本身就已经把溢出的情况规避掉了。这个技巧我第一次看到的时候拍了下大腿因为它把复杂问题拆成了一个判断加一个选择门数少、思路也顺。对比一下就能看出补码的价值无符号比较只需要一个减法器加一根线有符号比较多了一个符号位异或和一个多路选择器但底层的加法器是同一个。这就是为什么我前面反复强调要理解补码——它不是某一道题的技巧而是贯穿整个游戏后半程的底层世界观。顺便提一句在真正的编程语言里整数比较和浮点比较也是两套逻辑。比如 C 语言里浮点数比较大小涉及到 NaN 这个特殊值任何和 NaN 的比较都会返回假判断逻辑比整数麻烦得多。但你会发现本质思路是共通的比较的核心永远是看差值的符号再处理那些让符号判断失效的特殊情况。理解了补码下的溢出再去看浮点数的这些规则理解成本会低很多。再往外延展一点如果你玩到后面的汇编和寄存器章节比较的结果通常不会马上用掉而是写进一个标志寄存器然后在条件跳转指令里被读取。那时候你会发现寄存器之间传来传去的不只是数据还有这些一位大小的条件标志它们决定了程序执行的走向。你现在这一关搭出来的小小的比较器就是后面整个指令集里条件判断的硬件地基。最后分享一个小习惯我搭完任何一块算术电路都会在画布上贴一行文字注释写清楚输入输出语义和使用的算法。这个习惯在《图灵完备》里看着有点多余但等你玩到十几层芯片嵌套的时候回头翻一个三天前搭的模块那行注释能救你一命。同样的道理这一关我给自己的注释就是out 1 当且仅当 A B算法8 位减法器 进位取反边界无符号读法最高位权重 128。写清楚这几行后面不管隔多久回来复用一眼就懂。