怎么实现一个加法器

最近刚通关图灵完备，作为一个没有学过计算机专业课的人来说，玩的过程中也算是对逻辑电路有了一点点了解。

不知道是不是我的 mac 配置不够的问题，我已经遇到两次玩的时候死机的情况了。本来还想尝试加一下 risc-v 指令集呢，还是先搁置吧。

基础实现

加法器的输入是两个八位数字 $x$，$y$ 以及进位 $c$，计算 $x+y+c$ 以及输出进位。

一个最基础，同时也是最直观的实现，就是模拟手工计算的过程。这里我们定义 $x_i$，$y_i$ 分别是输入的第 $i$ 位，$s_i$ 以及 $c_i$ 则是第 $i$ 位的输出值和输入进位。其流程如下：

计算第 0 位的输出以及进位，其中 $s_0 = x_0 \oplus y_0 \oplus c $, $c_0 = (x_0 \land y_0) \lor (x_0 \land c) \lor (y_0 \land c)$。为了方便起见，我们把传入的进位定义为 $c_{-1}$。
把第 0 位得到的进位和第一位，计算 $s_1$ 和 $c_1$。
以此类推，得到所有八位输出以及最终进位 $c_7$。

其实这里就是把 8 个全加器连接起来。

第一个方法很简单，很直白，除了慢了点，没啥缺点。这种实现也有个名字，叫行波进位。容易看出，每一位的计算需要 7 个原件，延迟主要来自 $c_i$ 的计算，抛开能预计算得到的两部分，延迟是4。

P.S 这里原件是指 xor，nor 之类的，延迟也是游戏里的定义，不玩游戏的话不用关心。

*不过这其实并不是最简形式，首先我们给预计算部分一个名字，至于为什么叫 $p$ 和 $g$ 后面就会知道了

$$ \begin{aligned} g_i &= x_i \land y_i \\ p_i &= x_i \oplus y_i \end{aligned} $$

另外，注意力惊人的人可以发现，$c_i$ 其实可以改写为：

$$ c_i = (x_i \land y_i) \lor \left(c_{i-1} \land (x_i \oplus y_i)\right) $$

诶，这时候第 $i$ 位的计算就可以写成如下形式，延迟也降低了1。

$$ \begin{aligned} s_i &= p_i \oplus c_{i-1} \\ c_i &= p_i \lor (g_i \land c_{i-1}) \end{aligned} $$

虽然但是，目前大部分计算仍然是串行执行的，每一位的计算都依赖于前一位的结果。想要让速度快起来，就必须找到一种方式能够进行并行计算。

先来看 $c_i$ 的计算，我们来展开看看