恢复余数除法

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

硬件没有"看一眼就知道够不够减"的能力

机器除法与手算是同源的：都用中间余数减除数得到每一位商——够减上商 1、不够减上商 0。差别只在两处工程改造。

第一处：谁在动。 手算是除数逐位右移；硬件里除数放在寄存器中不动更省事，于是把相对运动倒过来。

🔴 "余数左移"只是换了参照系：除数右移一位 $⟺$ 中间余数左移一位。 不是新原理。

第二处：怎么判"够不够减"。 人眼可以比大小，硬件不能，所以只能先减再看符号：

🔴 做 $R + [- Y]_{补}$ 之后看结果的符号位——0（非负）够减、上商 1；1（负）不够减、上商 0。整个除法的控制信息量，就只有这一位符号位。

不够减那一步减出来的负数不是这一步应有的中间余数（应有的是没减之前的 $R$ ），所以必须 $R \leftarrow (R - Y) + Y$ 加回去，这就是"恢复余数"。

⚠️ 恢复这一步不产生任何新信息，纯粹是一次撤销——这正是它显得浪费、并催生出加减交替法的地方。

交互可视化

加载可视化中...

一、两处工程改造

手算 $10011101 \div 1011$ 的做法是：拿被除数的高几位与除数相减，够减上商 1、不够减上商 0；得到的差是中间余数，把除数向右挪一位再比较；重复直到商的位数够为止。计算机做的事一模一样，只在两处做了改造。

改造一：除数不动，改成余数左移。 手算写在纸上时除数右移方便；硬件里除数寄存器 $Y$ 不动更省电路，于是把相对运动倒过来，两者的相对位置变化完全相同。（乘法器里"被乘数不动、部分积右移"是同一个思路的镜像，见总述篇。）

改造二：够不够减，靠"减了再看符号"。

R - Y ⟺ R + [- Y]_{补}

结果符号位为 0 就上商 1、这个差就是新的中间余数；为 1 就上商 0，但这个差是个错误的中间余数——于是就有了"恢复"这一步的必要性。

二、算法与首次试减的口径

原码除法中符号与数值分开处理（见速查），下面只讨论数值部分。

输入：被除数 |X|、除数 |Y|
初始：R = |X| 的高位部分，Q = |X| 的低位部分

R = R - |Y|                  // 首次试减：溢出判据
if R >= 0: 上商 1 -> 溢出，停止
else:      上商 0，R = R + |Y|   // 恢复，该商位不计入结果

for i = 1 to n:
    (R, Q) 同步左移一位       // Q 的最高位移入 R 的最低位，Q 空出末位
    R = R - |Y|              // 试减
    if R >= 0:
        Q 的末位上商 1        // 够减，保留 R
    else:
        Q 的末位上商 0        // 不够减
        R = R + |Y|          // 恢复余数

逐步走一遍一个 4 位定点小数除法：每一步试减、上商、恢复、左移的完整过程（想确认恢复到底发生在哪一步、代价有多大时展开）

计算 $0.1001 \div 0.1101$ ，4 位数值位。中间余数用一位符号位表示，"减除数"由"加除数的补"实现：

| X | = 0.1001, | Y | = 0.1101, [- | Y |]_{补} = 1.0011

步骤	操作	余数 $R$	商位
初始		`0.1001`
首次试减	$0.1001 + 1.0011 = 1.1100$	`1.1100`（负）	$Q_{n} = 0$ → 不溢出，不计入商
恢复	$1.1100 + 0.1101 = 0.1001$	`0.1001`
左移		`1.0010`
第 1 步	$1.0010 + 1.0011 = 0.0101$	`0.0101`（正）	$q_{1} = 1$ ，保留
左移		`0.1010`
第 2 步	$0.1010 + 1.0011 = 1.1101$	`1.1101`（负）	$q_{2} = 0$
恢复	$1.1101 + 0.1101 = 0.1010$	`0.1010`
左移		`1.0100`
第 3 步	$1.0100 + 1.0011 = 0.0111$	`0.0111`（正）	$q_{3} = 1$ ，保留
左移		`0.1110`
第 4 步	$0.1110 + 1.0011 = 0.0001$	`0.0001`（正）	$q_{4} = 1$ ，保留

商 $= 0.1011$ ，余数 $= 0.0001 \times 2^{- 4}$

