第二章 布尔算术

导读

在掌握了布尔逻辑的基础之后，本章将探索如何使用逻辑门执行算术运算。算术逻辑单元(ALU)是计算机的核心组件之一，负责执行所有的基本算术和逻辑运算。

本章的学习目标是从最基本的加法器开始，逐步构建出能够执行加减乘除运算的ALU。我们将学习二进制数的表示方法，理解补码系统的原理，并掌握各种算术电路的设计方法。

通过本章的学习，你将理解计算机如何进行数学运算，并为后续章节中构建完整的处理器奠定基础。ALU的设计是计算机体系结构中最关键的部分之一，它直接影响计算机的性能和功能。

核心概念详解

2.1 二进制数系统

计算机使用二进制系统表示和处理数据。理解二进制数是理解计算机算术的基础。

无符号二进制数

一个n位无符号二进制数可以表示0到2^n-1之间的整数：

数值 = b[n-1]×2^(n-1) + b[n-2]×2^(n-2) + ... + b[1]×2^1 + b[0]×2^0

例如，8位二进制数10110101表示：

1×2^7 + 0×2^6 + 1×2^5 + 1×2^4 + 0×2^3 + 1×2^2 + 0×2^1 + 1×2^0
= 128 + 32 + 16 + 4 + 1
= 181

有符号二进制数：补码表示

为了表示负数，计算机使用补码系统。在n位补码系统中：

• 最高位(符号位)为0表示正数或零
• 最高位为1表示负数
• 可表示的范围是-2^(n-1)到2^(n-1)-1

补码的计算方法：

• 正数的补码是其本身
• 负数的补码是将其绝对值的二进制表示取反后加1

例如，在8位系统中表示-5：

5的二进制：00000101

取反：11111010

加1：11111011

所以-5的8位补码表示是11111011。

补码的优势

补码系统有几个重要优势：

零的表示唯一：只有一种零的表示(全0)

加减法统一：加法和减法可以使用相同的电路

溢出检测简单：可以通过简单的规则检测溢出

2.2 加法器设计

加法器是算术运算的基础。我们从半加器开始，逐步构建完整的加法器。

半加器(Half Adder)

半加器实现两个单比特数的加法，产生和(Sum)与进位(Carry)：

输入：a, b
输出：sum, carry

sum = a XOR b
carry = a AND b

真值表：

全加器(Full Adder)

全加器实现两个单比特数和进位输入的加法：

输入：a, b, carryIn
输出：sum, carryOut

sum = a XOR b XOR carryIn
carryOut = (a AND b) OR (carryIn AND (a XOR b))

真值表：

行波进位加法器(Ripple Carry Adder)

将多个全加器级联可以构建多位加法器。例如，16位加法器需要16个全加器：

CHIP Add16 {
    IN a[16], b[16];
    OUT out[16];
    
    PARTS:
    FullAdder(a=a[0], b=b[0], c=carry0, sum=out[0], cout=carry1);
    FullAdder(a=a[1], b=b[1], c=carry1, sum=out[1], cout=carry2);
    // ... 继续到第16位
}

行波进位加法器的缺点是进位信号需要逐级传播，导致延迟较大。对于n位加法器，最坏情况下的延迟是O(n)。

超前进位加法器(Carry Lookahead Adder)

为了减少延迟，可以使用超前进位技术。通过并行计算进位信号，可以将延迟降低到O(log n)。

超前进位的基本思想是定义两个中间信号：

• 生成信号(Generate)：G[i] = a[i] AND b[i]
• 传播信号(Propagate)：P[i] = a[i] XOR b[i]

进位信号可以表示为：

c[i+1] = G[i] OR (P[i] AND c[i])

通过展开这个递推关系，可以直接计算每个进位信号，而不需要等待前一级进位。

2.3 减法器设计

在补码系统中，减法可以转换为加法：

A - B = A + (-B) = A + (~B + 1)

因此，减法器可以通过在加法器的基础上添加取反电路来实现。

16位ALU中的减法实现

在ALU中，我们使用一个控制信号来控制是执行加法还是减法：

• 当sub=0时，执行加法：out = a + b
• 当sub=1时，执行减法：out = a - b = a + ~b + 1

实现方法：

使用sub信号控制b的取反

将sub信号作为加法器的进位输入

2.4 算术逻辑单元(ALU)

ALU是计算机的核心运算组件，能够执行多种算术和逻辑运算。Nand2Tetris中的ALU具有以下特性：

ALU功能规格

输入：
- x[16], y[16]：两个16位输入
- zx, nx：控制x的零化和取反
- zy, ny：控制y的零化和取反
- f：控制加法或AND运算
- no：控制输出取反

输出：
- out[16]：16位运算结果
- zr：零标志，当out=0时为1
- ng：负标志，当out<0时为1

ALU运算流程

ALU按照以下步骤执行运算：

零化操作：

- 如果zx=1，x=0

- 如果zy=1，y=0

取反操作：

- 如果nx=1，x=~x

