不恢复余数除法（加减交替法）

2026 大纲 二（二）3　乘/除运算（乘/除法运算的基本原理）。大纲没有点名加减交替法，但实际计算机普遍采用这一算法，除法器的结构基本都以它为背景。

恢复那一步能省掉，靠的是一个恒等式

恢复余数法里，不够减时要把减掉的除数加回去，然后左移、再减。把这三步连起来写：

R_{i + 1} = 2 (R_{i} + Y) - Y = 2 R_{i} + Y

🔴 "恢复 $+$ 左移 $+$ 减"与"左移 $+$ 加"恒等——不是近似也不是简化。两种算法每一步的中间余数、每一位商、最终余数完全相同。

于是规则压成六个字：正、1、减，负、0、加——中间余数为正就上商 1、下一步做减法；为负就上商 0、下一步做加法。每步固定一次加或一次减，加减交替出现。

用这条规则时有两处最容易翻车：

🔴 判加减看的是上一步（左移之前）的余数符号。 单符号位表示下，左移会把符号位被第一个数值位顶掉——0.1011 左移得 1.0110，看着像负数，其实只是原来那个正余数的两倍。读左移之后的最高位必错。（若改用双符号位、左移按算术左移处理，高位那个符号位才是真符号，这时读左移后的符号位也对。两种写法别混。）

🔴 末位余数为负仍要修正一次。 "不恢复"依赖的是下一步的左移把这笔账带过去（恒等式左边的因子 2 正来自左移）；最后一步之后没有左移了，这个负余数就是最终输出，而原码除法中余数应与被除数同号，所以必须当场做 $R + Y$ 。

交互可视化

加载可视化中...

一、恢复那一步能省掉，是一次代数化简

恢复余数法里，第 $i$ 步的中间余数是 $R_{i} = 2 R_{i - 1} - Y$ 。走到下一步时分两种情况。

情况一： $R_{i} ⩾ 0$ （够减，上商 1），不需要恢复，直接左移再试减： $R_{i + 1} = 2 R_{i} - Y$ 。

情况二： $R_{i} < 0$ （不够减，上商 0），按恢复余数法要走三步——恢复、左移、试减：

R_{i + 1} = 2 \underset{恢复}{\underset{⏟}{(R_{i} + Y)}} - Y = 2 R_{i} + 2 Y - Y = 2 R_{i} + Y

化简结果里没有"恢复"这一步了。 与其"加回 $Y$ 、左移、再减 $Y$ "，不如直接"左移、加 $Y$ "——两者恒等。把两种情况合起来：

R_{i} ⩾ 0 ⟹ 上商 1, R_{i + 1} = 2 R_{i} - Y R_{i} < 0 ⟹ 上商 0, R_{i + 1} = 2 R_{i} + Y

教材把它概括成六个字："正、1、减，负、0、加"。

二、算法流程

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

R = R - |Y|              // 首次试减：溢出判据，产生 Q_n
if R >= 0: 上商 1 -> 商溢出，停止
else:      上商 0（不计入商），不恢复，继续

for i = 1 to n:
    s = sign(R)          // ★ 必须在左移之前记下符号
    (R, Q) 同步左移一位
    if s >= 0: R = R - |Y|    // 上一步余数为正 → 减
    else:      R = R + |Y|    // 上一步余数为负 → 加
    Q 末位上商：R >= 0 记 1，R < 0 记 0

if R < 0:
    R = R + |Y|          // 末位商 0，余数须真正恢复一次

三、与恢复余数法的对照

	恢复余数法	加减交替法
每步操作次数	1 或 2 次（不够减要多做一次加法）	恰好 1 次
总步数	不固定	固定 $n$ 步
末尾处理	不需要	末位余数为负时修正一次
控制逻辑	需要"要不要恢复"的条件分支	每步结构完全相同，只是加或减
实际采用	很少	普遍采用

四、定点小数与定点整数：只差四处口径

算法骨架一个字都不用改——"正 1 减、负 0 加"、每步固定一次加减、末位余数为负要修正一次，三条全部照搬。要改的只是小数点约定带来的四处口径：

	定点小数	定点整数
被除数怎么扩展	低位补 $n$ 个 0	高位补 $n$ 个 0
$R$ / $Q$ 初值	$R$ = 被除数， $Q$ = 全 0	$R$ = 全 0， $Q$ = 被除数
首次试减	$R$ 初值非 0，必须做， $Q_{n} = 1$ 即溢出	$R$ 初值全 0，商必不超过 $n$ 位，可省
最终余数	$R$ 被左移了 $n$ 次，真实余数 $= R \times 2^{- n}$	$R$ 里就是真实余数，不用还原

判据只有一句：看 0 补在被除数的高位还是低位。 补在低位（小数）则首次试减不能省、余数要乘 $2^{- n}$ ；补在高位（整数）则两者都不必。省掉首次试减时，第一步的"上一步余数符号"取 $R$ 的初值 $0$ 、按非负处理，所以第一步做减法——与有首次试减时的第一次操作一致。

而 $2 n$ 位被除数除以 $n$ 位除数（双精度除法）不做任何扩展， $R$ 初值装被除数高 $n$ 位，这时首次试减是唯一的溢出判据，绝不能省。三种情形的对照见总述篇。

