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

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

C では、2 つの 64 ビット整数 (uint64_t) の乗算の結果は次のようになります。積の下位 64 ビットを表す値、つまり (i * j) mod(2^64)。上位 64 ビットを取得するには、さまざまな方法を使用できます。

128 ビット数値の使用

コンパイラが 128 ビット整数 (__uint128_t) をサポートしている場合、最も効率的なアプローチは、128 ビット算術演算を使用して乗算を実行し、上位を抽出することです。 64 ビット。

64 ビット算術のための移植可能なアプローチ

128 ビット数値をサポートしないコンパイラの場合、移植可能な解決策は、各 64 ビット整数を分割することです。を 2 つの 32 ビットの半分に分割し、64 ビット乗算を使用して乗算します。次に、上位半分と下位半分が結合されて、完全な 128 ビットの積が計算されます。

ただし、64 ビット演算を使用すると、この計算でオーバーフローが発生する可能性があります。以下のコードは、上位 64 ビットの計算中にオーバーフローを処理する実装を提供します。

uint64_t mulhi(uint64_t a, uint64_t b) {
    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;
    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;
}

carry_bit の計算を省略すると、上位 64 ビット値が 1 ずれる可能性があることに注意してください。

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