- 如果ny=1，y=~y

功能选择：

- 如果f=1，out=x+y

- 如果f=0，out=x AND y

输出取反：

- 如果no=1，out=~out

标志位设置：

- zr = (out == 0)

- ng = (out < 0)

ALU控制编码

通过6个控制信号(zx, nx, zy, ny, f, no)的组合，ALU可以执行18种不同的运算：

2.5 乘法器设计

乘法是更复杂的算术运算。最简单的乘法算法是移位加法。

无符号乘法

对于两个n位无符号数a和b，乘法可以通过以下步骤实现：

初始化结果result=0

对于i从0到n-1：

- 如果b的第i位为1，result = result + (a << i)

返回result

例如，计算5×3(假设4位)：

a = 0101 (5)
b = 0011 (3)

i=0: b[0]=1, result = 0 + (0101 << 0) = 0101
i=1: b[1]=1, result = 0101 + (0101 << 1) = 0101 + 1010 = 1111 (15)
i=2: b[2]=0, result不变
i=3: b[3]=0, result不变

最终结果：1111 (15)

硬件实现

硬件乘法器通常使用阵列结构：

• 生成n个部分积
• 使用加法器树将部分积累加

对于16位乘法，需要16个部分积，使用多级加法器树可以减少延迟。

2.6 除法器设计

除法是四种基本算术运算中最复杂的。常用的算法是恢复余数法和不恢复余数法。

恢复余数法

算法步骤：

初始化余数remainder=被除数，商quotient=0

对于i从n-1到0：

- remainder = remainder - (除数 << i)

- 如果remainder >= 0：

- quotient的第i位设为1

- 否则：

- quotient的第i位设为0

- remainder = remainder + (除数 << i) // 恢复余数

不恢复余数法

不恢复余数法通过避免恢复操作来提高效率：

如果余数为负，商位为0，下一步加上除数

如果余数为正，商位为1，下一步减去除数

这种方法减少了操作次数，提高了除法速度。

重要知识点

知识点1：补码系统的数学基础

补码系统基于模运算的数学原理。在n位系统中，所有运算都在模2^n的意义下进行。

关键性质：

• x + (-x) = 0 (mod 2^n)
• -x = 2^n - x (mod 2^n)
• -x = ~x + 1 (mod 2^n)

这些性质保证了补码系统中加减法的正确性。

知识点2：溢出检测

在补码运算中，溢出是一个重要问题。溢出发生在结果超出了可表示的范围。

加法溢出规则：

• 正数 + 正数 = 负数 → 溢出
• 负数 + 负数 = 正数 → 溢出
• 正数 + 负数 → 不会溢出

检测方法：

overflow = (a[n-1] == b[n-1]) && (result[n-1] != a[n-1])

即：如果两个操作数符号相同，但结果符号与操作数不同，则发生溢出。

知识点3：ALU设计的权衡

ALU设计涉及多个方面的权衡：

速度 vs 面积：

• 快速ALU使用并行计算，但需要更多硬件
• 慢速ALU使用串行计算，硬件更简单

功能 vs 复杂度：

• 功能丰富的ALU支持更多运算
• 但控制逻辑更复杂

通用性 vs 专用性：

• 通用ALU可以执行多种运算
• 专用ALU针对特定运算优化

知识点4：位级操作的重要性

许多运算可以通过位级操作高效实现：

移位操作：

• 左移n位等价于乘以2^n
• 右移n位等价于除以2^n(对于无符号数)

位掩码：

• 使用AND操作提取特定位
• 使用OR操作设置特定位
• 使用XOR操作翻转特定位

知识点5：条件码标志

ALU的条件码标志对于实现分支和跳转至关重要：

零标志(ZF)：

• 用于实现相等性判断
• 在比较操作中特别重要

负标志(NF)：

• 用于实现大小比较
• 在条件跳转中使用

溢出标志(OF)：

• 用于检测有符号数运算的溢出
• 在异常处理中使用

进位标志(CF)：

• 用于检测无符号数运算的溢出
• 在多精度运算中使用

常见误区

误区1：混淆有符号数和无符号数

一个常见的错误是混淆有符号数和无符号数的表示和运算。同一个二进制模式，根据解释方式不同，可能表示不同的数值。

例如，11111111：

• 作为无符号数：255
• 作为有符号数(补码)：-1

在进行运算时，必须明确操作数的类型，并使用相应的运算规则。

误区2：忽视溢出问题

许多初学者在实现算术运算时忽视了溢出问题。溢出会导致错误的结果，而且往往难以检测。

正确的做法是：

始终考虑溢出的可能性

实现溢出检测机制

在发生溢出时采取适当的处理措施

误区3：认为ALU只能执行固定运算

实际上，通过合理设置控制信号，ALU可以执行比规格中列出的更多的运算。例如，通过组合基本运算，可以实现更复杂的功能。

误区4：过度优化ALU设计

