為什么這種使用32位除法的簡單64位/32位除法演算法有效？-有解無憂

我正在尋找一種 64 位/32 位除法演算法，最好是用于 32 位 x86 機器的小代碼大小。我發現這個非常簡單，但看不出它是如何作業的。

演算法如下。

我們正在計算64 位和32 位的位置x / y。兩者均未簽名。xy
x.l是的低位x，x.h是的高位x，假設是小端機器。
h <- x.h / y
x.h <- x.h % y
x.l <- x / y, (x.h <- x % y); 64 位/32 位除法僅在商適合 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;
}

uj5u.com熱心網友回復：

該演算法是對高中教授的經典長除法方法的改編：

代替基數 10，使用基數 2 ³²
將 64 位被除數除以 32 位除數類似于將 2 位數字除以A:B一位數字C
取第一個數字 A并除以被除數C：in Ago DtimesC余數E
取下一個數字 B：在E:Bgo FtimesC中，余數G（在代碼中被忽略，但可以通過指標回傳）
結果D:F與代碼中的構造相同。

該代碼使用一條div指令，該指令采用如上構造的 64 位運算元 EDX:EAX (x.h % y):(x.l)。見https://godbolt.org/z/7x9K8dzsf

一個完全可移植的版本，沒有匯編并且只使用 32 位操作更難以高效地撰寫。

轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/424328.html

標籤：C 算法分配

上一篇：將污染減半所需的最少過濾器數量

下一篇：是否可以在具有相同大O可擴展性的消費級處理器上實作PRAMCRCW演算法？