小菜学编程
众所周知，计算机内部采用二进制来保存和处理数据。那么，计算机又是如何实现二进制数学运算的呢？我们先从最简单的 加法（ addition ）运算入手，一探究竟。
一位加法运算
先考察一位二进制数的加法运算，两个加数可分为以下四种组合：
| 加数① | 加数② | 结果 | 结果（二进制） | 加和 | 进位输出 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 00 | 0 | 0 |
| 0 | 1 | 1 | 01 | 1 | 0 |
| 1 | 0 | 1 | 01 | 1 | 0 |
| 1 | 1 | 2 | 10 | 0 | 1 |
- 两个 0 相加，结果为 0 ；
- 一个 0 和一个 1 相加，结果为 1 ；
- 两个 1 相加，结果为 2 ，写成二进制为 10 ；
由此可见，两个一位二进制数相加，结果可能是两位的。因此，我们可以将结果拆成两部分：
- 右边的位称为 加和（ sum ）；
- 左边的位称为 进位输出（ carry out ）；
进位输出，顾名思义表示它应该进到更高一位。在多位二进制数加法运算中，每一位的进位必须和更高一位的数值加起来。
一位半加器
观察加和与两个加数之间的关系，我们发现它们满足异或逻辑，可以用一个 异或 门来实现。而进位输出跟两个加数之间则满足 与 逻辑，可以用一个与门来实现：
如上图，两个加数输入到异或门输出加和，输入到与门则输出进位。由此，我们得到一个对两个一位二进制数求和的电路，称为 一位半加器（ one bit half adder ）。
一位半加器，顾名思义表明它的功能还不是完整的。接下来，我们继续探索功能完整的一位加法器应该是怎样的。开始之前，我们需要先考察多位二进制数加法的运算步骤。
多位加法运算
一位的二进制数加法很简单，而多位二进制数则复杂一些。我们来看一个例子：
- 每一位两个加数和低位的进位相加，得到加和、进位输出；
- 进位输入则进一步跟更高位的加数相加；
- 最低位没有来自更低位的进位，进位用灰色的 0 表示；
一位全加器
由于加法运算每一位的结果必须加上更低一位的进位，因此一位半加器仍需升级，使它能够处理进位输入。换句话讲，我们需要一个电路，来计算两个一位二进制数和进位输入的和。
实际上，这个电路并不难，串联两个一位半加器即可实现：
- 第一个半加器计算将两个加数相加，得到 加和 以及 进位输出 ；
- 第二个半加器将加和与进位输入相加，得到最终的 加和 ；
- 两个半加器的进位输出接到一个 或门 ，得到最终的 进位输出 ；
两个加数以及进位输入相加，需要执行两次加法运算。任意一次加法运算产生进位，最终结果就有进位。值得一提的是，这两次加法运算不可能都产生进位。
至此，我们得到一个功能完整的加法器，即 一位全加器（ one bit full adder ）。它有 3 个输入：
- 输入①，即加数①；
- 输入②，即加数②；
- 进位输入；
一位全加器负责计算这三者之和，并输出结果：
- 和；
- 进位输出；
多位全加器
有了一位全加器，我们可以实现任意位数的加法器。每个位由一个一位全加器负责计算，得到的进位输出作为更高一位的输入。以八位加法器为例：
两个加数分别是 A 和 B ，其中 A0 和 B0 分别表示两个加数的最低位。以最低位举例，A0 和 B0 被送到最右边的全加器，产生的加和 S0 就是结果的最低位；进位输出则接到下一个全加器，跟下一位相加。
我们可以将这个八个串联的一位全加器作为一个整体，封装成一块简洁的芯片。芯片有 17 个输入端，以及 9 个输出端，分别是：
- A0 ~ A7 用于输入第一个加数；
- B0 ~ B7 用于输入第二个加数；
- CI 用于输入来自更低位的进位（芯片也可以串联）；
- S0 ~ S7 用于输出加和；
- CO 用于输出进位；
串联更多一位全加器，我们可以制造支持更多位加数的加法器。多位加法器也可以串联，例如串联两个 8 位加法器即可得到一个 16 位加法器。
【小菜自制计算机】系列文章首发于公众号【小菜学编程】，敬请关注：
