Booth 乘法（补码一位乘）

2026 大纲 二（二）3　乘/除运算（乘/除法运算的基本原理）。大纲没有点名 Booth 算法，本篇是支撑这一条目的具体算法之一，要求到基本原理层次。

补码最高位带负权重，照搬原码乘法就把符号算反了

原码乘法很朴素：符号位单独异或，数值位当成两个无符号数，每一步只有"加或不加"。补码不能照搬，根子在一处：

🔴 补码的最高位带的是负权重 $-2^{n-1}$。 把 $Y_{n-1}$ 当成普通位、遇 1 就加一次 $X$，等于把 $-2^{n-1}X$ 算成了 $+2^{n-1}X$——符号位的贡献被算反了。

Booth 算法的解法不是打补丁，而是把补码的真值式做一次代数变形（错位相减）：

$$y=\sum _{i=0}^{n-1}(Y_{i-1}-Y_i)2^i,\text{约定 }{Y}_{-1}=0$$

🔴 变形之后每一项的形式完全一致，"哪一位是符号位"的区别就消失了——这正是 Booth 全程没有异或、也不用取绝对值的原因。它不是一套凑出来的规则。

由差值 $Y_{i-1}-Y_i$ 直接读出位对规则：01 加 $[x{]}_{\mathrm{补}}$、10 加 $[-x{]}_{\mathrm{补}}$、00 与 11 不动。直觉上，一段连续的 1 等于"段末位的下一位权重减去段首位权重"，所以 01 是一段 1 的开始、10 是一段 1 的结束。

🔴 $Q_0$ 是当前位，$Q_{-1}$ 是更低的那一位，顺序记反加减就全做反。自查口诀：$Q_0$ 是刚要被用掉的那位，$Q_{-1}$ 是上一轮刚用完的那位。

⚠️ $Q_{-1}$ 是补位不是"多存一位数"：递推式在 $i=0$ 时要用到 $Y_{-1}$，而乘数最低位下面本来没有位，所以硬件在乘数寄存器最低位之外再挂一个一位触发器、初值置 0，每次右移接住 $Q$ 移出的最低位，结束时无意义、丢弃。

交互可视化

加载可视化中...

一、补码坏在最高位

原码一位乘把符号位摘出去单独异或，数值位当成两个无符号数处理，所以每步只需"加或不加"。补码不能这么用，问题出在最高位的权重。$n$ 位补码的真值是

$$y=-Y_{n-1}{2}^{n-1}+\sum _{i=0}^{n-2}{Y}_i{2}^i$$

最高位带的是负权重，其余位是正权重。出路有两条：要么先取绝对值转成原码（多两次求补、符号还要单独处理），要么想办法让这个负权重自己在运算中体现出来。Booth 走的是第二条路。

二、Booth 递推：从补码定义直接推出来

关键一步是错位相减：把每一项 $Y_i{2}^i$ 写成 $Y_i{2}^{i+1}-Y_i{2}^i$，然后重新配对。

$$\begin{array}{rl}y& =-Y_{n-1}{2}^{n-1}+Y_{n-2}{2}^{n-2}+\cdots +Y_1{2}^1+Y_0{2}^0\\ & =-Y_{n-1}{2}^{n-1}+(Y_{n-2}{2}^{n-1}-Y_{n-2}{2}^{n-2})+\cdots +(Y_0{2}^1-Y_0{2}^0)\\ & =(Y_{n-2}-Y_{n-1})2^{n-1}+(Y_{n-3}-Y_{n-2})2^{n-2}+\cdots +(0-Y_0)2^0\end{array}$$

写成通式（约定 $Y_{-1}=0$，它正来自最后一项 $(0-Y_0)2^0$）：

$$\boxed{{\displaystyle y=\sum _{i=0}^{n-1}(Y_{i-1}-Y_i)2^i}}⟹x\times y=\sum _{i=0}^{n-1}x(Y_{i-1}-Y_i)2^i$$

按乘法器"部分积右移"的老办法整理成递推式：

$${\left[P_{i+1}\right]}_{\mathrm{补}}={\left[2^{-1}(P_i+(Y_{i-1}-Y_i)x)\right]}_{\mathrm{补}},i=0,1,\dots ,n-1$$

