恢复余数除法

考情分析

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

原码除法的前提

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

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

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

恢复余数法的基本思想

模拟手工除法的"试减"过程：

试减：用当前余数减去除数
判断余数符号：
- 余数 $\geq 0$ （够减）：该位商 1，保留新余数
- 余数 $< 0$ （不够减）：该位商 0，加回除数恢复余数
余数左移 1 位（等效于引入下一位被除数）
重复 $n$ 次（ $n$ = 数值位位数）

算法伪代码

输入：被除数 |X|，除数 |Y|
初始：余数 R = |X|

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

商 = Q[1]Q[2]...Q[n]
最终余数 = R >> n         // 右移 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`
第 1 步	$R - Y = 0.1011 + 1.0011 = 1.1110$	`1.1110`（负）	商 0
恢复	$R + Y = 1.1110 + 0.1101 = 0.1011$	`0.1011`
左移		`1.0110`
第 2 步	$R - Y = 1.0110 + 1.0011 = 0.1001$	`0.1001`（正）	商 1
左移		`1.0010`
第 3 步	$R - Y = 1.0010 + 1.0011 = 0.0101$	`0.0101`（正）	商 1
左移		`0.1010`
第 4 步	$R - Y = 0.1010 + 1.0011 = 1.1101$	`1.1101`（负）	商 0
恢复	$R + Y = 1.1101 + 0.1101 = 0.1010$	`0.1010`

商 $Q = 0.0110$ ，余数 $= 0.1010 \times 2^{- 4}$

验证： ${0.0110}_{2} \times {0.1101}_{2} + {0.00001010}_{2} = {0.01001110}_{2} + {0.00001010}_{2} = {0.01011000}_{2} \approx {0.1011}_{2} \times 2^{- 1}$

精度受限于 4 位商，结果正确。

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

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

被除数用双倍长寄存器存放：高位 $0000$ ，低位 $0111$

步骤	操作	余数（高位部分）	商位
初始		`0000.0111`
第 1 步	$R - Y$ ： $0000 - 0011 = 1101$ （负）	恢复 → `0000`	商 0
左移		`0000.111_`
第 2 步	$R - Y$ ： $0001 - 0011 = 1110$ （负）	恢复 → `0001`	商 0
左移		`0011.1___`
第 3 步	$R - Y$ ： $0011 - 0011 = 0000$ （正）	`0000`	商 1
左移		`0001.____`
第 4 步	$R - Y$ ： $0001 - 0011 = 1110$ （负）	恢复 → `0001`	商 0

商 = 0010 = 2，余数 = 0001 = 1

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

恢复余数法的缺点

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

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

考点清单

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

恢复余数除法 ​

考情分析 ​

原码除法的前提 ​

恢复余数法的基本思想 ​

算法伪代码 ​

硬件实现要点 ​

算法流程图 ​

交互可视化 ​

例题 ​

恢复余数法的缺点 ​

考点清单 ​

相关文章