乘除运算的基本原理与实现结构

2026 大纲 二（二）3　乘/除运算（乘/除法运算的基本原理，乘法电路和除法电路的基本结构）。两处都写着"基本"，意思是要的是原理和结构，不是手推长表。

二进制让"乘以一位"退化成"取或不取"

机器不会乘法，它只会加法和移位。之所以还能算乘法，靠的是二进制的一个特性：

🔴 二进制每一位只有 0 和 1，所以"乘以一位"退化成了"取或不取"——一个与门就够了，再配上移位与加法就凑成了乘法。十进制做不到这一点（乘以 7 不是取或不取的事）。

于是乘法变成一条递推式，共 $n$ 次"判断—加法—右移"：

$$P_{i+1}=2^{-1}(P_i+X\times Y_{n-i})$$

这条式子里藏着一个很省硬件的设计：

🔴 乘积有 $2n$ 位，加法器却只需要 $n$ 位。 因为部分积每步右移一位，已经移出去的低位不会再被修改——它们被逐位推进乘数寄存器，最后凑成乘积的低 $n$ 位；每一步真正参与相加的永远只有部分积的高 $n$ 位。若改成手算式的"被乘数左移"，加法器就必须做到 $2n$ 位。

除法是它的镜像，两者的移位方向正好相反：

🔴 乘法右移、除法左移。 乘法器（$P$、$Y$）右移，部分积不断被 $\times 2^{-1}$；除法器（$R$、$Q$）左移，中间余数不断被 $\times 2$ 去和不动的除数比较。记法：乘法往小里走、除法往大里走，移位方向跟着权重的变化走。

⚠️ 还有一条能省掉很多记忆的观察：乘数 / 商寄存器是"边腾边填"的——每移一位就用掉一位乘数（或被除数）、腾出一个空位，正好接住新产生的一位结果。所以它运算中途装的既不是操作数也不是结果，而是一半一半。记住这条，各寄存器的初值终值都不必背。

一、乘法：把"乘"拆成机器会做的事

$X\times Y$，$Y=0.Y_1{Y}_2\cdots Y_n$：

$$X\times Y=\sum _{i=1}^{n}X\times Y_i\times 2^{-i}$$

每一项只需要两种能力：$Y_i$ 只能取 0 或 1，所以 $X\times Y_i$ 要么是 0、要么就是 $X$ 本身（一个与门）；$\times 2^{-i}$ 就是移位。整个乘法只用到「判位」「移位」「加法」。

直接照搬手算式子做电路很浪费，教材给出三处改进：

改进	做法	省下什么
边算边累加	每求出一项就立刻累加成部分积 $P_i$，不是全算完再求和	省 $n-1$ 份中间项存储
部分积右移，而非被乘数左移	被乘数原地不动，每步把部分积右移一位	省一半加法器宽度（见速查）
$Y_i=0$ 时只移不加	对为 1 的位做"加法 + 右移"，为 0 的位只右移	省时间；也是 Booth"遇连续 0/1 跳过加法"的同源思路

把递推式一路展开就是 $2^{-1}(2^{-1}(\cdots 2^{-1}(0+X\cdot Y_n)+X\cdot Y_{n-1})\cdots )$，$n$ 个 $2^{-1}$ 嵌套，正好还原成上面那个求和式。

二、迭代式运算器的通用骨架

三条改进落到电路上，就是一套三寄存器 + 一个计数器 + 控制逻辑的骨架。乘法器、除法器都是这个骨架，只是控制逻辑不同。

图 6.9　补码比较法运算基本硬件配置
（唐朔飞《计算机组成原理》第 3 版，见文末教材出处）

以 32 位无符号乘法为例：

部件	初值	结束时
$X$　被乘数寄存器	被乘数	不变（全程只被读）
$P$　乘积寄存器（部分积）	0	64 位乘积的高 32 位
$Y$　乘数寄存器	乘数	64 位乘积的低 32 位
$C$　进位触发器	0	保存加法器的进位
计数器 $C_n$	32	每循环减 1，减到 0 结束
ALU	—	受控制逻辑指挥，对 $P$ 与 $X$ 做加法，结果在"写使能"下送回 $P$

每次循环各寄存器怎么移，以及图 6.9 上的 A/X/Q 与上表的 P/X/Y 怎么对（想确认移位到底谁进谁出、或对着教材图找不到进位触发器时展开）

