这次回顾第二章的内容，这部分主要介绍了布尔运算，讲解了如何实现二进制加法，负数的表示以及算数逻辑单元（ALU）。

课程官网：

https://www.nand2tetris.org/

视频地址：

https://www.coursera.org/learn/build-a-computer

Chapter 2 布尔运算

Part 1：课程回顾

这部分回顾一些重点内容。

二进制加法

来看一个二进制加法的例子：

从上述例子不难看出，最后一位只要考虑两个数相加的问题，处理这部分使用HalfAdder，接口如下：

除最后一位以外，其余每一位还要考虑前一位的进位问题，所以要处理三个数相加的问题，处理这部分使用FullAdder，接口如下：

最后要注意计算机存储数字的位数是固定的，如果超过这个范围，就会产生溢出：

处理方法是直接不考虑溢出位。假设计算机存储的位数为$n$，那么$x+y$的结果为

负数

一个比较关键的问题是如何在计算机中表示负数，一个直接的想法是用第一位表示符号，$0$表示正数，$1$表示负数，但是这样$0$会有两个表示：

并且

实际中使用的是补码表示，即

现在考虑

由定义可得

所以这样定义的表示方式满足常见的负数加法运算，例如

因为

所以如果我们能计算出$-y$，那么减法运算可以直接获得。现在给定$x$，由定义可得

而

所以$(2^n-1)-x$表示对每一位取反的操作，因此$-x$可以通过对每一位取反然后加$1$得到。

算数逻辑单元（ALU）

首先回顾冯诺依曼结构计算机的基本组成部分：

这一部分介绍算数逻辑单元（ALU），一般的ALU输入输出如下：

其中$f$为一族事先定义好的算数和逻辑函数。该课程中编写的计算机名为Hack，其ALU的形式稍有不同：

其接口如下

通过真值表，不难验证其输出如下：

Part 2：项目

这一次的项目实现加法器以及算数逻辑单元（ALU）

HalfAdder

半加器对两个比特位进行加法，输入为$a,b$，输出为和sum以及进位carry：

$a$ $b$ $\text{sum}$ $\text{carry}$
$0$ $0$ $0$ $0$
$0$ $1$ $1$ $0$
$1$ $0$ $1$ $0$
$1$ $1$ $0$ $1$

由上述真值表，不难看出

FullAdder

全加器对三个比特位进行加法，输入为$a,b,c$，实现思路很简单，先对$a,b$使用使用半加器，得到

然后对$c,d$使用半加器，得到

最后不难看出

Add16

计算16个比特位的加法，输入为$a[16], b[16]$，输出为$\text{out}[16]$。对$a[0],b[0]$使用半加器，得到$\text{sum}=\text{out}[0]$，记录进位$\text{carry}$，然后从第二位开始，使用全加器，计算$a[i],b[i]$和前一位的进位的和，以此类推。

Inc16

对16个比特位加$1$，第一位使用半加器加$1$，其余每位和上一位的进位相加即可。

另解，直接增加1即可：

CHIP Inc16 {
    IN in[16];
    OUT out[16];

    PARTS:
   // Put you code here:
   Add16(a=in, b[1..15]=false, b[0]=true, out=out);
}

ALU

根据提示即可，这里需要注意的一点是可以有多个输出：

Mux16 (a=out1, b=out2, sel=no, out=out, out[0..7]=o1, out[8..15]=o2, out[15]=ng);