编码 隐匿在计算机软硬件背后的语言

第一个全加器的进位输出就是第二个全加器的进位输入。随后的每列二进制数都以同样的方式连接。每一列进位输出都是下一列的进位输入。

最终，第8个灯泡和最后一对开关将以如下方式连接到全加法器上。

这里，最后一个进位输出将被连接到第9个灯泡上。

至此，我们就大功告成了。

还可以用另一种方式来看这8个全加器的连接，每个全加器的进位输出都作为下一个全加器的进位输入。

下面是画成一个盒子的完整的8位二进制加法器，输入标记为 ${ \bf A } _ { 0 } \sim { \bf A } _ { 7 }$ 和 ${ \bf B } _ { 0 } \sim { \bf B } _ { 7 }$ ，输出标记为 $\mathbf { S } _ { 0 } \sim \mathbf { S } _ { 7 }$

编码—隐匿在计算机软硬件背后的语言

144

这就是表示多位数字中各位数字的常用方法。 $\mathbf { A } _ { 0 }$ 、 $\mathrm { B } _ { 0 }$ 和 ${ \bf S } _ { 0 }$ 是最低有效位，或者说是最右边的一位。 $\mathbf { A } _ { 7 }$ 、 $\mathbf { B } _ { 7 }$ 和 $\mathbf { S } _ { 7 }$ 是最高有效位，或者说是最左边的一位。例如，下面演示了这样一列带有下标的字母是如何用来表示一个二进制数0110-1001的。

$$
\begin{array} { r c c c c c c c c c } { \mathsf { A } _ { \gamma } } & { \mathsf { A } _ { \varepsilon } } & { \mathsf { A } _ { \varepsilon } } & { \mathsf { A } _ { \varepsilon } } & { \mathsf { A } _ { \varepsilon } } & { \mathsf { A } _ { \varepsilon } } & { \mathsf { A } _ { \varepsilon } } & { \mathsf { A } _ { \varepsilon } } & { \mathsf { A } _ { \varepsilon } } & { \mathsf { A } _ { \varepsilon } } \\ { 0 } & { \uparrow } & { \uparrow } & { 0 } & { \uparrow } & { 0 } & { 0 } & { 1 } \end{array}
$$

下标从0开始，并且向着高有效位的方向递增，因为它们和2的乘方数（幂）相对应。

$$
\begin{array} { c c c c c c c c c } { { 2 ^ { 7 } } } & { { 2 ^ { } } } & { { 2 ^ { } } } & { { 2 ^ { } } } & { { 2 ^ { } } } & { { 2 ^ { } } } & { { 2 ^ { z } } } & { { 2 ^ { } } } & { { 2 ^ { } } } & { { } } \\ { { 0 } } & { { 1 } } & { { 1 } } & { { 0 } } & { { 1 } } & { { 0 } } & { { 0 } } & { { 1 } } \end{array}
$$

如果把下面一排的每个二进制位和其对应的2的幂相乘再依次相加，你就会得到0110-1001的十进制数表示 $6 4 + 3 2 + 8 + 1$ ，即105。

另一种8位二进制加法器可用下图表示。

双线箭头包含了8个输入端，代表一组8个独立的信号。它们被标识为 $\mathbf { A } _ { 7 } . . . \mathbf { A } _ { 0 } , \ \mathbf { B } _ { 7 } . . . \mathbf { B } _ { 0 }$ $\mathbf { S } _ { 7 } . . . \mathbf { S } _ { 0 }$ ，同样也表示一个8位二进制数。

一旦你搭建起了8位二进制加法器，你就可以再搭建另外一个加法器。把它们级联起来就可以很容易地扩展出一个16位加法器。

12 二进制加法器

145

右边加法器的进位输出被连接到了左边加法器的进位输入上。左边加法器的输入包含了两个加数的高8位，而得到的结果也是最终加和的高8位。

你可能会问：“这真的就是计算机进行加法运算时所采用的方式么？”

基本上来说，是的。但也并不完全是。

首先，可以制作一个比这个算得更快的加法器。如果你看一下这个电路是如何工作的，最低有效位的一对数字相加所得出的一个进位输出，将要参与接下来的一对数字的加法运算，由此得到的一个进位输出又要参与再下一对数字的加法运算，依此类推。加法器的总体速度等于数字的位数乘以全加器器件的速度，这被称做行波进位(ripple carry，或脉冲进位)。更快的加法器运用了一个被称为“前置进位”的电路来提高运算的速度。

其次，也是最重要的，计算机已经不再使用继电器了！尽管它曾经被使用过。第一台数字计算机在20世纪30年代被建造完成，当时所使用的就是继电器，后来也使用过真空管。今天的计算机使用的是晶体管。在被用到计算机中时，晶体管的工作方式与继电器基本相同，但是正如我们即将了解到的，晶体管要比继电器计算速度更快、体积更小，而且噪声更弱、耗能也更低，而且更便宜。搭建一个8位加法器依然需要144个晶体管（如果你用前置进位法代替行波进位，将会用到更多的晶体管），但是电路却是极小的。

