3.3 使用全加器来构造加法机

在学习了二进制加法运算之后，大家可能会感觉很愉快、很满足（通常吃饱了之后也是这种感觉，这证明知识的确也是食粮）。高兴之余，你可能想在别人——比如你的父亲面前卖弄一下你的学问，向他演示101+11=1000。看到你拥有这样非凡的才能，他肯定表现得非常激动：“揍死你这个不成器的东西，竟然连加法都不会做了！”这也难怪，大人们很少有懂得二进制的。如果不是为了研制计算机，我们干吗要研究二进制，和它纠缠在一起？

任何一个二进制数都是由一个以上的比特组成的，是一个比特串。为了突出组成它的每个比特，一个二进制数可以表示成（如果它包含了6比特的话）：

a5a4a3a2a1a0

在这里，a0、a1…a5都是单个的比特，是这个二进制数的每一位。奇怪吧？它们都有一个“a”，脚底下还吊着一个独一无二的下标。什么意思呢？“a”表示它们都属于同一个大家庭，即这个二进制数；下标则指明了它们在这个二进制数中的位置，或者说，在这个大家庭里的长幼次序。

我们在日常生活中通常都是从1开始编号，但是这里却是从0开始，而且从右向左递增。为什么要这样干呢？电子计算机是外国人发明的，我们研究计算机技术，引进他们的技术资料，自然也就把这个学来了。交朋友要交脾气相投的，干事业要找志趣一样的。要是你和自己的创业伙伴一起放羊，晚上赶羊进圈的时候，你数的是1、2、3、4、5，共5只，而他数的是0、1、2、3、4，共4只，弄不好你们俩就要反目。

所以，如果a5a4a3a2a1a0=110101，那么它们的对应关系就如图3.3所示。

你可能怀疑我的动机，正在猜想我为什么要跟你说这些。你的怀疑是对的，因为我正是想和你一起分析分析，在不知道或不用知道两个二进制数究竟是几的情况下，它们是如何相加的，这里面都有些什么规律。如果可能的话，我们将会得到一份奖赏，那就是顺利地把期盼已久的加法机造出来。

既然知道了我的心思，那么，让我们来看看，随便两个二进制数相加时会怎样，比如：

a5a4a3a2a1a0+b5b4b3b2b1b0

它们可以是任意两个数。照惯例，要先把它们右对齐，叠在一起，如图3.4所示。

因为最先相加的是最右边那一列，即a0和b0，所以这里没有从其他列来的进位，属于单纯的两个比特相加。如图3.5所示，这里有4种可能的情况。

依据二进制加法口诀，很显然，只有在来自被加数和加数的比特都为“1”的时候，也只有在这个时候，才会向左边甩出一个进位“1”，并且结果是“0”。

相比之下，倒数第二列就没有这么幸运了。因为它不单纯是a1和b1相加，还可能会收到最右边那列赠予的礼物——进位，这样这一列实际上就是三个比特相加。当然，要是运气好，最右边一列没有产生进位，那么情况会和图3.5一样。

不过，如果最右边一列产生了进位，那么这一列实际上是另外4种可能，如图3.6所示。

综合图3.5和图3.6，就得到了在这一列上做加法时，所有可能出现的情形，共8种。我想大家都看得很清楚，这一列相加的结果可能是0，也可能是1。而且，也可能产生进位，但这个进位必定是1（而不会是其他数值）。

我们可以接着研究其他列上相加的情况，但实际上已无必要，原因是除了最右边那一列，不管哪一列相加，情况都和刚才讨论的一样，每一列都有可能需要加上前一列来的进位（1），相加的结果可能是0，也可能是1，并且它自己也可能会把一个进位（1）塞给别人。

既然是这样，你的大脑也许会闪出灵感的火花，迸出一个非常绝妙的想法：既然加法都是按列进行的，而且每一列的计算过程都一样，那么完全可以设计一个电路来完成每一列的相加过程，如图3.7所示。

在图中，A和B分别是来自被加数和加数的一个比特，它们正好在同一列上；Ci是来自右边一列的进位；Co是本列产生的进位；S是本列的“和”。为了表明这个电路的用途，我们在图的中间加了一个符号“∑”。在数学中，这个符号用来表示“加”，它的读音是“西格马”。很显然，这并不是马的一个新品种。