每次循环，$C$、$P$、$Y$ 同步右移：$C$ 移入 $P$ 的最高位，$P$ 的最低位移出到 $Y$ 的最高位，$Y$ 的最低位移出，0 移入 $C$。而 $Y$ 的最低位被送到控制逻辑，用来决定这一步加不加。

图 6.9 画的是补码乘法器，寄存器记作 $A$、$X$、$Q$；上表按无符号乘法列，记作 $P$、$X$、$Y$。三者一一对应：

$$A(\text{部分积})\leftrightarrow P,X(\text{被乘数})\leftrightarrow X,Q(\text{乘数})\leftrightarrow Y$$

两处不同不影响骨架：

• 图中 $A$、$X$、$Q$ 均为 $n+2$ 位（$X$ 含两位符号位，$Q$ 含一位符号位与末尾的附加位）。这种双符号位写法里，多出的那位符号位本身就承接了部分积累加时越出的一位，所以图上没有单独的进位触发器 $C$；上表按单符号位列，就得补一个 $C$。
• 图右侧的「移位和加控制逻辑」就是骨架里的控制逻辑。它受 $Q$ 寄存器末两位控制——这正是 Booth 乘法「看相邻两位决定加减」在硬件上的落点。

换掉的只是寄存器的名字和符号位的位数，"三寄存器 + 计数器 + 控制逻辑"这个骨架没有变。

原码乘与补码乘的分界：上面这套流程为什么不能直接拿去算补码（想弄清 Booth 算法是从哪冒出来的时展开）

上面这套流程有一个隐含前提：参与相加的都是无符号数，只做加法。原码乘法正好满足——符号位单独异或，数值位当成两个无符号数相乘，最后拼上符号：

$$Z_0=X_0\oplus Y_0,Z_1\cdots Z_{2n}=(0.X_1\cdots X_n)\times (0.Y_1\cdots Y_n)$$

但机器里的带符号整数是补码，最高位带负权重 $-2^{n-1}$，把它当普通数值位送进上面的流程会算错。两条出路：

出路	做法	代价
转成原码	先取绝对值，算完再定符号	多两次求补，且符号要单独处理
让符号位直接参与运算	Booth 乘法	每步多一种选择：还要能做减法

补码乘法之所以要引入"减"，根子就在那个负权重上——这也是乘法器的 ALU 必须支持加和减两种运算的原因。

三、除法器的结构

图 3.15　32 位除法运算逻辑结构
（袁春风《计算机组成与系统结构》第 3 版，见文末教材出处）

除法的普遍形式是

$$\text{被除数 }2n\text{ 位}÷\text{除数 }n\text{ 位}=\text{商 }n\text{ 位}+\text{余数 }n\text{ 位}$$

$n$ 位数除以 $n$ 位数也归到这个形式里，办法是把被除数扩展成 $2n$ 位。扩展方式按数据类型分三种：

情形	扩展方式	$R$ 初值	$Q$ 初值	会不会溢出
两个 $n$ 位定点正整数相除（单精度除法）	被除数高位补 $n$ 个 0	全 0	被除数	不会（商必不超过 $n$ 位）
两个 $n$ 位定点正小数相除（浮点尾数）	被除数低位补 $n$ 个 0	被除数	全 0	见下
$2n$ 位 ÷ $n$ 位（双精度除法）	无须扩展	被除数高 $n$ 位	被除数低 $n$ 位	可能（商可能多于 $n$ 位）

🔴 扩展方式还要看符号性：带符号数扩展要符号扩展（复制符号位），无符号数扩展要高位补 0。同一张框图，题面把操作数说成"32 位无符号数"还是"32 位带符号数"，$R$ 的初值填法就不同。

以 64 位 ÷ 32 位为例，各部件的职责：

部件	初值	结束时
$Y$　除数寄存器	除数	不变
$R$　余数寄存器	被除数的高 32 位	余数
$Q$　余数/商寄存器	被除数的低 32 位	32 位商
计数器 $C_n$	32	每循环减 1，减到 0 时结束
ALU	—	受控制逻辑指挥，对 $R$ 与 $Y$ 做加/减两种运算，结果在"写使能"下送回 $R$

