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

Question

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

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

Answer 1

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

但是你总是可以使用更小的表示。那么四个 32 位的数字呢？这样您就可以使用本机 64 位操作而不会出现溢出问题。

可以在这里找到一个简单的实现（在 Delphi 中） 。

Answer 2

我怎么能做到这一点，使用来自 CPU 的本机 64 位操作？

由于您需要本机操作，因此您必须使用一些内置类型或内在函数。以上所有答案只会为您提供不会编译为除法指令的通用 C 解决方案

大多数现代 64 位编译器都有一些方法可以进行 128×64 除法。在 MSVC 中使用_div128()，_udiv128()所以你只需要调用_udiv128(hi, lo, divisor, &remainder)

内在函数将_div128128 位整数除以 64 位整数。返回值保存商，内在函数通过指针参数返回余数。_div128是微软特有的。

在 Clang、GCC 和 ICC 中有一个__int128类型，你可以直接使用它

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

Answer 3

我有一个DECIMAL由三个 32 位值组成的结构：Lo32、Mid32 和 Hi32 = 96 位。

您可以轻松地将我的 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;
}