$(Y_{i-1}-Y_i)$ 只能取 $-1$、$0$、$+1$ 三个值，对应的操作正好是减 $x$、不动、加 $x$。

三、规则表与算法步骤

$$Y_i\text{（当前位）},Y_{i-1}\text{（前一位，即更低的那一位）}$$

$Y_i$	$Y_{i-1}$	$Y_{i-1}-Y_i$	操作
0	0	$0$	部分积不变
0	1	$+1$	部分积 $+[x{]}_{\mathrm{补}}$
1	0	$-1$	部分积 $+[-x{]}_{\mathrm{补}}$
1	1	$0$	部分积不变

$$[A\mid Q\mid Q_{-1}]$$

寄存器	初值	结束时
$A$（部分积）	0	乘积的高 $n$ 位
$Q$（乘数寄存器）	$[y{]}_{\mathrm{补}}$	乘积的低 $n$ 位
$Q_{-1}$（附加位）	0	无意义，丢弃
$X$（被乘数寄存器）	$[x{]}_{\mathrm{补}}$	不变

算法（$n$ 位补码整数，共 $n$ 轮）：

1. 置 $A=0$，$Q=[y{]}_{\mathrm{补}}$，$Q_{-1}=0$
2. 看 $(Q_0,Q_{-1})$：01 则 $A+=[x{]}_{\mathrm{补}}$；10 则 $A+=[-x{]}_{\mathrm{补}}$；00/11 不动
3. 对 $[A\mid Q\mid Q_{-1}]$ 整体算术右移一位
4. 重复 2–3 共 $n$ 次，乘积就是 $[A\mid Q]$ 这 $2n$ 位

四、为什么必须是算术右移

原码乘法的部分积永远非负，右移补 0 就行。Booth 引入了减法，部分积可以是负数——这时右移补 0 会把一个负数变成正数。所以 $[A\mid Q\mid Q_{-1}]$ 的右移必须是算术右移：最高位（符号位）保持不变，用它自己的值填补空出的高位。这与定点数的移位运算里"补码右移补符号位"是同一条规则。

五、与原码一位乘的分界

	原码一位乘	Booth 乘法
处理对象	原码（需先取绝对值）	补码（直接算）
符号	单独异或	自动包含在运算中
每步可能的操作	加 / 不加	加 / 减 / 不加
对 ALU 的要求	只需加法	必须能加也能减
右移方式	逻辑右移即可	必须算术右移
主要用途	浮点尾数（原码小数）运算	带符号整数运算

后三行是连锁的：引入减法 ⇒ 部分积可能为负 ⇒ 右移要补符号位 ⇒ ALU 要支持减法。

逐位走一遍：被乘数 +7 乘以 -6 的四轮推演（想确认每一轮该加该减、右移怎么补位时展开）

$x=+7$、$y=-6$，机器字长 4 位（含符号位）：

$$[x{]}_{\mathrm{补}}=0111,[-x{]}_{\mathrm{补}}=1001,[y{]}_{\mathrm{补}}=1010$$

初始：$A=0000$，$Q=1010$，$Q_{-1}=0$。

轮次	$(Q_0,Q_{-1})$	操作	$A$	$Q$	$Q_{-1}$
初始	—	—	0000	1010	0
1　加减	0,0	不动	0000	1010	0
1　右移	—	算术右移	0000	0101	0
2　加减	1,0	$A+[-x{]}_{\mathrm{补}}$	1001	0101	0
2　右移	—	算术右移	1100	1010	1
3　加减	0,1	$A+[x{]}_{\mathrm{补}}$	0011	1010	1
3　右移	—	算术右移	0001	1101	0
4　加减	1,0	$A+[-x{]}_{\mathrm{补}}$	1010	1101	0
4　右移	—	算术右移	1101	0110	1

乘积 $=[A\mid Q]=$ 1101 0110。核对：$-42$ 的 8 位补码是 11010110 ✓，而 $7\times (-6)=-42$ ✓

看两处细节：

