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

64 ビット整数乗算の上位部分の取得

C では、 i と j が 64 ビット符号なし整数の場合、 i * j はその積の下位 64 ビット、つまり (i * j) mod を生成します。 2^64。積の上位部分を取得するには、次のアプローチを検討してください。

128 ビット乗算の使用:

コンパイラが 128 ビット整数をサポートしている場合 (例: __uint128_t) )、128 ビット乗算を実行して上位 64 ビットを抽出すると、最も効率的な方法です。

YAK のアプローチ (32 ビット乗算を使用):

これには、各 64 ビット整数を 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;

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