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

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

C では、2 つの 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.
3. の合計の上位 32 ビット。

手順 2 の結果を、a_lo * b_lo.

注意事項

これらの演算を実行するときは、整数のオーバーフローに注意する必要があります。次のコードは、オーバーフローの処理方法を示しています。

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 中国語 Web サイトの他の関連記事を参照してください。