用逻辑电路做加法：把半加器当作谜题来想

在用解谜来理解与、或、非里，我写了组合、翻转真和假的三种运算。这篇文章接着往下写。计算机只用这三种运算就能做加法，做加法的最小部件叫做「半加器」。

名字听起来很难，里面其实只有两张四行的表。希望你能当作一道谜题来读。

二进制的加法

计算机内部只用0和1表示数，这叫做二进制。我们平时用的十进制，9的下一个数要进位，变成10。二进制在1的下一个数就进位。

十进制	二进制
0	0
1	1
2	10
3	11
4	100

二进制一位数相加，只有四种情况。

0＋0＝0
0＋1＝1
1＋0＝1
1＋1＝10

只有 1＋1 的答案是两位数。这和十进制的 5＋5＝10 一样：这一位留下0，向上一位进1。

把答案分成两部分

把答案分成留在这一位的数「和」，以及送到上一位的数「进位」，列成表。

A	B	和	进位
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

现在把1读成真，0读成假。和上一篇的真值表对照一下，会发现一些事情。

进位这一列，只有 A 和 B 都是1时才是1。这正是与（AND）。

和这一列，A 和 B 只有一个是1时为1，两个都是1时为0。它像或（OR），只是最后一行不同。这就是上一篇最后只提了名字的异或（XOR）。

也就是说，一位数的加法可以用「和是异或，进位是与」来计算。把这两个组合起来的电路，就是半加器。

用与、或、非做出异或

异或可以用与、或、非做出来。这就是这篇文章的谜题。

异或的意思是「至少一个为真」而且「不是两个都为真」。把这句话直接写成式子，就是这样。

和＝（A OR B） AND NOT（A AND B）

用表来确认。

A	B	A OR B	A AND B	NOT（A AND B）	和
0	0	0	0	1	0
0	1	1	0	1	1
1	0	1	0	1	1
1	1	1	1	0	0

最后一列和前面和的那一列一致了。而且中途用到的「A AND B」，正好就是进位。所以，有一个与、一个或、一个非，再加一个与，就能组成半加器。

也可以用上一篇的开关和小灯泡电路来想。串联的开关是与，并联的开关是或。半加器就是用这样的开关组合成的装置：遇到 1＋1 时，让「和」的灯熄灭，让「进位」的灯亮起来。

为什么叫「半」

半加器只能把一位和一位相加。两位以上的数相加时，还要把从下一位进上来的1一起加进去。把三个一位数相加的电路叫做「全加器」。全加器可以用两个半加器和一个或来做：先把 A 和 B 相加，再把这个和与下面来的进位相加，两个半加器中只要有一个产生进位，就向上一位送1。

按位数把全加器排成一排，每一位的进位传给旁边，就能做任意位数的加法。二进制的 11＋01（十进制的 3＋1），第一位是 1＋1，和0、进位1；第二位是 1＋0＋1，还是和0、进位1；第三位出现1，答案是 100（十进制的4）。

这和竖式加法的进位做的事完全一样。不同的只是用到的数字只有0和1两个。

想看着电路图确认半加器和全加器，可以看维基百科的加法器条目。

从余数和商来看

也可以换成算术的说法。把 A＋B 除以2，和就是「除以2的余数」，进位就是「除以2的商」。1＋1＝2，除以2，商1，余0，正好是表的最后一行。

我觉得知道这种看法很有好处。半加器既是逻辑装置，也是「相加、除以2、分成余数和商」的计算装置。逻辑和算术并不是两门不同的科目，而是用两种语言写同一件事。我想半加器把这一点表现得很清楚。

在家能玩的电路谜题

只用纸和笔，就能出下面这样的题。

只用与、或、非，写出「A 和 B 相同时才为真」的式子（就是把异或用非翻过来）
用两个半加器，写出全加器的表（8行）
把二进制的 101＋011，当作排了三个全加器，一位一位地算

第1题写出式子以后，列一张四行的真值表来确认。式子对的话，表里的各列会照预想的那样排列。不对的话，看是哪一行对不上，就能知道是在哪里把与和或弄反了。

Math Gates 的逻辑电路

Math Gates 是我在做的电路解谜游戏。在棋盘的空格上放改变数值的「门」和把方向转90度的「镜子」，按下「运行」，带着数值的「比特」就会直线前进。终点的「出口」只接收满足条件的值。

最后一个世界「逻辑电路」里，通过比较门的数会变成真或假，再通过非、与、或的逻辑门。逻辑门上写着要组合的真假值，比如「AND T」，把它和比特本身的真假组合起来。棋盘上跑的比特只有一个，所以没法组成需要同时接收两个输入的半加器本身。不过，与很严格、或很宽松、非会翻转这些性质，可以通过比特的走法一次次确认。第3个世界「余数电路」里还有求余数的门，和本文「除以2的余数」的话题连在一起。

一共7个世界140道题，面向8岁以上。可以免费玩，过关之间会有广告，一次性购买可以去除广告。玩法写在 Math Gates 上手指南里。