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

Question

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

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

Answer 1

《计算机编程的艺术》第二卷的副标题是“半数值算法”。这是合适的，因为当您将数字视为方程而不是数字时，解决方案相当简单。 将数字视为 Hx + L，其中 x 为 2

64

。如果我们除以，称之为 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

64

，这仍然会通过某个除法得出 128，这将提高硬件故障（正如人们所指出的）Y 应该是 1。因此，您可以将问题重新表述为 ^(Ax3

+ Bx

2 + Cx + D) / Y^{，其中 x 为 2}32^{。您现在可以向下：} (A / Y)x3 ^{+ (((A % Y)x + B) / Y)x}2 + (((((A % Y)x + B) % Y)x + C) / Y)x + ((((((A % Y)x + B) % Y)x + C) / Y)x + D) / Y^{。如果您只有 64 位除法：您进行四次除法，在前三个除法中，您取余数并将其上移 32 位和或移入下一个除法的下一个系数中。 这是已经给出两次的解决方案背后的数学原理。}

如果您使用架构可以处理的最大可能的本机表示（64 位）来存储值（128 位），您将在处理除法的中间结果时遇到问题（正如您已经发现的:)）。

Answer 2

可以在

here

找到一个简单的实现（在Delphi中）。

我有一个

DECIMAL

Answer 3

您可以轻松地将我的 C 代码扩展为 128 位、256 位、512 位甚至 1024 位除法。

// in-place divide Dividend / Divisor including previous rest and returning new rest
static void Divide32(DWORD* pu32_Dividend, DWORD u32_Divisor, DWORD* pu32_Rest)
{
    ULONGLONG u64_Dividend = *pu32_Rest;
    u64_Dividend <<= 32;
    u64_Dividend |= *pu32_Dividend;

    *pu32_Dividend = (DWORD)(u64_Dividend / u32_Divisor);
    *pu32_Rest     = (DWORD)(u64_Dividend % u32_Divisor);
}

// in-place divide 96 bit DECIMAL structure
static bool DivideByDword(DECIMAL* pk_Decimal, DWORD u32_Divisor)
{
    if (u32_Divisor == 0)
        return false;

    if (u32_Divisor > 1)
    {
        DWORD u32_Rest = 0;
        Divide32(&pk_Decimal->Hi32,  u32_Divisor, &u32_Rest); // Hi FIRST!
        Divide32(&pk_Decimal->Mid32, u32_Divisor, &u32_Rest);
        Divide32(&pk_Decimal->Lo32,  u32_Divisor, &u32_Rest);
    }
    return true;
}

如何使用 CPU 的本机 64 位操作来做到这一点？

Answer 4

由于您想要

native

操作，因此您必须使用一些内置类型或内部函数。

所有

以上答案只会为您提供一般的C解决方案，不会被编译为除法指令 大多数现代 64 位编译器都有一些方法来进行 128×64 除法。在 MSVC 中使用 _div128()

和

_udiv128()

所以你只需要调用 _udiv128(hi, lo, divisor, &remainder) _div128

内在函数将 128 位整数除以 64 位整数。返回值保存商，内在函数通过指针参数返回余数。

_div128

是 Microsoft 特定的。

_(u)div128

直接映射到 CPU 的

缩小 (i)div 指令

，因此它会像指令本身的行为一样在溢出时出错。因此，您需要在调用之前检查是否溢出

在 Clang、GCC 和 ICC 中有一个

__int128

---

类型，你可以直接使用它

unsigned __int128 div128by32(unsigned __int128 x, uint64_t y)
{
    return x/y;
}

这不是缩小操作。结果和所有操作数的宽度相同，因此不会发生溢出。在底层，它会检查是否是 128 到 64 除法，并使用上面的

(i)div

 指令，并且仅在除数超过 64 位时才执行软件除法