如何在 C 中獲得 64 位元整數乘法的上半部？

取得64 位元整數乘法的上半部

在C 中，兩個64 位元整數(uint64_t) 的乘法結果為表示乘積的低64 位的值，即(i * j) mod （2^64）。要取得高 64 位，可以採用多種方法。

使用128 位元數字

如果您的編譯器支援128 位元整數(__uint128_t)，則最有效的方法是使用128 位元算術執行乘法並提取高64 位位。

64 位元算術的可移植方法

對於不支援128 位元數字的編譯器，一個可移植的解決方案是將每個64 位元整數拆分為兩個32 位元的一半，並使用64 位元乘法將它們相乘。然後將上半部和下半部組合起來計算完整的 128 位元乘積。

但是，在使用 64 位元算術時，此計算可能會導致溢位。下面的程式碼提供了一個在計算高 64 位元時處理溢位的實作：

uint64_t mulhi(uint64_t a, uint64_t b) {
    uint64_t    a_lo = (uint32_t)a;
    uint64_t    a_hi = a >> 32;
    uint64_t    b_lo = (uint32_t)b;
    uint64_t    b_hi = b >> 32;

    uint64_t    a_x_b_hi =  a_hi * b_hi;
    uint64_t    a_x_b_mid = a_hi * b_lo;
    uint64_t    b_x_a_mid = b_hi * a_lo;
    uint64_t    a_x_b_lo =  a_lo * b_lo;

    uint64_t    carry_bit = ((uint64_t)(uint32_t)a_x_b_mid +
                             (uint64_t)(uint32_t)b_x_a_mid +
                             (a_x_b_lo >> 32) ) >> 32;

    uint64_t    multhi = a_x_b_hi +
                         (a_x_b_mid >> 32) + (b_x_a_mid >> 32) +
                         carry_bit;

    return multhi;
}

請注意，省略進位位的計算將導致高 64 位元值可能偏離 1。

以上是如何在 C 中獲得 64 位元整數乘法的上半部？的詳細內容。更多資訊請關注PHP中文網其他相關文章！