第二十二课:为什么需要补码(Two’s Complement)

从负数表示的困难出发,比较符号加绝对值与补码,理解补码为何能复用加法器。

本章目录CONTENTS ↓

我们已经做出了 16 位加法器 Add16。它能把两串比特相加,但接下来的算术逻辑单元(Arithmetic Logic Unit,ALU)还要处理负数和减法。问题来了:怎样表示负数,才能尽量沿用已有的加法电路?

下面是从这个问题出发的一次设计推导,用来理解补码的好处;它不代表补码发明时的真实时间顺序。

先试一个直观的办法

我们可以拿出最高位表示正负,其余位表示数的大小。这叫符号加绝对值表示法(sign-magnitude representation)。用 4 位举例,0001 表示 +1,1001 表示 −1。这个规则很容易读懂,却不能把两串比特直接送进普通加法器:

0001 按符号加绝对值解释为 +1
+ 1001 按符号加绝对值解释为 −1
------
1010 按符号加绝对值解释为 −2,不是期望的 0

要算对,就得先判断两个数的符号,再决定怎样处理大小;+0 和 −0 还会有两种不同的编码。这不是说符号加绝对值不能用,而是它不适合我们眼下“直接复用加法器”的目标。MIT:负数表示与电路取舍

从加法器的结果倒推负数的编码

先把问题缩小到 4 位。加法器只输出低 4 位;如果向左产生第 5 位进位,那一位就不在输出中。现在希望 +1 与 −1 相加后,输出 0000。那么,−1 该用哪串比特表示?

0001 +1
+ 1111 给 −1 选用的编码
------
1 0000 只输出低 4 位,得到 0000

于是我们可以规定:4 位补码中的 1111 表示 −1。对 −5 也做同样的事。要让 +5(0101)与 −5 相加后,低 4 位为零,就可以给 −5 选用 1011:

0101 +5
+ 1011 给 −5 选用的编码
------
1 0000 只输出低 4 位,得到 0000

为什么用 16 − x?十进制的 16 写成二进制是 1 0000;4 位加法器舍弃最左边的第 5 位后,输出恰好是 0000。若正数 x 与代表 −x 的编码相加后也要输出零,就可以让它们的完整和等于 16。设后一个编码按普通无符号数看是 y,那么 x + y = 16,所以 y = 16 − x。例如 x 是 5,y 就是 11;11 的 4 位写法是 1011,正是上面给 −5 选用的编码。

因此,对 4 位补码能够表示的正数 x(1 到 7),−x 可以用 16 − x 的 4 位二进制表示;0 仍用 0000。换成 n 位,就是用 2ⁿ − x 求正数 x 的相反数编码,再只保留 n 位。这套规定叫补码(two’s complement)。

补码究竟是什么

补码是一套解释固定宽度比特的规则,不是一颗芯片,也不是另外附加的符号位。用 4 位时,0000 到 0111 依次表示 0 到 7;1000 到 1111 依次表示 −8 到 −1。因此 4 位补码能表示 −8 到 7,每个数只有一种编码。

最高位为什么能按 −8 计算?这不是另一条碰巧成立的规则。前面得到负数的编码 y = 16 − x,移项可得 −x = y − 16:把负数编码按无符号数读作 y 时,它代表 y − 16。将这个解释用于最高位为 1 的全部 4 位模式(y 为 8 到 15),也包括没有正数 +8 与之配对的 1000。设低三位按无符号数读作 r(0 到 7),则 y = 8 + r,因此该模式表示 (8 + r) − 16 = −8 + r。所以最高位的位权是 −8,低三位的位权仍是 4、2、1。

例如 1000 的低三位是 0,表示 −8 + 0 = −8,不是“−0”。把最高位单独当负号,是把符号加绝对值的规则套在补码上;0000 才是唯一的 0。

现在才需要回头看“同一串比特可以表示不同的数”:例如 1011,按无符号整数(unsigned integer)的位权 8、4、2、1 算是 11;按有符号整数(signed integer)的补码规则,最高位的位权改为 −8,其余位仍是 4、2、1,所以它是 −5:

1011 按无符号数解释: 8 + 0 + 2 + 1 = 11
1011 按 4 位补码解释:−8 + 0 + 2 + 1 = −5

换成 n 位,最高位的普通位权是 2^(n−1);当它为 1 时,补码把整个模式的无符号值减去 2ⁿ,所以最高位的位权变为 2^(n−1) − 2ⁿ = −2^(n−1)。这里的 2ⁿ 是 n 位加法回绕一圈的大小,不是最高位的位权。

这个对比是为了读懂加法器输出的位模式:电路给出比特,表示规则告诉我们它代表哪个整数。最高位称为符号位(sign bit),但它不是独立的负号;在补码中,它和其他位一样有自己的位权。对于 16 位补码,最高位的位权是 −32768,能表示的范围是 −32768 到 32767。MIT:补码位权与范围

这套表示法的收益是:正数与负数可以沿用同一套逐位加法电路,减法也可以转成“加上相反数”。代价是位数固定,结果可能超出表示范围;最小负数的相反数就无法用相同位数表示。后续两课会分别介绍怎样用补码完成减法,以及固定位宽的边界。官方 Chapter 2:有符号数和补码运算

补码并非一种方案取代另一种方案的简单历史故事。早期计算机曾使用符号加绝对值、反码和补码等不同表示法;WG21 的非完整历史综述记载了 1945 年 EDVAC 提案对补码的建议,以及 1949 年 EDSAC 的使用,但没有证实“补码只为复用加法器而发明”。上面的推导说明的是它为什么适合这个设计目标。

读完后,可以先问我不清楚的地方。完成本节学习后告诉我,我们再一次一题地练习;下一课再继续计算方法。

这一页,先记到这里。