第十八课:半加器(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 bcarry = 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 测验。
这一页,先记到这里。