0

2 つの 32 ビット数値 a と b を掛け合わせて 64 ビットの結果を得ようとしています。a と b が符号なし 32 ビット整数であるため、次のように思いつきました。

r = a * b

r = ((ah << 16) + al) * ((bh << 16) + bl)
  = ((ah * 2^16) + al) * ((bh * 2^16) + bl)
  = (ah * 2^16) * (bh * 2^16) + (ah * 2^16) * bl + al * (bh * 2^16) + al * bl
  = (ah * bh * 2^32) + (ah * bl * 2^16) + (al * bh * 2^16) + (al * bl)
  = ((ah * bh) << 32) + ((ah * bl) << 16) + ((al * bh) << 16) + (al * bl)
  = ((ah * bh) << 32) + ((ah * bl + al * bh) << 16) + (al * bl)

次に、次のようにcに翻訳しました

static void _mul64(unsigned int a, unsigned int b, unsigned int *hi, unsigned int *lo) {
    unsigned int    ah = (a >> 16), al = a & 0xffff,
                    bh = (b >> 16), bl = b & 0xffff,
                    rh = (ah * bh), rl = (al * bl),

                    rm1  = ah * bl,         rm2  = al * bh,
                    rm1h = rm1 >> 16,       rm2h = rm2 >> 16,
                    rm1l = rm1 & 0xffff,    rm2l = rm2 & 0xffff,
                    rmh  = rm1h + rm2h,     rml  = rm1l + rm2l;

    rl = rl + (rml << 16);
    rh = rh + rmh;
    if(rml & 0xffff0000)
        rh = rh + 1;
    *lo = rl;
    *hi = rh;
}

ただし、a = 0xFFFFFFFF と b = 0xFFFFFFFF を乗算して 0xFFFFFFFE00000001 を生成するこの小さなテストを実行すると、代わりに 0xFFFFFFFD00000001 が得られます。私は間違っていますか？

int main(int argc, char **argv) {
    unsigned int a, b, rl, rh;
    unsigned long long r;
    unsigned long long r1, r2, r3;

    a = 0xffffffff;
    b = 0xffffffff;
    mul64(a, b, &rh, &rl);
    r1 = ((unsigned long long) rh << 32) + rl;
    r2 = (unsigned long long) a * b;

    _mul64(a, b, &rh, &rl);
    r3 = ((unsigned long long) rh << 32) + rl;
    printf("a = 0x%08x, b = 0x%08x\n", (unsigned) a, (unsigned) b);
    printf("_mul64: 0x%16llx\n", (unsigned long long) r3);
    printf("a * b = 0x%16llx\n", (unsigned long long) r2);
    return 0;
}
4

2 に答える 2

1

ここに16ビットの数量を追加しています

rm1l = rm1 & 0xffff,    rm2l = rm2 & 0xffff,
rmh  = rm1h + rm2h,     rml  = rm1l + rm2l;

rmlに 16 ビット左にシフトされた値を追加しrl、

rl = rl + (rml << 16);

これは、2 つの 16 ビット量の合計が 17 ビット量になると、キャリーを破棄します。

また、後者の合計は 32 ビットの範囲を超える可能性があり、その場合、別のキャリー ビットが失われます。

于 2012-07-11T19:19:37.943 に答える
0

すべての演算がイニシャライザで行われるため、デバッグが困難になります。これらの計算をすべて初期化子から移動し、最適化を無効にしてコードをコンパイルします。デバッガーでそれをステップスルーし、各ステップが期待どおりの値を生成していることを確認します。手で解いたアルゴリズムに従ってコードを見ていくと、コードとアルゴリズムが逸脱している場所を簡単に見つけることができるはずです。

于 2012-07-11T17:52:36.707 に答える