第二十六课:ALU 为什么先置零,再取反

从输出 y 和计算 y−1 的需求出发,理解输入置零、按位取反及其处理顺序。

本章目录CONTENTS ↓

上一课的电路只能选择 x & y 或 x + y。现在增加两个需求:无论 x 是多少,都能输出 y;也能计算 y−1。能否继续使用已有的加法器,而不为每个需求各造一条运算通路?

另接一条直接输出 y 的通路,再造一颗减一芯片,当然可行,但最后需要从更多结果中选择。Hack ALU 采用的办法是:在运算前改变送入运算部件的值。因为 0+y=y,只要把加法器的一条输入变成 0,就能输出 y;如果把它变成 −1,就能计算 −1+y=y−1。这里讨论的是这份规格的设计理由。官方 Chapter 2:ALU 规格与设计

怎样从同一条输入得到 0 和 −1

先看 x 这一侧。输入预处理(input preprocessing)发生在按位与、加法之前;它改变的是 ALU 内部送往这些部件的信号,外部提供的 x 仍保持原值。

Hack ALU 为这一侧设置两个控制位:

  • zx:是否把这一侧置零(zeroing)。为 1 时,选用 16 位全 0;为 0 时,保留原输入。
  • nx:是否对置零步骤的结果做按位取反(bitwise NOT)。为 1 时,每一位 0 变 1、1 变 0;为 0 时,保留该结果。

先按 zx 决定是否置零,再按 nx 决定是否取反。 我们把最终送入运算部件的信号叫作 xReady;这是自己起的内部连线名。官方 ALU.hdl:输入处理顺序

zx nx 置零步骤之后 取反步骤之后:xReady
0 0 原始 x 原始 x
0 1 原始 x ~x,即逐位取反后的 x
1 0 16 位全 0 16 位全 0,即 0
1 1 16 位全 0 16 位全 1,按补码解释为 −1

最后一行为什么得到 −1?取反把 16 个 0 变成 16 个 1。全 1 的无符号值是 2¹⁶−1;按此前学过的补码规则,最高位为 1 时,用这个值减去 2¹⁶,得到 (2¹⁶−1)−2¹⁶=−1。因此,这两个控制位可以在不依赖原始 x 的情况下产生 0 或 −1。

nx 的 n 可以联系英文 negate 来记,但这里的具体操作是 bitwise NOT。它不会自动加 1,所以不能把 nx=1 理解成“求 −x”。例如 x=5 的 16 位表示是 0000 0000 0000 0101;逐位取反得到 1111 1111 1111 1010,按补码解释为 −6。再加 1 才得到 −5。

用已有芯片实现这两步

“保留原值还是改成 0”是一次选择;“保留当前值还是取反”又是一次选择。两颗 Mux16 和一颗 Not16 就能实现:

Mux16(a=x, b=false, sel=zx, out=xZeroed);
Not16(in=xZeroed, out=xInverted);
Mux16(a=xZeroed, b=xInverted, sel=nx, out=xReady);

这里 b=false 接到 16 位端口,表示整条 16 位全 0 总线。xZeroed 是第一步的结果,xInverted 是它的按位反值;第二颗选择器决定把哪一条接到 xReady。HDL 描述的是这些部件之间的连接,处理顺序来自信号如何流过电路。

y 侧采用相同结构,只把输入换成 y,控制位换成 zy、ny:

Mux16(a=y, b=false, sel=zy, out=yZeroed);
Not16(in=yZeroed, out=yInverted);
Mux16(a=yZeroed, b=yInverted, sel=ny, out=yReady);

上一课的运算部件随后接收 xReady 和 yReady:

And16(a=xReady, b=yReady, out=andResult);
Add16(a=xReady, b=yReady, out=sumResult);
Mux16(a=andResult, b=sumResult, sel=f, out=selected);

这九行是逐步构造 ALU 的接线片段。完整芯片还需要输出取反控制位 no,以及状态输出 zr、ng;后续再补齐。本课固定 no=0,所以最终主输出就是 selected。这些片段还不能直接通过完整的官方 ALU 测试。

跟着一个例子,看需求怎样实现

设原始输入 x=5、y=3,选择加法 f=1,并保持 zy=0、ny=0、no=0。因此 yReady 始终是 3,输出不再取反。现在只改变 zx 和 nx:

zx nx xReady 加法器实际接收的值 最终 out
0 0 5 5 + 3 0000 0000 0000 1000(8)
1 0 0 0 + 3 0000 0000 0000 0011(3,即 y)
1 1 −1 −1 + 3 0000 0000 0000 0010(2,即 y−1)

第三行的实际比特相加是:

1111 1111 1111 1111
+ 0000 0000 0000 0011
---------------------
1 0000 0000 0000 0010

Add16 保留低 16 位,所以得到 2。这沿用了此前的补码加法,并没有新增一套减法电路。一般地,zx=1、nx=1 总会让 xReady 成为全 1;保持 y 不变并选择加法,就得到 y−1 的低 16 位。若数学结果超出补码范围,仍遵守固定位数的回绕规则。

这也说明了为什么要先置零,再取反:两者都启用时,x → 0 → 全1,能产生 −1。若调换这两个步骤,则是 x → ~x → 0,最终只能得到 0,刚才的 y−1 就变成了 y。顺序决定了能够实现哪些函数。

以后在 Hack 程序中执行“某个值减一”的指令时,CPU 就可以给 ALU 设置相应控制位,把一侧输入变为 −1,再让加法器完成运算。当前 Project 2 的任务,就是把这种控制关系接成符合规格的电路。

本课的核心是:先让输入变成需要的形式,再交给已有的运算部件。 读完后可以沿接线核对上表,尤其检查 zx=1、nx=1 时是否得到全 1。学完告诉我,我们再按一次一题的方式练习。

参考资料:官方 ALU.hdl、官方 Chapter 2、官方 Project 2 分阶段测试。资料供自愿查阅。

这一页,先记到这里。