讲解半加器、全加器、多位加法器和补码加减电路,梳理无符号与有符号标志位,并覆盖移位加法乘法、顺序与阵列乘法器及二进制除法。

运算器处理的是位串。加法器不会自行判断操作数是无符号数还是补码;“进位”“溢出” 和结果应如何解释,取决于指令或题目规定的数据类型。计算题必须把位级结果和数值语义分开讨论。

# 一、加法运算电路

# 1. 半加器

半加器只对两个输入位 A,BA,B 相加,输出和 SS 与进位 CC:

S=A⊕B,C=A⋅B.\boxed{ S=A\oplus B,\qquad C=A\cdot B }.

AABBSSCC
0000
0110
1010
1101

半加器不能处理低位传来的进位,因而不足以直接构成普通多位加法器。

# 2. 全加器

全加器多了输入进位 CinC_{\mathrm{in}},输出和 SS 与输出进位 CoutC_{\mathrm{out}}:

S=A⊕B⊕Cin,\boxed{ S=A\oplus B\oplus C_{\mathrm{in}} },

Cout=AB+Cin(A⊕B).\boxed{ C_{\mathrm{out}}=A B+C_{\mathrm{in}}(A\oplus B) }.

AABBCinC_{\mathrm{in}}SSCoutC_{\mathrm{out}}
00000
00110
01010
01101
10010
10101
11001
11111
例题 2.7:全加器的输入输出

设 A=1A=1、B=1B=1、Cin=1C_{\mathrm{in}}=1,求全加器输出。

【解】

S=1⊕1⊕1=1,S=1\oplus1\oplus1=1,

Cout=1⋅1+1⋅(1⊕1)=1.C_{\mathrm{out}}=1\cdot1+1\cdot(1\oplus1)=1.

故输出为 CoutS=11\boxed{C_{\mathrm{out}}S=11},与 1+1+1=31+1+1=3 一致。

# 3. 多位加法器与进位传播

把 nn 个全加器从低位到高位串联,前一级的 CoutC_{\mathrm{out}} 接到后一级的 CinC_{\mathrm{in}},得到串行进位加法器(ripple-carry adder)。它结构简单,但最高位必须等待低位进位逐级传递,最坏延迟随 nn 线性增长。

可用如下生成项和传递项预先计算进位:

gi=AiBi,pi=Ai⊕Bi,g_i=A_iB_i,\qquad p_i=A_i\oplus B_i,

Ci+1=gi+piCi.C_{i+1}=g_i+p_iC_i.

这类思想构成先行进位加法器(carry-lookahead adder):硬件并行展开若干级进位,换取更低延迟与更高电路代价。考试中若未特别说明电路结构,通常关注补码结果与溢出判定,不要求画出门级网表。

# 二、加减统一与标志位

# 1. 补码减法

补码中

[A−B]补=[A]补+[−B]补=[A]补+[B]补‾+1.\boxed{ [A-B]_{\mathrm{补}} =[A]_{\mathrm{补}}+[-B]_{\mathrm{补}} =[A]_{\mathrm{补}}+\overline{[B]_{\mathrm{补}}}+1 }.

因此无需独立的减法器。令控制信号 Sub\mathrm{Sub} 为 00 或 11,逐位计算 Bi⊕SubB_i\oplus\mathrm{Sub},并把最低位输入进位置为 Sub\mathrm{Sub}:

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]

当 Sub=0\mathrm{Sub}=0 时,B⊕0=BB\oplus0=B 且 Cin=0C_{\mathrm{in}}=0,完成 A+BA+B;当 Sub=1\mathrm{Sub}=1 时,B⊕1=B‾B\oplus1=\overline B 且 Cin=1C_{\mathrm{in}}=1,完成 A+B‾+1=A−BA+\overline B+1=A-B。

# 2. 标志位的含义

设 FF 为 nn 位结果,CnC_n 是最高位向外的进位,Cn−1C_{n-1} 是进入最高位的进位。

标志位常见判定语义
ZFF=0F=0结果为零
SFFn−1=1F_{n-1}=1结果按补码解释时为负
CF加法时常取 CnC_n无符号加法是否向位宽外产生进位
OFCn−1⊕CnC_{n-1}\oplus C_n补码有符号加减是否超出范围

