Boolean Arithmetic

1.1 二进制数

十进制以 10 为基底，二进制则以 2 为基底。当遇到二进制数10011且已知其代表整数时，十进制值计算方式如下：
$(10011)_{\text{two}} = 1 \cdot 2^4 + 0 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0 = 19$

令$x = x_n x_{n-1} \dots x_0$，在以 b 为基底的 x 值表示为$(x)_b$，并定义公式如下：
$(x_n x_{n-1} \dots x_0)_b = \sum_{i=0}^{n} x_i \cdot b^i$
当$b=2$时即为二进制转十进制的通用公式。
Example：32 位计算机存储十进制数 19 时，寄存器中的值为0000000000000000000000000010011。

1.2 二进制加法

二进制加法是简单而基本的操作，大部分数字计算机执行的操作能够简化为基本的二进制数的加法。因此，要实现大量依赖于二进制加法的计算机操作，其关键是要从构造的角度来理解二进制加法。

两个二进制数从右至左（从最低有效位LSB，Least Significant Bits到最高有效位MSB，Most Significant Bits）逐位相加：

1. 先加最右端两位（LSB），产生的进位传递到下一位相加；
2. 重复上述过程直到处理完最左端两位（MSB）；
3. 若最高位相加后产生进位1，称为溢出，否则加法运算成功执行。

加法示例如下：

1.3 有符号二进制数

n 位二进制系统共可产生$2^n$种组合，若需用二进制表示有符号数，通常采用2-补码（2’s complement，又称基补码 radix complement） 编码，几乎所有现代计算机均采用该编码方式。

2 补码定义

n 位系统中数 x 的 2 补码$\bar{x}$定义为：
$\bar{x} = \begin{cases} 2^n - x & \text{if } x \neq 0 \\ 0 & \text{otherwise} \end{cases}$

Example：5 位二进制系统中，-2（原码00010）的补码为$2^5 - 2 = 30 = (11110)_{\text{two}}$。
Proof：$00010 + 11110 = 100000$，丢弃第 6 位（溢出位）后得到00000，符合补码加法规则。

4 位补码系统属性

从而我们归纳出如下特征：

1. 可编码全部$2^n$个有符号数，范围为$-2^{n-1}$到$2^{n-1}-1$；
2. 所有正数首位为0，所有负数首位为1；
3. 求-x的编码有两种等价方法：
   • 保留最右边的0和第一个1，剩余位全部取反；
   • 对x的所有位取反后加1（硬件更易实现）；
4. 补码加减法完全统一：任意两个补码数的加法无需区分正负，直接按二进制加法计算即可；减法可转换为$x - y = x + (-y)$，无需额外硬件支持。

2.1 加法器（Adders）

加法器分成三类：

• 半加器（Half-adder）：用来进行两位加法。
• 全加器（Full-adder）：用来进行三位加法。
• 加法器（Adder）：用来进行两位 n-位加法。

Example：半加器

NOTE

sum 用于保留低位，carry 用于保留进位。在这里可以认为需要进位时 carry 为 1，不需要进位时 sum 为 1。

全加器和加法器也是类似的，在这里不进行赘述。
值得一提的是，有一种特殊的加法器，称为增量器（incrementer），用来对指定的数字加 1。

2.2 算术逻辑单元（ALU）

ALU（算术逻辑单元）是本章最终构建的核心组件，是 CPU 的核心单元，执行计算机所有的算术和逻辑操作，是理解 CPU 及整个计算机工作原理的关键。
我们会基于第一章构建的基础逻辑门、本章前半部分实现的加法器（半加器、全加器、Add 16、Inc 16）搭建而成。

Hack（我们目标打造的计算机） 的 ALU 计算一组固定的函数 out = f(x,y)，
其中：

• x和 y是芯片的两个 16-位输入
• out是芯片的 16-位输出
• f是位于一个函数表中的函数,该函数表由 18 个固定函数组成。

我们通过设置六个称为控制位(controlbits)的输入位来告诉 ALU 用哪一个函数来进行何种函数计算。

NOTE

这 6 个控制位的每一位都会指示 ALU 来执行某个基本操作。这些操作的各种组合可以让 ALU 计算出 $2^6=64$个不同的函数进行操作。