如何在 C 中提取 64 位元整數乘法的高位元部分？

Extracting the High Part of 64-bit Integer Multiplication

In C , multiplying two 64-bit intetic injg >) results in a value representing the lower 64 bits of the product. This operation is commonly used to achieve modular arithmetic, where the lower bits contain the desired remainder. However,有時候，我們也需要計算乘法的更高位部分。

最優方案

考慮以下場景：

如果使用支援128 位元數字的GCC 編譯器，最有效的策略是執行128 位元乘法並提取高64 位元。

uint64_t i = // some value
uint64_t j = // some value
uint64_t k = mulhi(i, j); // where mulhi() returns the higher part of the 64-bit multiplication

無 128 位元支援時的替代方案

如果沒有 128 位元支援，可以使用 Yakk 提供的方法。這個方法將

a

和 b 各分解為兩個 32 位數字，然後使用 64 位乘法分別計算這些較小數字的乘積。 分解如下：

現在，乘積可以表示為：

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;

但是，使用 64 位元對上述公式進行計算會產生溢位。因此，我們需要對中間結果進行特殊處理：

a * b = ((a_hi << 32) + a_lo) * ((b_hi << 32) + b_lo)

      = ((a_hi * b_hi) << 64) +
        ((a_hi * b_lo) << 32) +
        ((b_hi * a_lo) << 32) +
          a_lo * b_lo

稍做修改，如果不在乎高位部分多 1，則可以省略進位位的計算。

// 为防止溢出而引入的临时变量
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;

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