对补码加法,OF 也可用 “同号相加、异号得结果” 判断:两个正数相加得负数,或两个负数相加得正数,均表示溢出。异号相加不可能发生补码加法溢出。

例题 2.8:区分 CF 与 OF

用 4 位补码计算 7+17+1,并判断 CF 与 OF。

【解】

7=(0111)2,1=(0001)2.7=(0111)_2,\qquad1=(0001)_2.

相加得到

0111+0001=1000.0111+0001=1000.

结果位串按补码解释为 −8-8,而数学结果应为 88,超过 4 位补码范围 [−8,7][-8,7]。进入最高位的进位为 11,最高位向外进位为 00,故

OF=1⊕0=1.\mathrm{OF}=1\oplus0=1.

没有向位宽外的进位,故 CF=0\mathrm{CF}=0。所以本题是有符号溢出而非无符号溢出。

减法中 CF 的命名与 “借位” 之间的对应由具体 ISA 规定:有的体系把 CF 解释为借位,有的把它解释为 “不借位”。除非题目给出定义,不应把某种机器的 CF 约定当作普遍结论;补码 OF 的判定规则不受这一命名差异影响。

# 三、乘法运算

# 1. 移位加法的基本思想

二进制长乘法与十进制长乘法相同。若乘数第 ii 位为 11,便把被乘数左移 ii 位后累加;该位为 00 时不累加。对 nn 位无符号数,完整乘积最多需要 2n2n 位。

例如:

10112×11102=10112≪1+10112≪2+10112≪3=100110102.1011_2\times1110_2 =1011_2\ll1+1011_2\ll2+1011_2\ll3 =10011010_2.

即 11×14=15411\times14=154。

# 2. 软件移位加法

没有专用乘法指令或硬件乘法器时,可用 “检测乘数最低位、条件累加、移位” 的循环实现无符号乘法:

1
2
3
4
5
6
7
8
9
10
11
12
13
uint32_t multiply(uint32_t multiplicand, uint32_t multiplier) {
uint32_t product = 0;

while (multiplier != 0) {
if ((multiplier & 1U) != 0) {
product += multiplicand;
}
multiplicand <<= 1;
multiplier >>= 1;
}

return product;
}

上面的位宽有限;若数学乘积超过目标类型能表示的范围,返回值会按该语言和类型规则截断或环绕。算法思路本身不等于 “任何语言中都无溢出”。

# 3. 顺序乘法器与阵列乘法器

顺序乘法器将移位加法分散到多个时钟周期中。典型寄存器包括被乘数 MM、乘数 QQ、部分积 PP 与计数器;每轮查看 QQ 的最低位:

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. 二进制长除法

二进制除法可以从被除数最高位开始反复执行 “左移当前余数、引入下一位、与除数比较、必要时相减”:

  1. 当前部分余数不小于除数时,商的当前位取 11,并用当前余数减除数。
  2. 当前部分余数小于除数时,商的当前位取 00,余数保持。
  3. 继续引入被除数下一位,直至全部处理完毕。
  4. 最后保留的部分余数即为余数。

以 15÷215\div2 为例:

11112÷102=1112,余12,1111_2\div10_2=111_2\text{,余 }1_2,

即 15÷2=715\div2=7 余 11。

# 2. 顺序除法器

顺序除法器通常以寄存器保存部分余数、除数、被除数和商。每一轮先左移部分余数并引入被除数下一位,再尝试减去除数;若结果非负,则保留差并把商位写 11,否则恢复原余数并把商位写 00。这就是恢复余数法的核心思想。

除法需要另行处理以下边界:

  • 除数为 00,结果无数学意义,应触发异常或由软件定义。
  • 有符号数的商通常向 00 截断,余数的符号规则取决于 ISA 或语言。
  • 最小补码负数除以 −1-1 的数学商超出同宽补码表示范围。

# 本节考点

  • 半加器、全加器的逻辑表达式和真值表。
  • 串行进位加法器的进位传播,以及先行进位的生成项、传递项思想。
  • 用 B‾+1\overline B+1 将补码减法统一为加法。
  • ZF、SF、CF、OF 的含义,尤其是无符号进位与补码溢出的区别。
  • 移位加法、顺序乘法器、阵列乘法器与二进制长除法的基本过程。