• 第 3 轮 0011 是 $1100+0111$ 丢掉最高进位的结果——这正是补码加法模 $2^n$ 的正常行为。
• 第 2 轮右移时 $A$ 从 1001 变成 1100：最高位的 1 被复制了一份填进来。若这里补 0 得到 0100，后面全盘皆错。

双符号位那套写法在做什么（对着别的书、发现表格长度对不上时展开）

另一种常见写法针对定点小数：部分积和被乘数取双符号位，乘数多取一位附加位，共 $n+1$ 步而最后一步只加不移。

多出来的那位符号位是为了容纳中间状态：部分积累加过程中可能暂时出现 01.xxxx（绝对值超过 1）——这不是错误，右移一位就回到正常范围。这与溢出判别里的变形补码是同一套机制。

本篇用单符号位整数写法时不会遇到这个现象，因为整数没有"绝对值超过 1"这回事。两种写法认准一种写到底。

考点速记

1. Booth 的合法性来自补码真值式的错位相减变形 $y=\sum _{i=0}^{n-1}(Y_{i-1}-Y_i)2^i$（约定 $Y_{-1}=0$）：变形后每一位形式一致，符号问题在数学上就消失了，所以流程里没有任何"处理符号"的步骤。
2. 位对规则 01 加、10 减、00/11 不动；$Q_0$ 是当前位、$Q_{-1}$ 是更低那位，顺序记反加减全做反；$Q_{-1}$ 是补位、初值 0。遇连续的 1 或 0 可跳过加法直接右移是它相对原码一位乘的额外收益。
3. 引入减法 $\Rightarrow$ 部分积可能为负 $\Rightarrow$ 右移必须是算术右移（补符号位）$\Rightarrow$ ALU 必须能减，这是一条因果链；结束时 $A$ 存乘积高 $n$ 位、$Q$ 存低 $n$ 位。两套书写约定不可混用：定点整数、单符号位是 $n$ 轮、每轮都移位（本篇）；定点小数、双符号位是 $n+1$ 步、最后一步只加减不移位——结果相同、中间表格长度不同，混着抄会多移或少移一位。

这一节在真题里的位置：

Booth 算法在 408 真题里至今不单独成题。下方「真题练习」挂的 multiplication-division 只有 3 道题，且由乘除四篇共用——看到与本篇内容对不上是正常的，不是漏挂标签。

它出现的方式是作为知识背景：判断题里的"两个变量的乘法能否编译成移位与加法的循环"、以及大题里问乘法指令要几个时钟周期时，用到的都是它的迭代次数。复习优先级：会手推一遍位对规则与算术右移即可，不必反复练表格。

易错：把 $Q_0$ 与 $Q_{-1}$ 的顺序记反，加减全做反。

易错：右移用逻辑右移。部分积可能为负，必须补符号位。

易错：把整数写法与小数写法混着抄，多移或少移一位。

教材出处

• 补码真值式的错位相减变形、$y=\sum (Y_{i-1}-Y_i)2^i$、递推公式（3-8）与布斯乘法的提出：袁春风《计算机组成与系统结构》第 3 版 §3.3.4 补码乘法运算，印刷页 p65
• 补码乘法运算四条规则（附加位 $Y_{-1}=0$、按 $Y_i{Y}_{i-1}$ 决定加减、每次加减后算术右移、重复 $n$ 次）：同书印刷页 p66
• "布斯乘法中遇到连续的 1 或连续的 0 时可跳过加法运算直接右移，运算效率较高"：同书印刷页 p67
• 位对状态表（$Y_i{Y}_{i+1}$ 与操作的对应）、"按比较法进行补码乘法时符号位也一起参加运算"：唐朔飞《计算机组成原理》第 3 版 §6.2 定点运算，印刷页 p254
• "比较法的补码乘法运算规则不受乘数符号的约束，控制线路比较简明，在计算机中普遍采用"、A/X/Q 均为 $n+2$ 位寄存器的双符号位写法：同书印刷页 p255

相关知识

乘除运算的基本原理与实现结构｜补码加减运算与溢出判别｜定点数的移位运算｜恢复余数除法

真题练习

相关真题（3题）

2025Q449分2024Q152分2020Q4313分

上一篇乘除运算的基本原理与实现结构下一篇恢复余数除法

相关文章

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