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

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

在C 中，如果i 和j 是64 位元無符號整數，則i * j 產生其乘積的低64 位，即(i * j) mod 2^64。要獲得乘積的較高部分，請考慮以下方法：

使用128 位元乘法：

如果編譯器支援128 位元整數（例如__uint128_t ），執行128 位元乘法並提取高64 位元是最有效的

YAK 的方法（使用32 位元乘法）：

這涉及將每個64 位元整數分成兩個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;

uint64_t multhi = a_hi * b_hi + (a_hi * b_lo >> 32) + (b_hi * a_lo >> 32) + a_lo * b_lo;

處理溢位：

但是，上述計算執行128 位元算術，這可能會導致溢出。為了在限制為64 位元算術時處理此問題，以下實作會針對溢位進行調整：

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 = ((uint32_t)a_x_b_mid + (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;

注意： 如果可以接受高64 位元中的1 位元錯誤，則進位位的計算可以省略。

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