每次循环 R 与 Q 怎么动，以及开始迭代之前的那一轮取值判断（想确认 Q 里中途装的是什么，或除数为 0、商溢出在整数与浮点下各自怎么处理时展开）

每次循环 $R$ 与 $Q$ 同步左移：$Q$ 的最高位移入 $R$ 的最低位，$Q$ 空出的最低位用来上商。所以运算中途 $Q$ 里是"一部分被除数/中间余数、一部分商"，只有最后一步才全部变成商——$Q$ 叫"余数/商寄存器"不是随便起的名字。

除法是唯一会在运算部件内部触发异常的算术运算。在真正开始迭代之前，必须先做一轮判断：

情况	结果
被除数为 0、除数不为 0（或整数除法中 |被除数| < |除数|）	商为 0，余数为被除数，不再迭代
除数为 0	整数："除数为 0"异常；浮点：结果为无穷大
被除数与除数都为 0	整数：除法错异常；浮点：产生 NaN
商可能溢出	异常（见速查，$-2^{n-1}÷(-1)$）

第四类最容易被漏掉：两个完全合法的数相除，商却可能不合法。

CPU 检测到异常后的响应流程与其他异常一致：关中断 → 保护断点（PC）与程序状态（PSW）→ 切换到内核态 → 跳转到异常处理程序入口。

四、三种实现层次：时间与硬件的交换

同一个乘法可以用三种代价完全不同的方式做出来。速度差别的根源始终是"花几个时钟周期"与"用多少硬件"之间的交换。

层次	做法	耗时	硬件代价
软件循环	用加法和移位指令写循环	最慢，每位一轮循环、每轮若干条指令	无额外硬件
ALU + 移位器（多周期）	一套加法器反复用，每周期处理一位	$n$ 位乘法约 $n$ 个时钟周期	一个 ALU + 移位逻辑 + 计数器
阵列乘法器（单周期）	把全加器铺成阵列，一次并行算完	一个时钟周期（纯组合逻辑）	面积随位数平方增长

阵列乘法器内部长什么样，以及它凭什么一拍出结果（想弄清"移位"在阵列里去哪儿了时展开）

图 3.13　4×4 位基于 CRA 的阵列乘法器
（袁春风《计算机组成与系统结构》第 3 版，见文末教材出处）

每个"细胞模块"（图中的一个方框）只有两个元件：一个与门算 $X_i{Y}_j$ 这一位部分积，一个全加器把它与上方传下来的部分积和左侧传来的进位相加。手算式里"每行向左错一位"的移位，在阵列里由全加器的空间错位直接实现——不需要真的做移位操作。

它是纯组合逻辑电路：没有寄存器、没有时钟、没有循环。数据从输入端进去，穿过一层层全加器，从输出端出来就是结果。这也是它与前两种的本质区别：前两种是"同一套硬件用 $n$ 次"，它是"$n^2$ 套硬件用 1 次"。$32\times 32$ 位要上千个全加器，所以它在数字信号处理这类乘法密集的场合才划算。

阵列乘法器本身还能再快：把行波进位换成进位保留加法器（CSA），让本级进位与本级和一起输出到下一级、而不是在本级内横向传播；再往上还有树形结构，把加法级数从 $O(N)$ 压到 $O(\log N)$。这些属于了解层面。

乘除法器里的那个 ALU 就是补码加减运算部件（想确认一套加法器怎么同时承担加和减时展开）

图 3.9　补码加减运算部件
（袁春风《计算机组成与系统结构》第 3 版，见文末教材出处）

$Y$ 输入端串一排反相器接二选一多路器，控制信号 $Sub$ 同时接到最低位进位输入——$Sub=1$ 时电路算 $X+\bar{Y}+1=X-Y$。一套加法器同时承担加和减，这正是"除法器的 ALU 只需两种运算"却足以跑加减交替法的原因。完整推导见补码加减运算与溢出判别。

考点速记

1. 乘法能化成"移位 $+$ 加"，根子在二进制的每一位只有 0 和 1；硬件相对手算做了三处改进，其中"部分积右移而非被乘数左移"最关键——它让两个 $n$ 位数相乘只需 $n$ 位加法器。
2. 迭代式运算器的通用骨架是三寄存器 $+$ 计数器 $+$ 控制逻辑，计数器在控制逻辑模块内（既不是与 $R$/$Q$/$Y$ 并列的数据寄存器，也不在 ALU 里）；乘数 / 商寄存器"边腾边填"；乘法器右移、除法器左移。
3. 除法的普遍形式是 $2n$ 位 $÷$ $n$ 位；除法器的 ALU 只需加、减两种运算——除法的全部工作是"用中间余数减除数试商"，不够减时改成加除数，不需要 ALU 会乘除；两类异常是除数为 0 与商溢出（$-2^{n-1}÷(-1)=2^{n-1}$ 越界一格，是补码不对称的后果）。

