从原码到补码：从一个最朴素的问题，推导出计算机为什么这样表示负数

一、计算机为什么首先需要解决负数怎么表示先假设计算机只有 4 个 bit。4 个 bit 每一位只有 0 和 1 两种可能因此总共只有 2⁴ 16 种状态也就是从 0000 到 1111。如果只表示无符号整数事情非常简单0000 表示 00001 表示 10010 表示 2一直到 1111 表示 15。可是数学中的整数并不只有 0 到 15还有负数。例如我们不仅希望表示 3还希望表示 −3。这就产生了第一个问题一个只有 0 和 1 的系统应该怎样表示负数最自然的想法非常符合人的直觉既然平时写数字可以在前面加一个负号那是不是也可以专门拿一位表示正负于是我们规定最高位作为符号位剩下的 bit 表示数值大小。例如 4 bit 下3 表示成0011−3 表示成1011。最高位 1 表示负号后面的011表示 3。这就是原码的基本思想。它有一个明显的优点人很好理解。但计算机真正需要解决的问题并不是人能不能看懂而是计算机能不能方便地拿这些 bit 去计算二、如果负数只是加一个负号计算就会变得麻烦考虑最简单的运算3 (−3) 0按照原码3 是0011−3 是1011。如果直接把这两个 bit 模式交给普通的二进制加法器得到的是1110也就是原码下的 −6而不是 0。问题在于原码把一个数拆成了两部分符号和数值。计算机做运算时就必须额外判断符号两个正数相加可以直接加两个负数相加绝对值相加之后还要处理符号一个正数和一个负数相加要先比较两个绝对值的大小再决定做减法还是加法最后还要决定结果的符号。此外原码还有一个小毛病0 有两种写法。0000是 01000是 −0。同一个数有两种表示比较和判断都要多处理一种情况。也就是说原码虽然解决了怎么表示负数却没有解决怎样让正数和负数统一参与二进制运算于是我们需要换一个思路。不再先考虑怎样写出一个看起来像负号的 bit而是问能不能找到一个普通的二进制状态让它在加法中表现得像负数三、我们真正想找的是一个加起来等于 0的东西还是以 −3 为例。在普通数学里3 的相反数是 −3因为 3 (−3) 0。如果我们暂时不知道 −3 应该对应哪个 bit 模式就把它假设成某个状态 X。我们真正需要的条件是3 X 经过计算机的运算以后结果变成 0。问题来了4 bit 的计算机怎样才能变成 0这就要认真观察 4 bit 本身的特点。4 bit 一共只有 16 种状态最大的是1111也就是 15。如果在 15 上再加 1普通数学当然得到 16。但 16 的二进制是10000需要 5 个 bit而我们只有 4 个 bit。因此实际保存下来时最高位的那个 1 没有位置存放留下的只有0000。所以这里发生的并不是普通数学意义上的15 加 1 等于 0而是真实结果是 16只不过 4 bit 保存不下代表 16 的那个最高位最终留下的 4 个低位就是 0。这一点非常关键。因为我们由此得到了一个有用的性质在固定 4 bit 的计算中只要两个数相加的真实结果恰好是 16保存下来的结果就是 0。四、反推出 −3 的编码现在回到最开始的问题我们希望找到 −3 的编码 X使 4 bit 加法的结果为 0。最直接的办法就是让真实结果变成 16因为 16 写成二进制是10000丢掉最高位之后就是0000。因此要求3 X 16于是X 16 − 3 1313 的二进制是1101。所以如果采用这种固定 4 bit 的加法规则1101就可以承担 −3 的作用。注意这里有一个非常重要的区别。我们并不是说 13 −3这当然不成立13 仍然是普通数学里的 13。我们真正发现的是3 13 16而 16 放进 4 bit 后留下 0。所以在这个计算系统中13 对应的 bit 模式具有 −3 所需要的加法效果。这就是补码最核心的思想。一般化以后如果有 n 个 bit就一共有 2ⁿ 个状态。对于一个正数 A我们希望找到状态 X使得A X 2ⁿ于是X 2ⁿ − A所以负数 −A 的 n bit 补码本质上就是 2ⁿ − A 对应的那个 bit 模式。这个公式不是背出来的而是从我要让 A 和它的相反数相加后得到 0这个要求直接推导出来的。五、循环的意义到这里我们已经能解释补码了。但还可以继续追问为什么会出现超过 15 后又回到 0这样的现象4 bit 的机器只有 16 种状态0, 1, 2, …, 15。而我们仍然希望它能不停地做加法。加到 15 再加 1 时怎么办结果必须重新落回这 16 个状态中的某一个。处理方式其实不止一种。比如饱和运算是超出之后就停在最大值 15。但绝大多数通用硬件选择的是直接丢弃超出位宽的高位。这个选择好用是因为它有一个很好的性质丢弃高位等价于只关心结果除以 2ⁿ 的余数而加法、减法、乘法都和取余数相容乘法的验证见进阶篇二。也就是说先算再截断和先截断再算最后得到的低 n 位是一样的。于是 15 加 1 得到 0继续不断加 1就会出现0 → 1 → 2 → … → 15 → 0 → 1 → …这就是所谓的循环。下面这张图把 4 bit 的 16 个状态排成一个环图里可以看到从 3 顺时针走 13 步正好回到 0所以 13 对 3 来说就像 −3同一个位置的外圈读法无符号和内圈读法补码相差 16。这里的循环并不是说我们真的把整数数轴画成了一个圆更不是补码额外增加的一条规则。它只是描述这样一个事实在固定 n bit 的二进制系统中丢弃高位的加法状态会以 2ⁿ 为周期重复。这个周期性也正是为什么一个原本不在 0~15 中的负数可以用 0~15 中的某个状态来表达。这里的直觉描述后面的进阶篇会用群论给出严格的版本。六、加法逆元给这个做法起个名字到这里可以给刚才的做法起一个名字。所谓一个数的加法逆元就是另一个数使它们相加以后得到 0。在普通整数里1 的加法逆元是 −1因为 1 (−1) 0。在只有 16 个状态的系统里我们问同样的问题哪个状态和 1 相加以后经过固定 4 bit 的计算得到 0答案是 15因为 1 15 16低 4 位是 0。所以在这个系统里15 扮演了 −1 的角色。同理3 的逆元是 13。因此1111可以被解释成 −11101可以被解释成 −3。这并不是说普通数学中的 15 等于 −1而是说在这个固定位宽的加法规则中15 和 −1 具有相同的加法效果。这也引出理解补码时很重要的一点一个 bit 模式到底表示什么不仅取决于它本身还取决于我们采用什么解释规则。1111作为无符号数是 15作为 4 bit 补码表示 −1。bit 没有变变的是解释它的方式。这里只是直观的说法。为什么逆元一定存在、而且唯一进阶篇会用群论严格回答。七、16 个状态怎么分给正数和负数具体数字版既然 −A 对应 2ⁿ − A那 16 个状态怎么分给 0、正数和负数同一个状态其实可以有无穷多种整数读法比如1101读作 13、−3、29 都说得通它们彼此相差 16 的整数倍。所以需要约定一个读法区间。补码的约定是取 16 个连续整数−8 ~ 7每个状态恰好对应其中一个一般地n bit 取 −2ⁿ⁻¹ ~ 2ⁿ⁻¹ − 1。严格的理由见进阶篇 A.5。下面用 4 bit 把全部 16 个状态列出来状态无符号读法补码读法状态无符号读法补码读法00000010008−800011110019−7001022101010−6001133101111−5010044110012−4010155110113−3011066111014−2011177111115−1从表里可以直接看到几件事最高位为 0 的是 0 ~ 7最高位为 1 的是 −8 ~ −1。一般地n bit 补码范围是−2ⁿ⁻¹ ~ 2ⁿ⁻¹ − 1。负数比正数多一个−8 没有对应的 8。所以对 −8 取相反数会溢出因为 8 在 4 bit 里装不下。0 只有0000一种写法没有原码那样的 0 和 −0。最高位为 1 的状态补码读法比无符号读法小 16正好是 2ⁿ这就是第六节说的15 和 −1 效果相同、13 和 −3 效果相同。八、从减法看补码的价值假设要计算 5 − 3。如果计算机必须专门设计一个复杂的减法世界事情会比较麻烦。但现在我们已经知道 −3 的 4 bit 补码是1101所以5 − 3 5 (−3)计算机只需要做一次普通的二进制加法5 是0101−3 的补码是1101相加得10010。因为只有 4 bit最高位被丢弃留下0010也就是 2。所以 5 − 3 2。整个过程没有任何特殊的负数加法器。本质上只有一件事把负数编码成另一个状态让普通加法器去计算它。负数加负数也一样。计算 (−3) (−2)−3 是1101−2 是1110相加得11011丢掉最高位留下1011查第七节的表就是 −5。完全不需要判断符号、比较绝对值。溢出是什么样子。计算 7 1011100011000按补码读出来是 −8。加法器本身没有算错它只是老老实实保留了 8 的低 4 位1000。问题在于真实结果 8 超出了 −8 ~ 7 的范围解释回整数时就读错了。错的不是加法而是这个状态代表哪个整数这一步。这就是补码真正重要的地方。九、为什么取反加一成立反码的位置我们已经知道补码的本质是 2ⁿ − A。那为什么教材又说负数的补码等于对应正数按位取反再加 1这是因为取反再加一是计算 2ⁿ − A 的一种非常方便的二进制办法。下面是完整的推导只需要一步观察。任何一个 n bit 数 A和它按位取反的结果 ~A 相加每一位上都是一个 0 和一个 1也就是 0 1没有进位所以A ~A 11…1n 个 1 2ⁿ − 1移项~A (2ⁿ − 1) − A再加 1~A 1 2ⁿ − A这正是 −A 的补码。例如 4 bit 下3 是0011按位取反得110012再加 1 得110113。而 16 − 3 13两种方法结果一致。所以取反加一并不是补码的来源而是 2ⁿ − A 的一种便捷算法取反给出 (2ⁿ − 1) − A这只需要每一位翻转硬件上非常便宜再加 1补上差的那一个单位。关于反码。在我们的推导里反码 ~A (2ⁿ − 1) − A 是连接 A 与 2ⁿ − A 的中间形式。需要补充的是反码在历史上也曾经被独立使用过用反码表示负数的机器例如 CDC 6600做加法时需要把最高位的进位加回最低位循环进位并且和原码一样存在 00000和 −01111两个零。补码用丢弃进位取代了循环进位又消除了双零因此成为现代计算机的标准。所以更准确的说法是反码在现代硬件里已经被淘汰但它在推导里仍是有意义的代数中间量。十、补码的最高位符号与权重初学者常说补码的最高位是符号位。这个说法没错但更精确的说法是n 位补码中最高位的权重是 −2ⁿ⁻¹其余各位的权重和无符号数相同。例如 4 bit 的11011101 −8 4 0 1 −3这个读法有两个好处它解释了为什么最高位能当符号位最高位为 1 时−2ⁿ⁻¹ 的绝对值总比其余各位权重之和最大是 2ⁿ⁻¹ − 1大所以整体为负它给了一个不需要取反加一就能直接读出补码值的方法。所以补码的最高位既不是单独的符号也不是普通的权重而是一个负权重。符号位只是我们读数时的一种方便说法补码本身并没有切出一个符号。这和原码不同原码的最高位确实是独立的符号其余位是绝对值。十一、原码、反码、补码各自的价值走完整个推导这三个概念就不应该再是一张需要背诵的表格。原码最直接地解决了负数怎么表示一位符号其余表示绝对值。但它有双零并且正负数不能共用同一种加法规则。反码是把负数取成 (2ⁿ − 1) − A。它让加法更接近统一但仍有双零且加法时需要循环进位。补码取 2ⁿ − A单零加减法统一为同一个加法器只需丢弃进位。这里还要提醒初学者容易混淆的几点原码、反码、补码都是针对有符号数的无符号数没有这些概念它直接就是二进制表示补码不是由原码演变出来的。我们的推导只用到了无符号数的加法和 2ⁿ 的周期性从头到尾没有用过原码。所以真正应该记住的逻辑不是原码 → 取反 → 加一。而是想表示负数 → 希望负数能直接参与加法 → 寻找它的加法逆元 → 固定 n bit 后A 的逆元是 2ⁿ − A → 这就是补码。十二、模运算到这里模运算其实已经没那么可怕了。时钟类比12 点之后回到 1 点和我们前面的15 加 1 回到 0本质上是同一件事只是换了载体。所谓模 16就是把刚才固定 4 bit 的行为用数学语言描述出来。因为 4 bit 的计算只保留 16 个状态所以 16 和 0 在这个系统里结果相同两者相差一个完整的周期。同样15 和 −1 相差 16所以它们在这个系统里的加法效果相同。我们写成15 ≡ −1 (mod 16)这里的 ≡ 不应该理解成普通数学里的15 就等于 −1。它表达的是15 和 −1 相差 16 的整数倍因此在模 16 的运算中属于同一个等价类。所以模运算并不是为了把补码搞复杂。恰恰相反模运算是给固定 bit 宽度下高位丢弃、状态周期重复这个现象提供的严格数学语言。它也解释了为什么加、减、乘都能在补码上直接用同一套硬件完成这些运算与模 2ⁿ相容。除法是例外见进阶篇二。乘法的一个小例子(−3) × 2也就是110113×00102 26 16 10保留低 4 位得1010按补码读出来正是 −6。严格的验证见进阶篇二。总结以后再看到原码、反码、补码不要先背取反加一而是从头想一遍计算机只有有限个 bit因此只有有限个状态加法器丢弃高位超出范围就回到 0状态以 2ⁿ 为周期循环每个 A 都能找到一个状态 2ⁿ − A和它相加刚好跨过一个周期回到 0这就是 A 的加法逆元补码用它来表示 −A一个状态可以有无穷多种整数读法补码约定取 2ⁿ 个连续整数 −2ⁿ⁻¹ ~ 2ⁿ⁻¹ − 1由此得到表示范围真实结果超出这个范围就是溢出最后A ~A 2ⁿ − 1所以 2ⁿ − A ~A 1这就是取反加一同样的丢高位让乘法低 n 位也成立但除法需要另外的算法。整个过程可以浓缩成一句话补码不是从取反加一开始的取反加一只是得到补码之后的一种方便算法。补码真正的根源是固定 n bit 的有限加法系统中用 2ⁿ − A 表示 A 的加法逆元。这才是从白纸推导出原码、反码、补码的思路而不是死记硬背。其实这篇文章的核心问题只有一个当数字只有有限个状态时加法会变成什么样理解了这句话也就理解了补码。如果你想知道为什么这一切是必然的欢迎继续读下面的进阶篇它会用群论把上面的直觉全部严格化。进阶篇一用群论严格理解加法逆元、循环与补码阅读提示补码本身的内容在上面的总结处已经讲完这一篇是进阶内容不读也不影响理解。如果读起来觉得吃力不必强求可以先去学习离散数学或抽象代数中的群论基础主要是群的定义、同态和循环群这几个概念再回来读会顺畅很多。前面我们一直在用直觉 例子推导。现在把它放进一个严格的框架里你会发现循环、逆元、补码、模运算其实都是同一个结构的不同侧面。A.1 硬件加法器到底在算什么设位宽为 n机器的状态集合为S {0, 1, 2, …, 2ⁿ − 1}硬件加法器丢弃高位的行为用数学语言写出来就是a ⊕ b (a b) mod 2ⁿ注意这里的 ⊕ 是 S 上的一个新运算它不等于整数的加法 只是在结果没有超出范围时恰好与 一致。我们把这个系统记作 (S, ⊕)也就是数学里的 ℤ/2ⁿℤ。A.2 (S, ⊕) 是一个群群的定义只有四条我们逐条检查封闭性任意 a, b ∈ Sa ⊕ b 经过取模仍落在 S 中。这正是丢弃高位后状态仍在 16 个之内。结合律(a ⊕ b) ⊕ c a ⊕ (b ⊕ c)。这是因为先取模再相加、最后再取模和直接把三个数加起来再取模结果相同。单位元0 满足 a ⊕ 0 a。逆元对每个 a存在 a′ 使 a ⊕ a′ 0。当 a 0 时 a′ 0当 a ≠ 0 时取 a′ 2ⁿ − a因为 a (2ⁿ − a) 2ⁿ取模后是 0。第 4 条就是我们前面反推出来的补码公式现在它是群的公理的直接结论不再是凑出来的。群还有一个重要性质逆元是唯一的。设 x 与 y 都是 a 的逆元则x x ⊕ 0 x ⊕ (a ⊕ y) (x ⊕ a) ⊕ y 0 ⊕ y y所以哪个状态在加法里扮演 −3这个问题答案是唯一的4 bit 下 3 的逆元只能是 13没有第二种选择。补码不是人为约定的一种编码而是在要让硬件加法器正确工作这个要求下被逼出来的唯一答案。A.3 整数和状态之间的桥梁同态现在要回答一开始最让人别扭的问题13 和 −3 到底是什么关系定义映射 φ整数 → Sφ(k) k mod 2ⁿ它满足φ(a b) φ(a) ⊕ φ(b)也就是说先在整数里相加再映射等于先映射再在 S 里用 ⊕ 相加。这样的映射叫群同态。通俗地说同态就是翻译时不丢运算无论你先在整数世界里算再翻译成状态还是先翻译再在状态世界里算结果都一样。同态必然保持逆元φ(−a) 一定是 φ(a) 的逆元因为 φ(−a) ⊕ φ(a) φ(0) 0。于是补码的严格定义整数 −A 的补码就是 φ(−A) (−A) mod 2ⁿ。当 1 ≤ A ≤ 2ⁿ − 1 时它恰好等于 2ⁿ − A。例φ(−3) (−3) mod 16 13φ(13) 13所以 φ(−3) φ(13)。这就是13 不等于 −3但它们在加法里作用相同的精确含义它们是同一个像。同理φ(15) φ(−1) 15所以1111既可以解释为 15也可以解释为 −1取决于我们选择把哪个整数作为这个状态的代表。同态的核是所有被映到 0 的整数即 2ⁿ 的整数倍。两个整数 a, b 的像相同当且仅当 a − b 是 2ⁿ 的整数倍这正是第十二节里 a ≡ b (mod 2ⁿ) 的定义。所以同余号 ≡ 并不是凭空引入的记号它就是同态后像相同的另一种写法。A.4 循环循环群再看 1 这个元素不断用 ⊕ 加它自己1, 1⊕1 2, 3, …, 2ⁿ − 1, 然后再加一次 1回到 0第一次回到 0 恰好是加了 2ⁿ 次。我们说元素 1 的阶是 2ⁿ。由于这条链走遍了 S 的所有元素S 可以由 1 一个元素生成这样的群叫循环群。所以前面一直说的0 → 1 → … → 15 → 0 → 1 → …严格说就是循环群的结构。这里有两点值得强调为什么一定回到 0在有限群里不断累加一个元素必然重复又因为每个元素有逆元可以消去第一次重复的一定是起点 0而不是中间某个状态。饱和运算为什么不行如果超出就停在 15那么 15 1 15 0 15加法不能消去1 就没有逆元(S, 饱和加) 不是群没法用加 −3来实现减 3。丢弃高位之所以被选择是因为它恰好让 (S, ⊕) 成为一个群。A.5 正负划分完全剩余系同态 φ 不是单射无穷多个整数映到同一个状态因此状态1101表示哪个整数需要选一个代表。选法有很多补码的选法是取 2ⁿ 个连续整数{−2ⁿ⁻¹, …, −1, 0, 1, …, 2ⁿ⁻¹ − 1}任意 2ⁿ 个连续整数在模 2ⁿ 下恰好各取到每个状态一次数学上叫完全剩余系所以 φ 限制在这个区间上是一一对应。这就同时回答了三个问题范围为什么是 −2ⁿ⁻¹ ~ 2ⁿ⁻¹ − 14 bit 是 −8 ~ 7为什么1000被解释成 −8它是 −8 在 φ 下的像8 不在区间内为什么会溢出当整数运算的真实结果落在这个区间之外时φ 会把它映到区间内另一个整数的像读出来就错了。⊕ 本身永远是正确的错的是我们把状态解释回整数的那一步。A.6 小结直觉说法群论说法丢弃高位状态有限状态集 S 与运算 ⊕ 模 2ⁿ 加法能让加法正常工作(S, ⊕) 是群封闭、结合、有单位元、有逆元负数的编码整数的像 φ(−A)也就是 A 的逆元 2ⁿ − A并且唯一15 和 −1 效果相同φ(15) φ(−1)同态的像相同循环S 是由 1 生成、阶为 2ⁿ 的循环群补码的正负划分选 2ⁿ 个连续整数作完全剩余系做代表溢出真实整数结果超出代表区间进阶篇二乘法与除法哪些能丢高位哪些不能前面一直在讲加减法。那乘除呢答案是乘法可以直接丢高位除法则不行需要另外的算法。B.1 乘法同样的结构直接成立在 S 上除了 ⊕我们再定义乘法a ⊗ b (a · b) mod 2ⁿ它和取模是相容的。设 a a′ 2ⁿ·kb b′ 2ⁿ·ma′, b′ 是 a, b 除以 2ⁿ 的余数展开a · b a′b′ 2ⁿ(a′m b′k 2ⁿkm)后面一项是 2ⁿ 的倍数取模后消失所以 φ(a · b) φ(a) ⊗ φ(b)。换句话说φ 不仅保持加法也保持乘法数学上这叫环同态(S, ⊕, ⊗) 是一个环。这意味着乘法也可以先算、再丢高位得到的低 n 位不受影响和加法一样不需要区分有符号和无符号。验证一下(−3) × 2110113×00102 26 16 10低 4 位是1010补码读出来是 −6 ✓(−3) × (−2)110113×111014 182 11 × 16 6低 4 位是0110也就是 6 ✓。这里要注意一个限制只有低 n 位与有符号乘法一致。如果想得到完整的 2n 位乘积有符号和无符号的结果就不同了上面第二个例子里无符号的完整乘积是 182有符号的是 6需要先把操作数做符号扩展。B.2 除法为什么不能靠这个结构得到除以 a 就是乘以 a 的乘法逆元。但在 (S, ⊗) 里并不是每个元素都有乘法逆元奇数有例如 3 ⊗ 11 33 2 × 16 1所以 3 的逆元是 11偶数没有2 乘以任何数结果都是偶数永远不可能是 1。所以 (S, ⊗) 不是群只有加法部分是群。补码解决的是负数加法逆元并不能解决除法乘法逆元。更实际的困难是整数除法与取模不相容。同一个 bit 模式1110无符号读作 14补码读作 −2无符号14 ÷ 2 7即0111补码(−2) ÷ 2 −1即1111。同样的输入 bit结果的 bit 不同。所以硬件必须提供两种除法指令例如 x86 的DIV无符号和IDIV有符号。也就是说除法不能靠模 2ⁿ的结构直接得到。硬件是另外用移位加减的长除法来实现的这属于计算机组成原理的内容这里不展开。B.3 一张表运算能否直接用同一套电路原因加、减能(S, ⊕) 是群减法就是加逆元乘低 n 位能φ 保持乘法(S, ⊕, ⊗) 是环乘完整 2n 位不能需要区分有符号和无符号除不能偶数无乘法逆元且整数除法与取模不相容进阶篇可以浓缩成一句话固定 n bit 的加法是群 ℤ/2ⁿℤ整数到状态的映射 φ 是同态对乘法而言是环同态。补码、循环、模运算、溢出都是这个结构的不同侧面。