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：半加器

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

2.2 算术逻辑单元（ALU）

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

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

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

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