为什么这个使用 32 位除法的简单 64-bit/32-bit 除法算法有效？

Question

我一直在寻找一种 64-bit/32-bit 除法算法，最好是代码大小较小的 32 位 x86 机器。我发现 this 非常简单，但看不出它是如何工作的。

算法如下

我们正在计算 x / y，其中 x 是 64 位，y 是 32 位。两者都是无符号的。
x.l 是 x 的低位，x.h 是 x 的高位，假设是小端机器。
h <- x.h / y
x.h <- x.h % y
x.l <- x / y, (x.h <- x % y)； 64-bit/32-bit 除法仅在商适合 32 位时有效，在这种情况下似乎是正确的。
x.h <- h
return x

我的数学知识太短，无法轻松获得此算法。你能帮我理解这个算法吗？

这是我写的一个测试程序，看看能不能用。

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

typedef union {
    uint64_t q;
    struct {
        uint32_t l;
        uint32_t h;
    };
} uint64_u;

uint64_t div_(uint64_t _x, uint32_t y) {
    uint64_u x = {_x};
    uint32_t h = x.h / y;
    x.h = x.h % y;
    __asm__ (
        "div %2":
        "+a" (x.l),
        "+d" (x.h):
        "r" (y)
    );
    x.h = h;
    return x.q;
}

int main() {
    for (int i = 0; i < 1000000; ++i) {
        uint64_t x = (uint64_t)rand() << 32 | rand();
        uint32_t y = rand() % RAND_MAX + 1;
        uint64_t r0 = x / y;
        uint64_t r1 = div_(x, y);
        if (r0 != r1) {
            abort();
        }
    }
    return 0;
}

Answer 1

该算法改编自高中教授的经典长除法：

使用 2 进制代替 10 进制³²
将 64 位除数除以 32 位除数类似于将两位数 A:B 除以一位数 C
取第一个数字A并将其除以被除数C：在A中得到D次C, 余数 E
取下一个位B：在E:B中去F次C，余数G （在代码中被忽略，但可以通过指针返回）
结果是 D:F，如代码中所构造的那样。

该代码使用 div 指令，该指令采用从 (x.h % y):(x.l) 构造的 64 位操作数 EDX:EAX。参见 https://godbolt.org/z/7x9K8dzsf

完全可移植的版本，没有汇编并且只使用 32 位操作更难以高效地编写。

为什么这个使用 32 位除法的简单 64-bit/32-bit 除法算法有效？

Why does this simple 64-bit/32-bit division algorithm using 32-bit division work?

c

algorithm

division