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

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

C では、2 つの 64 ビット符号なし整数の乗算 (uint64_t)結果は乗算の下位ビットを表す値となり、実質的に 2^64 を法とする結果が得られます。これにより、特定の計算にしばしば必要となる上位ビットをどのように取得するかという問題が生じます。

実装アプローチ

1. 128-ビット乗算:

コンパイラーが 128 ビット数値 (__uint128_t) をサポートしている場合、128 ビット乗算を実行して上位 64 ビットを抽出することが、上位の数値を取得する最も効率的な方法となります。 bits.

2. 32 ビット乗算と 64 ビット累算:

128 ビット数値がサポートされていない場合は、移植可能でシンプルなソリューション各 64 ビット数値を 2 つの 32 ビット数値に分解し、それらに対して 32 ビット乗算を実行し、整数のオーバーフローを避けるように注意しながら 64 ビットの部分積を慎重に累積します。

アセンブリ命令:

x86 などの一部のアーキテクチャでは、そのような 64 ビット整数の乗算を実行するように設計された特定のアセンブリ命令 (MULH など) があります。ただし、これらの命令を C で使用するには、アセンブリ プログラミングの知識が必要であり、前述の C のアプローチほど移植性が高くない可能性があります。

実装例:

次の C コード32 ビット乗算と 64 ビット累積アプローチを実装します:

uint64_t mulhi(uint64_t a, uint64_t b) {
  uint32_t a_lo = (uint32_t)a;
  uint32_t a_hi = a >> 32;
  uint32_t b_lo = (uint32_t)b;
  uint32_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 + a_lo * b_hi; // Avoid overflow
  uint64_t b_x_a_mid = b_hi * a_lo;
  uint64_t a_x_b_lo = a_lo * b_lo;

  uint64_t multhi = a_x_b_hi +
                   (a_x_b_mid >> 32) + (b_x_a_mid >> 32) +
                   (a_x_b_lo >> 64);

  return multhi;
}

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