可软可硬——从电路的角度做加法

最近在听《三体》的广播剧，今天刚好讲到人列计算机。电路设计是我大学的老本行，后来却跑去做软件，真让人唏嘘。今天，我们就从逻辑电路的角度来讲一讲，加法是怎么实现的。

我们知道，5+9=14，这是再简单不过的一个加法。稍稍懂一些计算机的同学也知道，数字在计算机里面是二进制形式存放的，所以显然5+9在计算机里面是101 + 1001 = 1110

相信很多人到这一步就停下来了，就拿出去装逼了。

那么我们更进一步，二进制101和二进制1001在电路里面，到底是怎么做加法的？我们知道电路的导通表示1，电路的关闭表示0.现在给你一个几个开关，你能通过改变它的导通和关闭来做加法吗？

为了使用电路来做加法，我们需要知道三个电路元件：与门、或门和异或门。这三个门都有两个输入脚和一个输出脚。两个输入脚是否通电决定了输出脚是否通电。他们长下面这样：

与门

对于与门，只有两个输入引脚同时有电流流入，输出脚才有电流流出。否则输出脚没有电流流出。相当于 Python 里面的and关键字。

或门

对于或门，任何一个输入脚有电流流入或者两个脚同时有电流流入，输出脚都有电流流出。相当于 Python 里面的or关键字。

异或门

对于异或门，当两个输入引脚中，只有一个引脚有电流流入时，有电流流出。但是如果两个引脚同时有电流流入，或者同时没有电流流入，输出引脚都没有电流流出。相当于Python 里面的^符号。

那么如和使用这三种逻辑门电路，组合出一个做加法的电路呢？我们来看一下一位的二进制加法。

• 0 + 0 = 0
• 0 + 1 = 1
• 1 + 0 = 1
• 1 + 1 = 0 并进1位。

如果不考虑进位，实际上这个结果就是异或门的结果。所以我们可以直接使用一个异或门，来表示1位二进制的加法。但由于最后的结果只有一个二进制位来存放，所以进位的1就丢失了。

现在我们来考虑，如何保留这个进位的1呢？注意到，只有两个1 + 1这一种情况才会出现进位。所以我们需要有一个电路，只对1 + 1起反应，而对另外三种不起反应。

显然，我们可以使用与门，只有在两个输入引脚都有电流流入的时候，才会有电流流出。我们通过这个与门是否有电流流出就能判断是否有进位发生。如下图所示：

与门和异或门并联，实现记录相加的结果和进位信息。

现在我们增加一下难度，如果是两个二位二进制数相加呢？对于低位的二进制数数，显然我们上面的做法已经可以了。但是对于高位的二进制数而言，不仅本身要相加，还要加上低位进上来的进位数。所以要到高位异或出来的结果再与低位的进位输入再异或一次。并且这个和也要考虑是否进位。如下图所示：

为什么最后还有一个或门呢？是因为，进位有三种情况下是进1，还有一种情况下是进0.

高位的被加数(a)、加数(b)他们本身的进位可能是0或者是1. a 和 b 的和再与低位进位数(c)再求和，新的进位可能是0或者是1。但需要注意，当 a与 b 需要进1的时候，a 与 b 的和必定为0.此时与c的和不可能进位。只有当 a 与 b 一个是0，一个是1的时候，他们本身的进位是0，但他们在 c 为1的时候新的进位是1。

所以最后两个进位的输出汇入一个或门得到最终的进位输出，成为新的进位。

我们发现，第一副图实际上就是第二幅图在 c=0时候的特殊情况。所以只有一位数做加法的时候，也可以使用第二幅图对应的电路。

当我们把4个这样的电路连在一起的时候，也就实现了一个4位的全加器。

我们通过 Python 来模拟这个电路：

def full_add(a, b, c):
    sum_of_a_b = a ^ b
    final_sum = sum_of_a_b ^ c
    increase_of_a_b = a & b
    increase_of_sum_of_a_b_c = sum_of_a_b & c
    final_increase = increase_of_a_b | increase_of_sum_of_a_b_c
    return final_sum, final_increase

我们使用两个数字来测试一下这个全加器：

这个结果最后输出的数字，我们从下往上读，就是1110，正好是14对应的二进制数，说明计算成功。

我们再来个复杂的，1099 + 237 = 1336，运行效果如下图所示：

从下往上读，确实是正确的：

大家注意，我最后把进位的数打印了出来。并且通过一个while循环，无论加数和被加数有多少位都进行计算。但是在实际电路中，或者 C 语言中，我们需要定义整型的长度，例如32位整型，64位整型等等。那么，当最后的进位超出了这个最大位数，如果是无符号整型，就会发现两个很大的数相加结果竟然是一个很小的数，因为最后的进位1由于超过了最大位数，被丢掉了；如果是有符号整型，就会发现两个正数相加变成了负数，因为最高位本来是0，由于进位的关系，它变成了1，但最高位是1表示负数。

这两种情况就叫做数值溢出。