64-bit - 64 位机器上的无符号 128 位除法

Question

我有一个 128 位数字存储为 2 个 64 位数字(“Hi”和“Lo”)。我只需要把它除以一个 32 位数字。我该如何使用 CPU 的 native 64 位操作来做到这一点？

(请注意，我不需要任意精度库。只需要知道如何使用 native 操作进行这个简单的除法。谢谢)。

Answer 1

计算机编程艺术第二卷的副标题是半数值算法。这是合适的，因为当您将数字视为方程而不是数字时，解决方案相当简单。

将数字视为 Hx + L，其中 x 为 2⁶⁴。如果我们除以 Y，那么 Hx = (N + M)x 显然是正确的，其中 N 可以被 Y 整除，并且 M 小于 Y。为什么要这样做？ (Hx + L)/Y 现在可以表示为 (N/Y)x + (Mx + L)/Y。 N、N/Y 和 M 值都是整数:N 就是 H/Y，M 就是 H % Y 但是，因为 x 是 2⁶⁴，这仍然使我们除以 128，如果 Y 为 1，这将引发硬件故障(正如人们所指出的)。

因此，您可以将问题重新表述为 (Ax³ + Bx² + Cx + D)/Y，其中x 为 2³²。您现在可以向下:(A/Y)x³ + (((A % Y)x + B)/Y)x² + (( (((A % Y)x + B) % Y)x + C)/Y)x + ((((((A % Y)x + B) % Y)x + C)/Y)x + D )/Y。如果您只有 64 位除法:您进行四次除法，在前三个除法中，您取余数并将其上移 32 位和/或移入下一个除法的下一个系数中。

这是已经给出两次的解决方案背后的数学原理。