编码隐匿在计算机软硬件背后的语言

146

如何实现减法

当你确信继电器连接到一起真的可以实现二进制数加法的时候，你可能会问；“那么如何实现减法呢？”本章后续的内容会帮你解答这个问题，因此提出这样的问题并不是说你在没事找事，而实际上这表明你是相当有察觉力的。加法和减法在某些方面相互补充，但在机制方面这两个运算则是不同的。加法是始终从两个加数的最右列向最左列进行计算的。每一列的进位加到下一列中。在减法中没有进位，而是有借位种与加法存在本质区别的麻烦机制。

例如，我们来看一个典型的借位减法的题目：

$$
\frac { - 1 7 6 } { 3 7 3 }
$$

要解决这个问题，首先从最右列着手。我们看到，6是大于3的，因此从5上借1，再用13减去6，得到结果为 $7 。$ 由于我们已经在5上借了1，因此，现在实际上那一位是4，而4是小于7的，因此继续从2上借1，14减7结果为 $7 \textdegree$ 而由于在2上借了1，实际上这一位是1，从中减去1，结果为 $0 _ { \circ }$ 因此，最后的结果应为77：

$$
\frac { - 1 7 6 } { 7 7 }
$$

如何才能通过一连串逻辑门来实现这个反逻辑呢？

然而，我们并不打算这样做。相反，我们打算用一个小技巧来让减法不涉及借位。这会使波洛尼厄斯（既不是欠债人也不是出借人）满意，我们其他人也一样。此外，由于减法与计算机中以二进制编码的存储有关，详细地了解减法也是很重要的。

为了便于表达，将进行减法的两个数分别用被减数（minuend）和减数（subtrahend）表示。从被减数中减去减数，得到的结果叫做差（difference)。

被减数一 减数差

为了避免借位，首先要从999中减去减数，而不是从原来的被减数中减去减数。

$$
\frac { - 1 7 6 } { 8 2 3 }
$$

由于操作数是三位数，所以这里使用999。如果操作数是4位，则用9999。从一串9中减去一个数叫做对9求补数。176对9的补数是823。反之亦然：823对9的补数是176。这样的好处就是无论减数是多少，计算对9的补数都不需要借位。

计算出减数对9的补数后，将补数与原来的被减数相加：

编码—隐匿在计算机软硬件背后的语言

1 波洛尼厄斯是莎士比亚著名戏剧《哈姆莱特》中的一位世故的御前大臣，他在第一幕第三场向他即将离家外出的儿子说了一大段告诫的话，其中有一句：“不要向人告贷，也不要借钱给人。因为向人告贷的结果，容易养成因循懒惰的习惯；而把债款放了出去，往往不但丢了本钱，而且还失去了朋友。”后来，美国经济学家范里安在其所著的《微观经济学：现代观点》一书中使用了“波洛尼厄斯”一词，该词就成为了经济学中的一个概念。经济学在研究消费者进行跨时期的消费行为时，把这种既不向别人借钱、也不借钱给别人的状态叫作“波洛尼厄斯点”。因此，这里的“波洛尼厄斯”也就表示既不向别人借钱、也不借钱给别人的人。译者注

148

$$
\frac { 2 5 3 } { 1 0 2 3 }
$$

最后再将结果加1，并减去1000。

$$
\begin{array} { r } { 1 0 7 6 } \\ { + 1 } \\ { \frac { - 1 0 0 0 } { 7 7 } } \end{array}
$$

到此，我们就得到了结果。答案与先前的相同，而且没有用到借位。

为什么这种方法行得通呢？原题目是这样的：

$$
2 5 3 - 1 7 6
$$

在这个式子中加上一个数再减去这个数，结果是相同的。因此先加上1000，再减去1000:

$$
2 5 3 - 1 7 6 + 1 0 0 0 - 1 0 0 0
$$

这个式子与下式等价：

$$
2 5 3 - 1 7 6 + 9 9 9 + 1 - 1 0 0 0
$$

然后用以下方式将数字重新组合：

$$
2 5 3 + ( 9 9 9 - 1 7 6 ) + 1 - 1 0 0 0
$$

这个式子与刚才描述过的用9的补数进行的计算是相同的。我们用两个减法和两个加法来替代一个减法，而在这个过程中避免了烦琐的借位。

如果减数大于被减数会怎么样呢？例如以下问题：

$$
\frac { - 2 5 3 } { 3 7 3 }
$$

通常遇到这个问题时你可能会说：“这里减数大于被减数，因此要将减数和被减数交换来执行减法，然后给结果取个相反数。”你可能在脑子里将这两个数交换，而写出这样

13 如何实现减法

149

的答案：