虽然优化ALU的性能很重要，但过度优化可能导致设计复杂度过高。在教学和原型设计中，清晰性和正确性比极致性能更重要。

误区5：不理解ALU控制信号的作用

ALU的6个控制信号看似复杂，但实际上每个信号都有明确的作用。理解每个信号的功能对于正确使用ALU至关重要。

实践应用

实践1：实现半加器和全加器

半加器HDL实现：

CHIP HalfAdder {
    IN a, b;
    OUT sum, carry;
    
    PARTS:
    Xor(a=a, b=b, out=sum);
    And(a=a, b=b, out=carry);
}

全加器HDL实现：

CHIP FullAdder {
    IN a, b, c;
    OUT sum, carry;
    
    PARTS:
    HalfAdder(a=a, b=b, sum=s1, carry=c1);
    HalfAdder(a=s1, b=c, sum=sum, carry=c2);
    Or(a=c1, b=c2, out=carry);
}

实践2：实现16位加法器

CHIP Add16 {
    IN a[16], b[16];
    OUT out[16];
    
    PARTS:
    FullAdder(a=a[0], b=b[0], c=false, sum=out[0], cout=c1);
    FullAdder(a=a[1], b=b[1], c=c1, sum=out[1], cout=c2);
    FullAdder(a=a[2], b=b[2], c=c2, sum=out[2], cout=c3);
    // ... 继续实现到第16位
    FullAdder(a=a[15], b=b[15], c=c15, sum=out[15], cout=c16);
}

实践3：实现ALU

ALU的实现需要按照规格逐步处理：

CHIP ALU {
    IN x[16], y[16], zx, nx, zy, ny, f, no;
    OUT out[16], zr, ng;
    
    PARTS:
    // 1. 零化操作
    Mux16(a=x, b=false, sel=zx, out=x1);
    Mux16(a=y, b=false, sel=zy, out=y1);
    
    // 2. 取反操作
    Mux16(a=x1, b=~x1, sel=nx, out=x2);
    Mux16(a=y1, b=~y1, sel=ny, out=y2);
    
    // 3. 功能选择
    Add16(a=x2, b=y2, out=addOut);
    And16(a=x2, b=y2, out=andOut);
    Mux16(a=andOut, b=addOut, sel=f, out=fOut);
    
    // 4. 输出取反
    Mux16(a=fOut, b=~fOut, sel=no, out=out);
    
    // 5. 设置标志位
    // zr = (out == 0)
    // ng = out[15]
}

实践4：实现移位器

左移位器：

CHIP ShiftLeft16 {
    IN in[16], shift[4];
    OUT out[16];
    
    PARTS:
    // 根据shift值选择移位量
    // shift=0: 不移位
    // shift=1: 左移1位
    // shift=2: 左移2位
    // ...
}

实践5：实现比较器

16位比较器：

CHIP Comp16 {
    IN a[16], b[16];
    OUT eq, lt, gt;
    
    PARTS:
    // eq: a == b
    // lt: a < b (有符号比较)
    // gt: a > b (有符号比较)
    
    // 可以通过ALU的减法功能实现
    // a - b，然后根据zr和ng标志判断
}

实践6：ALU测试

测试ALU时需要覆盖所有18种运算：

// 测试 out = 0
set zx 1, set nx 0, set zy 1, set ny 0, set f 1, set no 0;
eval;
// 验证 out = 0, zr = 1, ng = 0

// 测试 out = x + y
set zx 0, set nx 0, set zy 0, set ny 0, set f 1, set no 0;
set x 1234, set y 5678;
eval;
// 验证 out = 6912

本章小结

本章我们深入学习了计算机算术的原理和实现方法。从二进制数表示开始，我们逐步构建了完整的算术运算系统。

核心要点回顾

二进制数表示：理解无符号数和补码有符号数的表示方法。

加法器设计：从半加器到全加器，再到多位加法器，掌握加法电路的设计方法。

ALU设计：理解ALU的功能规格和实现方法，掌握通过控制信号选择不同运算的技术。

溢出检测：理解溢出的原因和检测方法，确保运算结果的正确性。

乘除法实现：了解基本的乘除法算法和硬件实现方法。

关键技能掌握

• 能够实现各种加法器电路
• 理解并能够实现ALU
• 掌握补码系统的原理和运算规则
• 能够进行溢出检测和处理
• 理解乘除法的基本算法

与后续章节的联系

本章构建的ALU是后续章节的基础：

• 第三章将把ALU与时序逻辑结合，构建处理器
• 第五章将在处理器的基础上构建完整的计算机体系结构
• 第六章将使用机器语言编程，直接操作ALU

学习建议

理解原理：不仅要会实现电路，更要理解其工作原理

动手实践：亲手实现每个组件，加深理解

测试验证：充分测试确保正确性

思考优化：在理解基本原理后，思考如何优化设计

通过本章的学习，你已经掌握了计算机算术的核心知识。这些知识对于理解计算机如何执行数学运算至关重要，也为后续章节的学习奠定了坚实基础。