2つの符号なし整数（HW）を乗算する32ビットを得る

Question

私はCSAPPを読んで宿題に関する質問を完了しようとしています。 w = 32と仮定すると、2.75は、32ビットの符号なし整数を2つ増やして上位32ビットを得ることです。与えられた関数int signed_high_prod(int x, int y)は、xの上位32ビットを計算します。 xとyが2の補数形式である場合のy unsigned int unsigned_high_prod(unsigned x, unsigned y)の実装にはint signed_high_prod(int x, int y)を使用する必要があります。

グーグルで私はx'.y' = x.y + x.y_31.2^32 + y.x_31.2^32 + x_31.y_31.2^64を見つけました。ここで、x 'とy'はそれぞれxとyの符号なしの形式です。

私はまだ答えを理解できません。

unsigned unsigned_high_prod(unsigned x, unsigned y){ 
    unsigned p = (unsigned) signed_high_prod((int) x, (int) y) 
    if((int) x < 0){ 
     p += y; 
    } 
    if((int) y < 0){ 
     p += x; 
    } 
    return p; 
} 

なぜ最終結果が結果に影響しないのですか？なぜx < 0だからx_31 = 1、プラスy？ yと同じです。

Answer 1

符号付き2の補数32ビット整数を符号なし32ビット整数に変換するには、負の値の場合は2³²を加算します。

signed_high_prodは符号付き乗算を行い、製品のビット63から32を返します。 unsigned_high_prodは、符号なし乗算に対して同じ処理を行い、signed_high_prodを使用して、符号なし乗算と符号付き乗算の差を補正します。

その後

Let N(i) = { 1, i < 0 
      { 0, i >= 0 

Let U(i) = i + N(i)·2³² { −2³¹ <= i < 2³¹ } 

：

U(x)·U(y) = (x + N(x)·2³²)·(y + N(y)·2³²) 
      = x·y + x·N(y)·2³² + N(x)·2³²·y + N(x)·2³²·N(y)·2³² 
      = x·y + x·N(y)·2³² + y·N(x)·2³² + N(x)·N(y)·2⁶⁴ 

⌊U(x)·U(y)/2³²⌋ = ⌊x·y/2³²⌋ + x·N(y) + y·N(x) + N(x)·N(y)·2³² 

符号なし、32ビット整数の四則演算は、我々が持っている、剰余2³²を行いますので：

⌊U(x)·U(y)/2³²⌋ mod 2³² = (⌊x·y/2³²⌋ + x·N(y) + y·N(x) + N(x)·N(y)·2³²) mod 2³² 
         = (⌊x·y/2³²⌋ + x·N(y) + y·N(x)) mod 2³² 

私は計算のためのアカウントが実行したことを信じていますあなたのunsigned_high_prod機能によって。

Answer 2

ビットレベルの乗算を実行するには、ビットを最初に拡張してから、一連のシフトと加算を実行する必要があります。例えば、w = 3と仮定すると、x = [011]とy = [101]とする。次のように（すなわち、x = 3とy = -3 (signed) or 5 (unsigned)）

符号なしの製品を実行するために、我々は最初にゼロ拡張：（上記ビット6とを無視する）

 000 011 
    * 000 101 
    -------- 
    000 011 
    + 001 100 
    -------- 
    001 111 
    ======== 

したがって、符号なしの上位ビットは[001]

あります署名された製品を実行するには

、我々は最初の符号拡張を次のよう

 000 011 
    * 111 101 
    -------- 
    000 011 
    + 001 100 
    + 011 000 ** 
    + 110 000 ** 
    + 100 000 ** 
    -------- 
    110 111 
    ======== 

したがって、記号高位ビットのビットが[110]

であることに注意してください。符号付きと符号なしの上位ビットの相違点は、符号付きの場合に[111] * [011]を追加したことです。したがって、この量を減算して、符号なし高位ビットを得る必要があります。

The unsigned high order bits = [110] - [111] * [011] 
          = [110] - [101] 
          = [110] + [011] ?? 
          = [001] (as above) 

[111] = -1ので、補正量、- [111] * [011]は- (-1 * x) = xと等価です。

したがって、yが負の場合（この場合）は、xを追加して結果を修正する必要があります。単純に、xが負の場合、yを追加して結果を修正する必要があります。

?? -[101] = ~[101] + 1 = [010] + [001] = [011]