$$
\frac { - 2 5 3 } { 7 7 }
$$

如果希望求解这个问题而不使用借位的话，就要采用与之前稍微不同的方法。首先要像前面一样，用999减去减数253，计算出对9的补数：

$$
\frac { - 2 5 3 } { 7 4 6 }
$$

把该数对9的补数与被减数相加：

$$
\frac { 1 7 6 } { 9 2 2 }
$$

在前面的例子中，下一步应该加1，并减去1000来得到最终结果。但是在这里，这种方法并不适用。因为你会遇到923减去1000的情况，这又导致了借位。

由于我们之前已经加了999，这里再减去999：

$$
\frac { - 9 9 9 } { 7 7 9 }
$$

到这里，我们会意识到这个问题的结果是负数，因此需要将减数与被减数交换，用999减去922。这里没有用到借位，结果与我们期望的相同：

$$
\frac { - 9 9 9 } { - 7 7 }
$$

同样的技巧可以用于二进制数中，而且实际上这要比十进制数简单。让我们一起来看看该如何操作。

原来的减法题目是：

编码—隐匿在计算机软硬件背后的语言

150

$$
\frac { - 1 7 6 } { 3 3 7 3 }
$$

将这些数字转化为二进制数，问题变为：

$$
\frac { - 1 0 1 1 0 0 0 0 } { ? ? ? ? ? ? 2 9 2 9 2 }
$$

第一步，用11111111（即255）减去减数：

$$
\frac { - 1 0 1 1 0 0 0 0 } { 0 1 0 0 1 1 1 1 }
$$

当计算十进制数减法的时候，减数是从一串9中减去的，结果称为9的补数。在二进制数减法中，减数是从一串1中减去的，结果称为1的补数。但是请注意，我们在求对1的补数时并不需要用到减法。在求对1的补数时，只需将原来的二进制数中的1变为0，将0变为1即可。因此对1求补数有时也会称为相反数(negation)或反码(inverse)。这里你可能会想起第11章中的反向器，它的作用就是将0变为1，将1变为0。

第二步，将减数对1的补数与被减数相加：

$$
\frac { 1 1 1 1 1 1 0 1 } { 1 0 1 0 0 1 1 1 1 }
$$

第三步，将上式所得结果加1：

$$
\frac { 1 0 1 0 0 \div 1 0 0 } { 1 0 1 0 0 \div 1 0 1 }
$$

第四步，减去100000000（即256）:

$$
\frac { 1 0 1 0 0 1 1 0 1 } { 1 0 0 0 0 0 0 0 0 }
$$

结果就等于十进制数的77。

13 如何实现减法

151

我们把这两个数颠倒位置后再做一遍。在十进制中，减法题目对应于：

$$
\frac { - 2 5 3 } { 3 7 3 }
$$

而用二进制表示为：

$$
\frac { - 1 1 1 1 1 0 } { ? ? ? 2 ? 2 ? 2 }
$$

第一步用11111111减去减数，得到对1的补数：

$$
\frac { - 1 1 1 1 1 1 0 1 } { 0 0 0 0 0 1 0 }
$$

第二步，将减数对1的补数与被减数相加：

$$
\frac { 1 0 1 1 0 0 0 0 } { 1 0 1 1 0 0 1 0 }
$$

现在我们要用某种方法在结果中减去11111111。当减数小于被减数的时候，我们将结果加1再减100000000来完成计算。但是你无法在不借位的情况下做到这一点。所以，我们先用11111111减去所得结果：

$$
\frac { - 1 0 1 1 0 0 1 0 } { 0 1 0 0 1 1 0 1 }
$$

这里又一次用到了将各位取反来求得结果的方法，但是这个结果是77，而真正的答案应该是-77。

到这里，我们已经有了足够的条件来改造上一章所搭建的加法器，并让它像实现加法一样来实现减法运算。为了不让问题太复杂，这个新的加/减法器只执行在减数小于被减数的减法操作，即结果为正数的操作。

该加法器的核心是由逻辑门集成的8位全加器。

编码—隐匿在计算机软硬件背后的语言

152

你可能还记得，输入 ${ \bf A } _ { 0 } \sim { \bf A } _ { 7 }$ 及 $\mathbf { B } _ { 0 } \sim \mathbf { B } _ { 7 }$ 与两排分别表示两个要相加的8位二进制数的开关相连。进位输入接地。 $\mathbf { S } _ { 0 } \sim \mathbf { S } _ { 7 }$ 与表示结果的8个灯泡相连。由于这个加法有可能得到9位数值，进位输出端也连接了一个灯泡。

控制面板示意如下图所示。

在上图中，开关所表示的是183（即10110111）与22（即00010110）相加，结果如灯泡所示为205（即11001101）。

8位加/减法器所用的新面板较从前做了些许的改动。它增设了一个开关，用以选择做加法还是做减法。

13 如何实现减法

153