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

提取64 位元整數乘法的高位元部分

在C 中，兩個64 位元無符號整數(uint64_t) 相乘的結果在僅包含乘積下部的uint64_t 中（即(i * j) mod 2^64）。如果您想要獲得乘法的較高部分，這裡有一些有效的方法：

使用128 位元數字

如果您的編譯器支援128 位元數字(例如，在GCC 中使用__uint128_t），您可以執行128 位元乘法並提取高64 位元。此方法可能是最有效的。

乘法分解

如果您的編譯器不支援128 位元數字，則可以將每個64 位元整數分解為以下部分：

• a = (a_hi
• b = (b_hi

其中a_hi、a_lo、b_hi 和 b_lo 是 32 位元無符號整數。

演算法

要計算乘法的高位部分(a_hi * b_hi)，您可以請依照下列步驟操作：

1. 計算乘積a_hi b_hi、a_hi b_lo、b_hi a_lo 和 a_lo b_lo。
2. 增加乘積a_hi b_hi 以及 a_hi b_lo 和 b_hi * a_lo 總和的高 32 位。
3. 將步驟 2 的結果加到 a_lo * b_lo 的高 32 位元。

注意事項

執行這些操作時，必須小心整數溢位。以下程式碼說明如何處理溢位：

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) >> 32;
uint64_t b_x_a_mid = (b_hi * a_lo) >> 32;
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 + b_x_a_mid + carry_bit;

return multhi;

請注意，此程式碼可能並不完全準確，但它提供了乘法較高部分的良好近似值。

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