Two's Complement Division Algorithm (Intel)

Question

On Intel machines, integer division requires a sequence of two instructions:

\n

\n
1. After you store the dividend in the a register (e.g., %eax), you extend the sign of the dividend into the corresponding d register (%edx).
\n
2. The idiv or div instruction itself then performs the division and places the quotient in the a register and the remainder in the d register.\nBut why does the operation require the sign extension? What does the algorithm actually do with that sign extension value? How does the remainder wind up in that same space?
\n

\n

I am not asking how to do integer division on Intel or what happens if you do not follow the rules. I want to know why these are the rules. I want to know how the algorithm works, such that it must use the sign-extended register space somehow.

\n

Let's take a manageable example with 8-bit operands\xe2\x80\x94decimal -65 / 3.

\n

         -------------------\n00000011 ) 11111111 10111111\n

\n

If it were 65/3 (with a positive dividend), I could see how the left padding would provide room for the subtraction\xe2\x80\x94

\n

                    00010101\n         -----------------------\n00000011 ) 00000000 01000001\n               0000 0011\n               ---------\n               0000 000100\n                 00 000011\n                 ---------\n                 00 00000101\n                    00000011\n                    --------\n                    00000010  (R)\n

\n

（我在上面进行了缩写，没有显示减去 0 的实例。此外，我显示了减法本身，而不是除数的补码否定的加法，但基本点保持不变。）这里，0 填充腾出空间来减去每一位。但是，当被除数是补码负整数时，我不知道这将如何工作。而且，即使在这种积极的情况下，也不清楚为什么剩余部分最终会出现在容纳填充物的空间中，除了它已经可用的仅仅是方便之外。

\n

谢谢你！

\n

Answer 1

这两个步骤用于将一个 32 位有符号值除以另一个 32 位有符号值。该idiv指令将 64 位有符号整数除以 32 位整数。因此，如果您只有 32 位整数，则需要先将其转换为 64 位整数。

为什么idiv设计为进行 64 位除以 32 位除法？出于同样的原因，mul设计为通过 32 位乘 32 位乘法生成 64 位结果：以便您可以使用这些原语在 32 位组上实现任意精度算术。

编辑： 为什么任意精度算术需要它？让我们看一下十进制长除法问题：

512 / 7 = ?

对于结果的第一个数字，我们需要计算出有多少次7适合51；我们计算truncate(51/7) = 7，因此下一个数字将是7，我们将其相乘、移位和相减得到：

512 / 7 = 7?
490
---
 22

我们对 重复上述操作truncate(22/7) = 3，得到：

512 / 7 = 73
490
---
 22
 21
---
  1   (remainder)

请注意，我们使用“oracle”将两位数除以一位数；并在不同的两位数组上重复使用它，以一一产生结果的数字。同样，如果您的“数字”是 32 位字，则您需要一个将 64 位数字除以 32 位数字的预言机。