讲解半加器、全加器、多位加法器和补码加减电路,梳理无符号与有符号标志位,并覆盖移位加法乘法、顺序与阵列乘法器及二进制除法。
运算器处理的是位串。加法器不会自行判断操作数是无符号数还是补码;“进位”“溢出” 和结果应如何解释,取决于指令或题目规定的数据类型。计算题必须把位级结果和数值语义分开讨论。
# 一、加法运算电路
# 1. 半加器
半加器只对两个输入位 相加,输出和 与进位 :
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
半加器不能处理低位传来的进位,因而不足以直接构成普通多位加法器。
# 2. 全加器
全加器多了输入进位 ,输出和 与输出进位 :
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
例题 2.7:全加器的输入输出
设 、、,求全加器输出。
【解】
故输出为 ,与 一致。
# 3. 多位加法器与进位传播
把 个全加器从低位到高位串联,前一级的 接到后一级的 ,得到串行进位加法器(ripple-carry adder)。它结构简单,但最高位必须等待低位进位逐级传递,最坏延迟随 线性增长。
可用如下生成项和传递项预先计算进位:
这类思想构成先行进位加法器(carry-lookahead adder):硬件并行展开若干级进位,换取更低延迟与更高电路代价。考试中若未特别说明电路结构,通常关注补码结果与溢出判定,不要求画出门级网表。
# 二、加减统一与标志位
# 1. 补码减法
补码中
因此无需独立的减法器。令控制信号 为 或 ,逐位计算 ,并把最低位输入进位置为 :
flowchart LR
A[n 位操作数 A] --> ADD[n 位加法器]
B[n 位操作数 B] --> XOR[对 B 逐位执行 XOR Sub]
SUB[Sub 控制信号] --> XOR
SUB -->|最低位进位 Cin| ADD
XOR --> ADD
ADD --> F[n 位结果 F]
ADD --> FLAGS[标志位<br/>ZF、SF、CF、OF]当 时, 且 ,完成 ;当 时, 且 ,完成 。
# 2. 标志位的含义
设 为 位结果, 是最高位向外的进位, 是进入最高位的进位。
| 标志位 | 常见判定 | 语义 |
|---|---|---|
| ZF | 结果为零 | |
| SF | 结果按补码解释时为负 | |
| CF | 加法时常取 | 无符号加法是否向位宽外产生进位 |
| OF | 补码有符号加减是否超出范围 |
对补码加法,OF 也可用 “同号相加、异号得结果” 判断:两个正数相加得负数,或两个负数相加得正数,均表示溢出。异号相加不可能发生补码加法溢出。
例题 2.8:区分 CF 与 OF
用 4 位补码计算 ,并判断 CF 与 OF。
【解】
相加得到
结果位串按补码解释为 ,而数学结果应为 ,超过 4 位补码范围 。进入最高位的进位为 ,最高位向外进位为 ,故
没有向位宽外的进位,故 。所以本题是有符号溢出而非无符号溢出。
减法中 CF 的命名与 “借位” 之间的对应由具体 ISA 规定:有的体系把 CF 解释为借位,有的把它解释为 “不借位”。除非题目给出定义,不应把某种机器的 CF 约定当作普遍结论;补码 OF 的判定规则不受这一命名差异影响。
# 三、乘法运算
# 1. 移位加法的基本思想
二进制长乘法与十进制长乘法相同。若乘数第 位为 ,便把被乘数左移 位后累加;该位为 时不累加。对 位无符号数,完整乘积最多需要 位。
例如:
即 。
# 2. 软件移位加法
没有专用乘法指令或硬件乘法器时,可用 “检测乘数最低位、条件累加、移位” 的循环实现无符号乘法:
1 | uint32_t multiply(uint32_t multiplicand, uint32_t multiplier) { |
上面的位宽有限;若数学乘积超过目标类型能表示的范围,返回值会按该语言和类型规则截断或环绕。算法思路本身不等于 “任何语言中都无溢出”。
# 3. 顺序乘法器与阵列乘法器
顺序乘法器将移位加法分散到多个时钟周期中。典型寄存器包括被乘数 、乘数 、部分积 与计数器;每轮查看 的最低位:
flowchart TB
A[初始化<br/>P = 0,M 为被乘数,Q 为乘数,计数器 = n] --> B{Q 的最低位是否为 1}
B -->|是| C[P = P + M]
B -->|否| D[M 左移一位<br/>Q 右移一位<br/>计数器减 1]
C --> D
D --> E{计数器是否为 0}
E -->|否| B
E -->|是| F[P 为乘积]阵列乘法器把部分积生成和加法单元按二维阵列连接,可并行处理更多位,延迟较低但面积、功耗和布线成本更高。顺序乘法器是 “时间换硬件”,阵列乘法器是 “硬件换时间”。
有符号乘法需额外处理符号扩展或采用 Booth 编码等算法;若题目未特别指定,不能把无符号移位加法的每一步直接照搬到补码有符号数。
# 四、除法运算
# 1. 二进制长除法
二进制除法可以从被除数最高位开始反复执行 “左移当前余数、引入下一位、与除数比较、必要时相减”:
- 当前部分余数不小于除数时,商的当前位取 ,并用当前余数减除数。
- 当前部分余数小于除数时,商的当前位取 ,余数保持。
- 继续引入被除数下一位,直至全部处理完毕。
- 最后保留的部分余数即为余数。
以 为例:
即 余 。
# 2. 顺序除法器
顺序除法器通常以寄存器保存部分余数、除数、被除数和商。每一轮先左移部分余数并引入被除数下一位,再尝试减去除数;若结果非负,则保留差并把商位写 ,否则恢复原余数并把商位写 。这就是恢复余数法的核心思想。
除法需要另行处理以下边界:
- 除数为 ,结果无数学意义,应触发异常或由软件定义。
- 有符号数的商通常向 截断,余数的符号规则取决于 ISA 或语言。
- 最小补码负数除以 的数学商超出同宽补码表示范围。
# 本节考点
- 半加器、全加器的逻辑表达式和真值表。
- 串行进位加法器的进位传播,以及先行进位的生成项、传递项思想。
- 用 将补码减法统一为加法。
- ZF、SF、CF、OF 的含义,尤其是无符号进位与补码溢出的区别。
- 移位加法、顺序乘法器、阵列乘法器与二进制长除法的基本过程。