核对： $\frac{11}{16} \times \frac{13}{16} + \frac{1}{256} = \frac{143}{256} + \frac{1}{256} = \frac{144}{256} = \frac{9}{16} = {0.1001}_{2}$ ✓

从这张表能直接读出恢复余数法的代价：4 个商位里有 1 个是 0，就多做了 1 次加法；加上首次试减后的那次恢复，本例一共做了 7 次加减才得到 4 位商。而每一位商本来只需要 1 次减法，多出来的 3 次全部是"撤销"，不产生任何新的商位。

定点小数除法里首次试减商位的一个例外（做浮点尾数除法、发现"溢出"却仍能继续算时展开）

对定点小数除法（浮点尾数），首次试减产生的 $Q_{n} = 1$ 意味着商的数值溢出到了整数部分。按定点小数的规矩这是溢出；但作为浮点尾数时可以靠右规救回来，所以有的实现会保留 $Q_{n}$ 继续算下去。

考点速记

机器除法与手算同源——用中间余数减除数得到每一位商；两处改造是"除数不动改成余数左移"（换参照系）与"减了再看符号位"（硬件不会比大小），后者使整个除法的控制信息量只有一位符号位。
不够减必须恢复余数，因为负的中间余数不能作为下一步的起点；这是纯撤销、不产生新信息，也正是它的短板所在（教材原话："在计算机中很少采用恢复余数除法，而普遍采用不恢复余数除法"）。
首次试减产生的商位是溢出判据（ $Q_{n} = 1$ 即商超出 $n$ 位），不计入商——把它当第一位商，整条商会错位一位（恰好小一半）；只有 $R$ 初值全 0 时可省（两个 $n$ 位正整数相除、被除数高位补 $n$ 个 0 的单精度除法），被除数本来就是 $2 n$ 位时绝不能省。 $R$ 与 $Q$ 同步左移（ $Q$ 最高位移入 $R$ 最低位， $Q$ 空出的最低位接商），定点小数的最终余数需乘 $2^{- n}$ 还原（定点整数不需要）。

这一节在真题里的位置：

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

复习优先级：这一篇的价值主要在于它是加减交替法的来路——理解"恢复那一步在做什么"，才能理解为什么它可以被省掉。会手推一遍、说得清首次试减那位商的含义即可，不必反复练表格。

易错：把首次试减那位当成第一位商。它是溢出判据，整条商会错位。

易错：定点小数除法的最终余数不乘 $2^{- n}$ 。 $R$ 被左移了 $n$ 次，值放大了 $2^{n}$ 倍。

易错：以为"整数除法就能省掉首次试减"。判据是 $R$ 初值是否全 0，不是数据类型。

教材出处

手算除法的三个要点、"计算机内部的除法运算与手算算法一样，通过被除数（中间余数）减除数来得到每一位商"：袁春风《计算机组成与系统结构》第 3 版 §3.3.6 原码除法运算，印刷页 p70
无符号数除法四条算法要点（操作数预置、做减法试商、上商为 0 时恢复余数、中间余数左移）与"除数在除数寄存器中不动，因此需要将中间余数左移"：同书印刷页 p71
恢复余数除法的分步算法、 $Q_{n} = 1$ 即溢出的判据、定点小数除法中 $Q_{n}$ 可保留继续执行的例外：同书印刷页 p72
"在计算机中很少采用恢复余数除法，而普遍采用不恢复余数除法"：同书印刷页 p73
商的符号由两数符号异或得到、数值为两数绝对值之商：同书印刷页 p70

真题练习

2025Q449分 2024Q152分 2020Q4313分

恢复余数除法

硬件没有"看一眼就知道够不够减"的能力

交互可视化

一、两处工程改造

二、算法与首次试减的口径

考点速记

相关知识

真题练习

相关真题（3题）

相关文章

恢复余数除法 ​

硬件没有"看一眼就知道够不够减"的能力 ​

交互可视化 ​

一、两处工程改造 ​

二、算法与首次试减的口径 ​

考点速记 ​

相关知识 ​

真题练习 ​

相关真题（3题）

相关文章

恢复余数除法

硬件没有"看一眼就知道够不够减"的能力

交互可视化

一、两处工程改造

二、算法与首次试减的口径

考点速记

相关知识

真题练习