剖析全加器的一次尝试
全加器是计算机进行计算的基本单元，是构成电子计算机核心微处理器中算术逻辑单元的基础。
全加器的结构如下。
全加器示意图
其中，A和B是计算所需要的两个数，表示输入进位，
表示输出进位，S表示求和结果。
全加器的硬件剖析
全加器本质上是一个数学概念。在实际生产时，可以使用不同的方式制造。在现代工艺中，主要使用晶体管进行制造。
后文将会详述，全加器实际上只是逻辑门的组合，所以实际上任何可以构成逻辑门的原件（哪怕是非电子元件）也可以通过组装构建成一个全加器。
二进制，布尔代数和电路
虽然这几个概念都是独立发明的，但是最后他们组合在一起，形成了我们所认识的逻辑门。
二进制
0代表十进制中的0，1代表十进制中的1，10代表十进制中的2，11代表十进制中的3，以此类推。
实际上，我们需要注意到的是，在任意的进制中，例如在8进制中，10代表8，十进制中，10表示10，在16进制中，10代表16。
这一点很有趣，10永远表示的是代表该进制的数。
这不是偶然，因为当我们用于表示该改进所有可用的数都用完了之后，我们想表示下一个数的时候，只能通过进位的方式表示，而进位的结果就是下一位置为1，而原来的位置位0。
布尔代数
布尔的贡献在于将原本属于哲学范畴，或者说是语言表达范畴的逻辑推论数学化，使得我们可以简单的使用数学语言来描述逻辑推论的命题。
| 运算 | 符号 |
|---|---|
| 交集（与） | |
| 并集（或） | |
| 非 |
| 运算律 | 符号 |
|---|---|
| 结合律 |
|
| 交换律 |
|
| 分配律 |
|
| 互补律 |
|
有了这样的数学表达，逻辑运算就变成了可以通过数学进行推导的运算。
同时，更重要的，让计算机实现逻辑运算成为可能。
电路
香农在他著名的硕士论文《继电器与开关电路的符号分析》中详述了如何通过电路实现逻辑运算，这给计算机的实现提供了有力的理论基础。
事实上，全加器就是一系列逻辑运算的总和。
继电器
继电器示意图
继电器与电报机。
电报机在按下一个开关后，实际上是接通了电路，
我们可以想象，
电报机A和继电器相连，
电报机按下按键后，继电器的开关闭合，
电磁线圈通电后带动弹簧片位移，
与继电器相连的另一个电路被接通，
这个另一个电路实际上连接着电报机B（接收方），
这样电报机B就接收到了电报机A发送的消息。
继电器与逻辑电路
上文描述的继电器其实不属于一种逻辑电路，
但是如果，
继电器开关闭合，与继电器相连的电路断开，那么我们就实现了一个简单的非门电路。
如果让两个继电器串联，那么就实现了一个与门电路。
反之，如果两个继电器并联，就实现了一个或门电路。
继电器与现代计算机
继电器属于物理设备，受物理学的限制，机械运动相对效率较低因此由继电器构成的计算机运行缓慢。
其中比较有名的是马克一号计算机，1944年诞生，由3000多个继电器组成。
值得一提的是，马克一号虽然是继电器计算机，运行速度缓慢，但其使用了二进制，同时可编程，所以实际上算是真正意义上的计算机。
继电器之后出现了真空管，只有又出现了晶体管，集成电路，于是计算器的运算速度一步步加快。
晶体管的发明者，诺贝尔奖获得者肖克利在发明了晶体管后，召集了一群精英一同研制并销售晶体管。后来他手下的八个人，史称八叛徒组建了赫赫有名的仙童公司。后来仙童公司日落西山，曾经仙童公司的当家，诺伊斯和摩尔（提出摩尔定律的那个男人）成立了另一家公司，就是英特尔。
全加器的“软件”部分
全加器这个名字，看起来好像是要做数学加法。可实际上内部做的都是逻辑运算。
这也就是为什么只要我们有继电器，我们就可以自己动手做一个全加器的原因，
乃至我们可以做一台计算机的原因。
因为计算机实际上就是逻辑计算的总和。
半加器
全加器实际上是半加器的组合，所以要了解全加器，首先我们需要知道什么是半加器。
首先来看A和B两个1bit数字，相加时的效果。
| A | B | sum |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 10 |
当A和B同时为1时，计算结果溢出了。
因为我们的全加器只支持1bit的计算，所以无法保存10这个2bit的数据。
那么显然，我们需要两个输出来保证我们不会丢失信息。
| A | B | sum | carry |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 |
我们把A和B相加的结果，分别存放在sum输出和carry输出中，
其中，sum表示A和B相加之后原始位的结果，carry表示是否产生进位。
Carry
通过观察Carry，我们可以发现，Carry实际上是A和B进行与操作之后的结果。
Sum
对于sum来说，我们现有的非，与，或操作都无法满足，所以我们需要对逻辑门进行组合。
第一次尝试：
与非门
通过将与门和非门串联，我们可以实现如下的表格。
| A | B | A NAND B |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 0 |
我们希望实现，当A或者B其中有一个为1时，结果为1，否则结果为0。
通过观察或门和与非门的结果我们发现，
他们在A和B为1时输出的结果相同（都为1），而当A和B为其他值时输出的结果相异。
那么，什么门可以保证我们在两个输入当且仅当其都为1时，输出1呢，那就是与门。
| A | B | A NAND B | A |
(A NAND B) |
|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 |
对于最右侧一列，我们就通过逻辑计算求出了sum。
同时，这样的逻辑门的组合我们也给它一个名字，异或XOR。
到此为止，我们通过将A和B输入与门得到了进位，通过将A和B输入异或门，得到了当前位的sum值。
异或门的内部逻辑
半加器图示
全加器
在半加器中，我们输出了进位，很明显，在实际计算中，当我们计算A和B的加法时，进位也可能成为输入。
所以在二进制的1bit计算中，我们应该有三个输入：A，B，进位。
让我们画一个完整的表格。
| A | B | cin | sum | cout |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Sum
先将A和B放入半加器试试。
sum(A,B)表示A和B放入半加器后的sum输出。
c(A,B)表示A和B放入半加器后的carry输出。
| A | B | sum(A,B) | c(A, B) | cin | sum | cout |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 |
把多余的部分去除。
| sum(A,B) | cin | sum |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 0 |
神奇的事情发生了，
原来全加器的sum输出，就是sum(A,B)和cin作为输入，再进行一次半加器的输出。
sum(sum(A, B), cin) = sum
用符号表示。XOR（）
Carry
那同理，cin和A，B半加器的进位输出，我们用c(sum(A,B), cin)表示。
| A | B | cin | c(A,B) | c(sum(A,B), cin) | cout |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 1 |
如果我们只关注后三列的话，
| c(A,B) | c(sum(A,B), cin) | cout |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 0 | 0 |
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| c(A,B) | c(sum(A,B), cin) | cout |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
我们发现，其实
用逻辑运算表示的话，
全加器的结构
实现多bit运算
当我们实现了一个全加器后，我们就实现了1bit运算。
自然而然的，我们将多个全加器级联后，就构成了多比特加法器。
多个全加器级联
例如上图，我们构建了一个6bit的加法器。
例如我们输入A（001010）和B（100101），X表示进位。
这里如果我们在首次计算时，X置为0表示加法计算，置为1表示减法计算。
从A和B的低位开始依次计算。
和
的sum结果作为
输出，进位输出作为下一个全加器的输入，以此类推。
最后我们得到加法结果为，如果C不为0，则表示计算结果溢出。