逐步走一遍同一个 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.1000`
第 1 步	负	$R + Y = 1.1000 + 0.1101 = 0.0101$	`0.0101`（正）	$q_{1} = 1$
左移			`0.1010`
第 2 步	正	$R - Y = 0.1010 + 1.0011 = 1.1101$	`1.1101`（负）	$q_{2} = 0$
左移			`1.1010`
第 3 步	负	$R + Y = 1.1010 + 0.1101 = 0.0111$	`0.0111`（正）	$q_{3} = 1$
左移			`0.1110`
第 4 步	正	$R - Y = 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{144}{256} = \frac{9}{16} = {0.1001}_{2}$ ✓

与恢复余数法的对照：商和余数完全相同，但恢复余数法为这 4 位商做了 7 次加减（含 2 次纯恢复），加减交替法只做了 5 次（1 次首次试减 + 4 步），且每一步的操作次数都是 1。

补码加减交替法（题面给的是补码除法、要按同号异号起步时展开）

上面讨论的是原码除法。补码除法也可以用加减交替，规则形式相同但判据换成"同号异号"：

判断	操作
被除数与除数同号	初始做减法
被除数与除数异号	初始做加法
余数与除数同号	上商 1，下一步做减
余数与除数异号	上商 0，下一步做加
末位	恒置 1

商直接就是补码表示，不需要单独处理符号。

"末位恒置 1"是补码除法专属：不管末位余数是正是负，商的末位一律置 1，带来的精度损失最大为 $2^{- n}$ 。这与原码加减交替法"末位余数为负才修正"是两套不同的收尾方式，不能互换套用。

考点速记

恢复那一步能省，依据是恒等式 $2 (R_{i} + Y) - Y = 2 R_{i} + Y$ ——"恢复 $+$ 左移 $+$ 减"等价于"左移 $+$ 加"，不是近似；规则即"正、1、减，负、0、加"，每步固定一次加或一次减。
判加减看上一步（左移之前）的余数符号（单符号位下左移会顶掉符号位）；末位余数为负仍要修正一次，因为"不恢复"依赖后续的左移，末位之后没有左移可依赖。首次试减的口径与恢复余数法完全相同——那位商是溢出判据，不是第一位商。
它的真正价值是步数固定——时序可预测（除法指令的周期数是常数，便于流水线调度）、控制逻辑规整（一位符号位就能决定加还是减）、计数器初值置 $n$ 减到 0 即结束，因而被实际计算机普遍采用。⚠️ 它不一定更快：商位全为 1（每步都够减）时两者操作次数相同，优势在确定性、不在平均速度。

这一节在真题里的位置：

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

复习优先级：这是实际计算机普遍采用的除法算法，理解"为什么能省掉恢复"这条恒等式是主线；会手推一遍、说得清末位为什么还要修正即可，不必反复练表格。

易错：读左移之后的最高位来判下一步加还是减。要看左移之前的符号。

易错：末位余数为负时不做修正。原码除法里余数应与被除数同号。

易错：把原码版与补码版的收尾互换。原码是"末位为负才加一次除数修正"（精确），补码是末位恒置 1（带已知误差上界 $2^{- n}$ 的简化约定），混用会得到既不精确也不符合约定的结果。

易错：认为加减交替法一定比恢复余数法快。商位全 1 时两者相同。

教材出处

不恢复余数法的推导（ $R_{i + 1} = 2 (R_{i} + Y) - Y = 2 R_{i} + Y$ ）、"正、1、减，负、0、加"六字要点、"运算中每次循环内的步骤都是规整的，差别仅在做加法还是减法"、"如果在最后一步上商为 0，则必须恢复余数"：袁春风《计算机组成与系统结构》第 3 版 §3.3.6 原码除法运算，印刷页 p73
"在计算机中很少采用恢复余数除法，而普遍采用不恢复余数除法"：同书印刷页 p73
恢复余数除法与不恢复余数除法两种方式的划分、上商与恢复的算法要点：同书印刷页 p71

真题练习

2025Q449分 2024Q152分 2020Q4313分

不恢复余数除法（加减交替法）

恢复那一步能省掉，靠的是一个恒等式

交互可视化

一、恢复那一步能省掉，是一次代数化简

二、算法流程

三、与恢复余数法的对照

四、定点小数与定点整数：只差四处口径

考点速记

相关知识

真题练习

相关真题（3题）

相关文章

不恢复余数除法（加减交替法） ​

恢复那一步能省掉，靠的是一个恒等式 ​

交互可视化 ​

一、恢复那一步能省掉，是一次代数化简 ​

二、算法流程 ​

三、与恢复余数法的对照 ​

四、定点小数与定点整数：只差四处口径 ​

考点速记 ​

相关知识 ​

真题练习 ​

相关真题（3题）

相关文章

不恢复余数除法（加减交替法）

恢复那一步能省掉，靠的是一个恒等式

交互可视化

一、恢复那一步能省掉，是一次代数化简

二、算法流程

三、与恢复余数法的对照

四、定点小数与定点整数：只差四处口径

考点速记

相关知识

真题练习