这一节在真题里被考过的形式（multiplication-division 这个 topic 至今只有 3 道题，其中选择题只有 1 道）：

• 挑关于整数乘法运算的错误叙述：四个选项通常踩"阵列乘法器可在一个时钟周期完成"（对）、"用 ALU 加移位器实现的乘法无法在一个周期内完成"（对，它要迭代 $n$ 次）、"变量与常数的乘法可编译优化成若干移位与加减"（对）、"两个变量的乘法无法编译为移位加法的循环实现"（错——可以，那正是本篇讲的迭代算法）。
• 大题里出现的乘除：一般不单独考算法本身，而是作为数据通路 / 指令执行题的一环出现（如问乘法指令的执行阶段要几个时钟周期）。

⚠️ 下方「真题练习」挂的 multiplication-division 只有 3 道题，却由本篇与 Booth 乘法、恢复余数除法、加减交替法 四篇共用——所以后三篇的真题练习看起来会是同一批题，这不是重复挂载，是这个考点本身出题就少。

易错：把计数器画进 ALU 或当成第四个数据寄存器。它在控制逻辑里。

易错：认为除法器的 ALU 需要会乘除。它只需要加和减。

易错：以为两个变量相乘编译不成移位与加法。迭代实现就是。

教材出处

• 手算乘法的三个特点、硬件的三处改进（累加部分积、部分积右移、为 0 只移不加）、"只需用 $n$ 位加法器就可实现两个 $n$ 位数相乘"、递推公式 $P_{i+1}=2^{-1}(P_i+X\times Y_{n-i})$：袁春风《计算机组成与系统结构》第 3 版 §3.3.3 原码乘法运算，印刷页 p62–p63
• 32 位无符号乘法逻辑结构（图 3.10）各寄存器职责与同步右移规则：同书印刷页 p63–p64
• 阵列乘法器的细胞模块构成、"移位由全加器的空间错位实现"、CSA 与树形结构：同书 §3.3.5 快速乘法器，印刷页 p67–p69
• 除法前的取值判断（除数为 0、商为 0、商溢出如"补码中最大负数除以 $-1$"）：同书 §3.3.6 原码除法运算，印刷页 p69
• 32 位除法逻辑结构（图 3.15）中 $Y$/$R$/$Q$/计数器/ALU 的职责、$R$ 与 $Q$ 同步左移上商规则：同书印刷页 p70
• "$n$ 位定点数的除法实际上是用一个 $2n$ 位的数去除以一个 $n$ 位的数"、被除数扩展的三种情况与单/双精度除法的溢出差别：同书印刷页 p71
• 补码加减运算部件（图 3.9）：同书 §3.3.1 补码加减运算，印刷页 p60
• 补码比较法（Booth 算法）运算基本硬件配置（图 6.9）、A/X/Q 三个寄存器的位宽与职责：唐朔飞《计算机组成原理》第 3 版 §6.2 定点运算，印刷页 p255

相关知识

Booth 乘法｜恢复余数除法｜不恢复余数（加减交替）除法｜补码加减运算与溢出判别｜算术逻辑单元（ALU）

真题练习

相关真题（3题）

2025Q449分2024Q152分2020Q4313分

上一篇补码加减运算与溢出判别下一篇Booth 乘法（补码一位乘）

相关文章

• 进位计数制与转换
• 真值与机器数：四种编码
• 定点数编码的转换与书写
• 算术逻辑单元（ALU）
• 补码加减运算与溢出判别
• Booth 乘法（补码一位乘）
• 恢复余数除法
• 不恢复余数除法（加减交替法）
• 定点数的移位运算
• C 语言中的数据类型与转换
• 浮点数表示（IEEE 754）
• 浮点数的加减运算
• 数据对齐与大小端（属指令系统章）
• 校验码与码距（纲外）
• 海明码详解（纲外）