既然是一个电路，它肯定有一个名字。是的，它叫全加器。这不是一个很容易理解的名字，特别是这个“全”字。而且，既然有全加器，是不是还应该有“半加器”？你别说，还真有半加器这东西。但是，半加器仅仅是把来自被加数和加数的两个比特加起来，产生一个“和”以及一个进位，并不考虑从其他列来的进位。换句话说，它只是用电路来实现二进制加法口诀。全加器则不然，它真正实现了二进制加法中每一列的加法过程，所以它才叫做“全加器”。

有了全加器，解决了二进制加法过程中每一列的计算问题，那么，我们可以搞一大堆全加器，根据被加数和加数的比特数，把它们串联起来组成一个完整的加法电路，图3.8显示了这一过程。

图中，参与相加的两个二进制数分别是 a2a1a0和 b2b1b0，组成它们的每一个比特都可以用开关的闭合与断开来得到。

随着开关的闭合与断开，我们会得到一些二进制数，比如 a2a1a0=110，这个很正常。

但是，也有可能会得到一些看似不那么正常的，比如 a2a1a0=011。不要大惊小怪，这其实很正常，它实际上就是11，只不过前面多了个“0”。和十进制一样，在1左边不管有多少个“0”，都不会改变它的大小。有人不是说嘛，“1”就好比是健康，“0”就是财富。健康打头，财富多了才有意义；否则，你把健康放到最后，前面的财富再多有什么用呢？

因为被加数和加数各自用了3个开关，很明显，参与运算的被加数和加数都只能是3比特的二进制数，比如110+101。之所以没有使用比3比特更大的二进制数，是因为较小的数能够使我少画一些电路，这样看起来更清楚，并因此而节约了篇幅（印刷之前，出版社的老编们可能会重新绘制这些图，我希望他们能感谢我如此善解人意，并在适当的时候请我吃饭）。

像按列做加法一样，3个全加器串联在一起，把被加数和加数中位置相同的两个比特相加，输出结果，并将进位传递给下一个全加器。可以看出，第一个（左下角那个）全加器的进位输入端没有使用，意思是“没有进位输入”，或者“从后面来的进位是0”。其余的全加器，它们的进位输入端都和前一个全加器的进位输出端相连，意思是“前面的，你产生进位了吗？如果有，我得加上它”。S2S1S0是两个二进制数相加后的最终结果。S3是最后一个全加器产生的进位，由于这是最后一个全加器，所以它的进位也是最终结果的一部分。尽管100+1的结果是3比特的101，但是100+100却产生4比特的结果1000，最左边的那个“1”纯粹是由于进位产生的。

如果仔细品味的话，你还可以发现它很容易进行扩充以计算更大的数（这样它会更实用），唯一所要做的就是在现有的基础上再串联更多的全加器。现在你应该感到高兴，看看你自己，进步多大呀！刚拿起这本书的时候，你对电子技术还知之甚少，现在，你连这样复杂的电路都能看懂了，这难道不值得庆贺吗？

在所有的计数方法里，二进制不见得是最实用的，它不够简明，写起来麻烦。别人不敢说，我相信交警们一定喜欢十进制，而不是二进制。当他们在路上执勤的时候，肯定能迅速记住刚才超速的是“计A9998”，而“计A10011100001110”这样的车牌号只能让他们眼晕。

好吧，我承认大家平时过日子不需要它。但是，计算机需要它。很奇怪吧？就因为它简单。它的全部，它的一切，就只有0和1。简单意味着具有较少的运算规则；较少的运算规则意味着设计不太复杂；不复杂的设计又意味着可以用很少的材料来制造，并最终节省人力、物力、时间和金钱，还能保证机器工作的可靠性。

要造一台机器来计算加法，全加器无疑是最基础的零部件了。但是，这个全加器到底应当如何构造呢？看起来，我们已经离目标不远了，应该很快就能揭开最终的谜底。

事实上，还差得远呢。要想知道全加器的内部都是些什么，它是如何把3个比特加起来的，我们还必须回到过去，了解电与磁的历史，以及先哲们创立的逻辑学，看能不能从中得到一些启发。