不归零除法算法

Question

有没有人知道使用非恢复除法（non-restoring division）分割无符号二进制整数的步骤？

在网上很难找到好的资料。

例如，如果 A = 101110 和 B = 010111

我们如何在非恢复除法中找到 A 除以 B？每个步骤中寄存器看起来像什么？

谢谢！

- CyberShot

---

@RaymondChen，错误的结果 - Imago

Answer 1

我的答复有点晚，但我希望对以后的访问者有用。

非恢复除法算法如下图所示：

在这个问题中，被除数（A）= 101110，即46，除数（B）= 010111，即23。

初始化：

Set Register A = Dividend = 000000
Set Register Q = Dividend = 101110
( So AQ = 000000 101110 , Q0 = LSB of Q = 0 )
Set M = Divisor = 010111, M' = 2's complement of M = 101001
Set Count = 6, since 6 digits operation is being done here.

接下来我们开始算法，我在下面的表格中展示了：

在表格中，SHL(AQ) 表示将 AQ 左移一位，保留 Q0 为空。

同样地，Q0 位置上的正方形符号表示 稍后将进行计算。

希望所有步骤都可以从表格中清晰地理解！

- Abid Rahman K

---

提醒一下：如果余数(A)变成负数，仅仅调整余数是不够的：要把商(Q)减去1。 - greybeard

Answer 2

1）将寄存器A的值设置为0（N位）
2）将寄存器M的值设置为除数（N位）
3）将寄存器Q的值设置为被除数（N位）
4）连接A和Q {A，Q}
5）重复以下“N”次（这里N是除数中的位数）：
  如果A的符号位等于0，
   则将A和Q组合向左移动1位并从A中减去M，
  否则将A和Q组合向左移动1位并从A中加上M
  现在，如果A的符号位等于0，则将Q [0]设置为1，否则将Q [0]设置为0
6）最后，如果A的符号位等于1，则将M添加到A中。
7）将A分配为余数，将Q分配为商。

- Jhashank Gandhi

---

这似乎只是用语言表达了（不完整）的图解，来自[Abid Rahman K的回答]（https://dev59.com/Q2fWa4cB1Zd3GeqPjrfC#14712244）。 - greybeard

@greybeard：如果这是准确的（我没有检查），那对于使用屏幕阅读器或其他无法处理文本图像的技术的人来说是有用的。 - Peter Cordes

（@PeterCordes：表达出来 对于 多个目的 有用，我已经做过了。不是我的反对票。） - greybeard

@老程序员，请检查一下是否准确，有时候步骤点说明比流程图更好。 - Jhashank Gandhi

我不明白告诉我：“我已经在其他问题中完成了相应的工作（甚至在上面声称过）”的意义，我没有投票反对，我认为这个答案并不是“没有用”的（将鼠标悬停在“反对三角形”上方）。 - greybeard