第十八课:半加器(Half Adder),把两个比特相加

从一位二进制加法的四种情况出发,理解本位和进位,并用 XOR 与 AND 构造 HalfAdder。

本章目录CONTENTS ↓

Project 1(Boolean Logic,布尔逻辑)让我们有了逻辑门;Project 2(Boolean Arithmetic,布尔算术)要用它们做算术电路,最后构造算术逻辑单元(Arithmetic Logic Unit,ALU)。第一颗芯片是半加器(Half Adder,官方芯片名 HalfAdder):它把两个单比特 a、b 相加。结果可能是 0、1 或 2,因此输出需要两位:当前这一位叫本位和(sum),向高一位传递的叫进位(carry,这里是输出进位)。

为什么 1 + 1 需要两个输出

二进制中,1 + 1 = 10₂。写在当前位的是 0,向左一位进 1。把四种输入列出来:

a b a+b(二进制) 进位 carry 本位和 sum
0 0 00 0 0
0 1 01 0 1
1 0 01 0 1
1 1 10 1 0

把 carry 写在 sum 左边,两位合起来就是本次加法的完整结果。也可以用数值关系检查每一行:a + b = sum + 2 × carry。例如最后一行是 1 + 1 = 0 + 2 × 1。

从规格认出两颗旧芯片

观察本位和 sum:只有 a、b 不同时才是 1,这正是异或(exclusive OR,XOR;芯片名 Xor)。观察进位 carry:只有两者都是 1 才是 1,这正是逻辑与(AND;芯片名 And)。两个输出分别从相同的输入计算出来:

sum = a XOR b
carry = a AND b

因此官方的 HalfAdder 接口可以这样实现:

CHIP HalfAdder {
IN a, b;
OUT sum, carry;
PARTS:
Xor(a=a, b=b, out=sum);
And(a=a, b=b, out=carry);
}

例如 a=1、b=1 时,Xor 给出 sum=0,And 给出 carry=1,合起来是 10₂。如果只看 sum,会误以为结果是 0;进位是结果的一部分,不能丢掉。

“半”表示它只处理 a、b 两个输入位,还没有接收来自更低位的进位。下一步的全加器(Full Adder,芯片名 FullAdder)会增加这个输入;之后才能把许多位的加法串起来。

本节记住一个对应关系即可:XOR 给当前位的和,AND 给进位。已经学过的逻辑门,从这里开始变成算术电路。读完有疑问可以直接问;无需先做一轮 Project 1 测验。

参考资料:官方 Project 2:Boolean Arithmetic、官方 HalfAdder.hdl 接口。

这一页,先记到这里。