Holen Sie sich die 32 hohen Bits multipliziert zwei vorzeichenlose Ganzzahlen (HW)

Question

Ich lese CSAPP und versuche, die Hausaufgaben Fragen zu vervollständigen. Nehmen wir an, w = 32, 2.75 geht es darum, die hohen 32 Bits durch Multiplikation von zwei 32-Bit-Ganzzahlen mit Vorzeichen zu erhalten. Gegeben die Funktion int signed_high_prod(int x, int y), die die 32 Bits höherer Ordnung von x berechnet. y für den Fall, dass x und y in Zweierkomplementform vorliegen. int signed_high_prod(int x, int y) sollte bei der Implementierung unsigned int unsigned_high_prod(unsigned x, unsigned y) verwendet werden.

Durch Googeln fand ich x'.y' = x.y + x.y_31.2^32 + y.x_31.2^32 + x_31.y_31.2^64, wobei x 'und y' sind vorzeichenlose Form von x und y jeweils.

Ich kann immer noch nicht die Antwort verstehen.

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; 
} 

Warum die letzte Amtszeit keine Auswirkungen des Ergebnisses hat? warum wenn x < 0 so x_31 = 1, plus y? und das gleiche mit y.

Answer 1

Um eine vorzeichenbehaftete Zweierkomplement-32-Bit-Ganzzahl in eine vorzeichenlose 32-Bit-Ganzzahl zu konvertieren, fügen wir ihrem Wert 2³² hinzu, wenn sie negativ ist.

signed_high_prod führt eine vorzeichenbehaftete Multiplikation durch und gibt die Bits 63 bis 32 des Produkts zurück. Wir wollen unsigned_high_prod dasselbe für vorzeichenlose Multiplikation tun und signed_high_prod verwenden und dann die Differenz zwischen vorzeichenloser und vorzeichenbehafteter Multiplikation kompensieren.

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

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

Dann:

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³² 

Da die Arithmetik auf unsigned 32-Bit-Integer wird Modulo 2² durchgeführt werden, haben wir:

⌊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³² 

Ich glaube, dass Konten für die Berechnungen durchgeführt durch Ihre unsigned_high_prod Funktion.

Answer 2

Um eine Multiplikation auf Bit-Ebene durchzuführen, müssen wir zuerst die Bits erweitern und dann eine Reihe von Verschiebungen und Additionen durchlaufen. Wenn beispielsweise w = 3 angenommen wird, lassen Sie x = [011] und y = [101]. (Dh x = 3 und y = -3 (signed) or 5 (unsigned))

die unsigned Produkt ausführen können, wir zuerst Null erweitern, wie folgt: (ohne Berücksichtigung Bits 6 und höher)

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

Daher sind die unsigned höherwertigen Bits sind [001]

das signierte Produkt ausführen zu können, wir erste Vorzeichen erweitern, wie folgt:

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

daher das Zeichen Ed hohe Bits sind [110]

Hinweis, der Unterschied zwischen den vorzeichenbehafteten und vorzeichenlosen Bits hoher Ordnung (wie oben angegeben) ist, dass wir im signierten Fall [111] * [011] hinzugefügt haben. Daher müssen wir diesen Betrag subtrahieren, um die vorzeichenlosen Bits höherer Ordnung zu erhalten.

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

Da [111] = -1, der Korrekturbetrag, ist - [111] * [011] entspricht - (-1 * x) = x.Wenn y negativ ist (wie in diesem Fall), müssen wir das Ergebnis korrigieren, indem wir x hinzufügen. Wenn x negativ ist, müssen wir das Ergebnis korrigieren, indem wir y hinzufügen.

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