恢复余数除法

考情分析

定点除法在 408 中考频低于乘法，但仍有出过大题。恢复余数法逻辑直观，是理解加减交替法的基础。考题一般给出被除数和除数，要求手工模拟 3-4 步算法过程并写出商和余数。

原码除法的前提

原码除法中，符号和数值分开处理：

商的符号 = 被除数符号 $\oplus$ 除数符号
数值部分取绝对值，单独做无符号除法
余数的符号与被除数相同

下面讨论的除法过程均针对数值部分（绝对值）。

恢复余数法的基本思想

模拟手工除法的"试减"过程。以定点小数除法为例（ $n$ = 数值位位数）：

首次试减（溢出判断）： $R - Y$ ，所得符号给出商的整数位 $q_{0}$ 。定点小数除法要求 $| X | < | Y |$ ，所以 $q_{0}$ 必须为 0（若为 1 说明商 $\geq 1$ ，溢出）。 $q_{0}$ 不计入小数商位，试减后把余数恢复
重复 $n$ 次，每次得到一个小数商位 $q_{i}$ ：
- 余数左移 1 位（等效于引入下一位被除数）
- 试减：用左移后的余数减去除数
- 余数 $\geq 0$ （够减）：该位商 1，保留新余数
- 余数 $< 0$ （不够减）：该位商 0，加回除数恢复余数
商 $= 0. q_{1} q_{2} \dots q_{n}$

最容易错的一步

首次试减只是溢出判断，它产生的是商的整数位 $q_{0}$ ，不是第一个小数商位。真正的小数商位都从"左移之后"的试减开始。把 $q_{0}$ 当成 $q_{1}$ ，整条商会错位一位（恰好小一倍）。

算法伪代码

输入：被除数 |X|，除数 |Y|（定点小数，要求 |X| < |Y|）
初始：余数 R = |X|

R = R - |Y|              // 首次试减：溢出判断
if R >= 0: 溢出，停止     // q0 = 1，商 ≥ 1
else: R = R + |Y|        // q0 = 0，恢复余数，q0 不计入商

for i = 1 to n:
    R = R << 1           // 先左移
    R = R - |Y|          // 再试减
    if R >= 0:
        Q[i] = 1         // 够减，商1
    else:
        Q[i] = 0         // 不够减，商0
        R = R + |Y|      // 恢复余数

商 = 0.Q[1]Q[2]...Q[n]
最终余数 = R × 2^(-n)     // 余数带 2^(-n) 权

硬件实现要点

在补码运算器中，"减除数"通过"加除数的补"实现：

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

判断余数正负只看最高位（符号位）：0 为正，1 为负。

算法流程图

交互可视化

加载可视化中...

例题

例 1：用恢复余数法计算 $0.1011 \div 0.1101$ （正数，4 位数值位）

$| X | = 0.1011$ ， $| Y | = 0.1101$ ， $[- | Y |]_{补} = 1.0011$

步骤	操作	余数 $R$	商位
初始		`0.1011`
首次试减	$R - Y = 0.1011 + 1.0011 = 1.1110$	`1.1110`（负）	$q_{0} = 0$ （不溢出，不计入商）
恢复	$R + Y = 1.1110 + 0.1101 = 0.1011$	`0.1011`
左移		`1.0110`
第 1 步	$R - Y = 1.0110 + 1.0011 = 0.1001$	`0.1001`（正）	$q_{1} = 1$
左移		`1.0010`
第 2 步	$R - Y = 1.0010 + 1.0011 = 0.0101$	`0.0101`（正）	$q_{2} = 1$
左移		`0.1010`
第 3 步	$R - Y = 0.1010 + 1.0011 = 1.1101$	`1.1101`（负）	$q_{3} = 0$
恢复	$R + Y = 1.1101 + 0.1101 = 0.1010$	`0.1010`
左移		`1.0100`
第 4 步	$R - Y = 1.0100 + 1.0011 = 0.0111$	`0.0111`（正）	$q_{4} = 1$

商 $Q = 0.1101$ ，余数 $= 0.0111 \times 2^{- 4}$

验证： ${0.1101}_{2} \times {0.1101}_{2} + {0.0111}_{2} \times 2^{- 4} = {0.10101001}_{2} + {0.00000111}_{2} = {0.10110000}_{2} = {0.1011}_{2}$ ，与被除数完全相等，结果正确。

（真值核对： $0.6875 \div 0.8125 \approx 0.846$ ，商 ${0.1101}_{2} = 0.8125$ 为其 4 位截断 ✓）

例 2：用恢复余数法计算 $X = + 7$ ， $Y = + 3$ ，机器字长 5 位（含符号位）

取绝对值： $| X | = 0111$ ， $| Y | = 0011$

被除数用双倍长寄存器对 $(R, Q)$ 存放：余数寄存器 $R = 0000$ ，低位 $Q = 0111$ 。每步先把 $(R, Q)$ 整体左移 1 位（被除数最高位移入 $R$ ， $Q$ 末位空出），再对 $R$ 试减，商位填入 $Q$ 空出的末位。整数除法共 $n$ 步，无需小数除法的首次溢出试减。

步骤	左移后 $(R, Q)$	试减 $R - Y$	商位（填入 $Q$ 末位）	本步结果 $(R, Q)$
第 1 步	`0000, 111_`	$0000 - 0011$ （负）	0（恢复 $R$ ）	`0000, 1110`
第 2 步	`0001, 110_`	$0001 - 0011$ （负）	0（恢复 $R$ ）	`0001, 1100`
第 3 步	`0011, 100_`	$0011 - 0011 = 0000$ （正）	1（保留）	`0000, 1001`
第 4 步	`0001, 001_`	$0001 - 0011$ （负）	0（恢复 $R$ ）	`0001, 0010`

商 = $Q$ = 0010 = 2，余数 = $R$ = 0001 = 1

验证： $7 \div 3 = 2 \dots \dots 1$ ，正确。

恢复余数法的缺点

问题	说明
步骤数不固定	每次不够减多做一次加法，最坏情况每步 2 次加法
控制逻辑复杂	需要根据余数符号决定是否恢复
平均效率低	统计上约一半步骤需要恢复

这些缺点推动了加减交替法（不恢复余数法）的出现——通过数学推导将恢复操作与下一步的试减合并。

考点清单

[ ] 恢复余数法三步骤：试减 → 判断符号 → 恢复（若需）→ 左移
[ ] 原码除法符号位单独处理（异或）
[ ] 共执行 $n$ 步， $n$ 为数值位位数
[ ] "减除数"通过"加除数的补"实现
[ ] 最终余数需右移 $n$ 位还原真实值
[ ] 恢复余数法缺点：步数不固定、效率低，引出加减交替法

恢复余数除法 ​

考情分析 ​

原码除法的前提 ​

恢复余数法的基本思想 ​

算法伪代码 ​

硬件实现要点 ​

算法流程图 ​

交互可视化 ​

例题 ​

恢复余数法的缺点 ​

考点清单 ​

相关文章