C で 64 ビット整数乗算の上位部分を抽出するにはどうすればよいですか?

64 ビット整数乗算の上位部分の抽出

C では、2 つの 64 ビット整数を乗算します ( uint64_t ) 結果は、積の下位 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 ビット数値をサポートする GCC コンパイラーを使用する場合、最も効果的な戦略128 ビットの乗算を実行し、上位 64 ビットを抽出します。

128 ビット サポートなしの代替手段

128 ビット サポートがない場合は、Yakk が提供する方法を使用できます。このメソッドは、

a と b をそれぞれ 2 つの 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;

ここで、積は次のように表すことができます:

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

ただし、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 = (((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;

わずかな変更を加えて、上位部分の余分な 1 を気にしない場合は、次の計算を省略できます。キャリービット。

以上がC で 64 ビット整数乗算の上位部分を抽出するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。