计算机自底向上（一）：数字逻辑电路和二进制加法

数字逻辑电路有三种基本的门电路：非（NOT）、与（AND）、或（OR）。这三个门电路构成了基本的计算机逻辑。通过将它们结合，我们可以得到异或门（Exclusive OR，XOR），它的特点是当A，B相同时输出0，不同时输出1。这是一个重要的门；我们很快就会明白其重要性。同时，根据布尔代数的相关结论，只要有与非门或者或非门我们就可以实现所有的逻辑电路，也就是说这两个门是万能的。

现代计算机的核心部件是CPU，其首要功能就是进行算术和逻辑运算。CPU采用的算术运算是二进制的，也就是逢2进1。我们先从最简单的二进制加法开始：假设我们现在只有一个bit的空间，进行二进制加法，我们会得到以下结果：

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 0

我们很快就可以发现一个规律：当两个加数相同时，我们输出0；当加数不同时输出1。这与我们之前提到的XOR门的结果完全一致；也就是说我们可以认为异或门部分地实现了二进制加法。之所以称之为部分地，是因为我们还没法处理进位。因此，除了当前位的结果，我们还需要输出一个进位（Carry Bit）。那怎样判断进位呢？很明显，只有两个加数都是1的时候才会发生进位。这就是AND的逻辑：1 AND 1 = 1，除此之外全都为0。到这里，我们已经初步地实现了一个竖式加法的电路，它被称为半加器（Half Adder）：

为什么是个半加器呢？因为它只能处理自己的进位，却不能处理前一位加法运算产生的进位。所以，它应该将前一位加法的进位结果也考虑进来。为了实现这一目标，我们先把A，B加起来，得到一个输出S0；然后模拟竖式加法，把S0和上一位的进位C0再加一下，就得到了当前位的最终结果了。我们之前设计的半加器既能处理加法又能处理进位，放在这里刚好进行两次加法。但是问题是，两个半加器会有两个进位输出，而我们最终的进位输出必然只有一个，怎么处理呢？

让我们再来仔细考虑一下进位。在一位的运算中我们事实上要处理的是三个数：A，B，C。简单的穷举可以帮我们发现规律：

0 + 0 + 0 = 0

0 + 0 + 1 = 1

0 + 1 + 0 = 1

0 + 1 + 1 = 0 （进位，此时第一个半加器进位为0，第二个半加器进位为1）

1 + 0 + 0 = 1

1 + 0 + 1 = 0 （进位，此时第一个半加器进位为0，第二个半加器进位为1）

1 + 1 + 0 = 0 （进位，此时第一个半加器进位为1，第二个半加器进位为0）

1 + 1 + 1 = 1 （进位，此时第一个半加器进位为1，第二个半加器进位为0）

我们发现我们有四种情况需要进位，并且要进位时两个半加器的进位输出总是至少有一个是1（事实上，两个输出不可能同时为1）。与它等价的命题是，当两个进位输出都不为1时，就没有最终的进位输出。这和OR门的特征一致：当且仅当两个输入均为0时，输出0；只要输入中至少有1个1，输出1。因此，我们只需要将两个进位输出通过OR门连接起来，就可以得到最终的进位结果。至此，我们得到了一个全加器（Full Adder）：

得到了一个全加器以后我们要做的事就非常简单了，我们想要多少位加法就把多少个全加器并列起来，将上一个全加器的进位输出和下一个全加器的进位输入相连，最终得到一个多位的加法器。