Ist-Stand-Multiplikation Algorithmus zur Multiplikation 2 positive zahlen?
Ist booth-Algorithmus für die Multiplikation nur für die Multiplikation 2 negative zahlen (-3 * -4)
oder eine positive und eine negative Zahl (-3 * 4)
? Immer wenn ich multiplizieren mit 2 positiven zahlen mit Stand-Algorithmus erhalte ich ein Falsches Ergebnis.
Beispiel : 5 * 4
A = 101 000 0 //binary of 5 is 101
S = 011 000 0 //2's complement of 5 is 011
P = 000 100 0 //binary of 4 is 100
x = 3 number of bits in m
y = 3 number of bits in r
m = 5
-m = 2-Komplement von m
r = 4
-
Nach rechts Verschiebung von P um 1 bit 0 000 100
-
Nach rechts Verschiebung von P um 1 bit 0 000 010
-
P+S = 011 001 0
Nach rechts-shift um 1 bit 0 011 001
-
Verwerfen des LSB 001100
Aber das kommt auf das Programm des 12 . Es sollte 20(010100)
UPDATE nach @ ruakh Antwort
5 * 4 = 20
m = 0101 is 5
r = 0100 is 4
A = 0101 0000 0
S = 1010 0000 0
P = 0000 0100 0
-
shift P nach rechts um 1 bit : 0 0000 0100
-
shift P nach rechts um 1 bit : 0 0000 0010
-
P+S = 10100010
Die Verlagerung rightby 1 bit : 1101 0001 -
P+A = 1 0010 0001
here 1 is the carry generated
verschieben nach rechts um 1 bit : 110010000
Verlassen des LSB : 11001000 (nicht gleich 20)
Du musst angemeldet sein, um einen Kommentar abzugeben.
Bist du nicht geben genug Platz für Ihre Zeichen-handling. 5 ist nicht
101
, aber0101
: es beginnt mit einem0
, da die Werte, beginnend mit1
negativ sind.101
ist tatsächlich -3: es ist das Zweierkomplement von011
3. Ähnlich 4 ist nicht100
, aber0100
;100
ist -4. Also, wenn Sie multiplizieren101
durch100
, bist du eigentlich die Multiplikation von -3 -4; das ist, warum Sie bekommen 12.P+A
im 4. Schritt, es ist ein carry in MSB von P+A . Wenn ich es weglassen, bekomme ich die richtige Antwort. Aber warum haben wir es weglassen. Wie im 4. Schritt :P+A = 110110001 + 010100000 = 1 001010001
finden Sie die carry (1) in der MSB . Wenn ich es weglassen werde ich die richtige Antwort im nächsten Schritt, wo ich weglassen müssen LSB der Zahl.1011
bedeutet das gleiche wie...11111011
, nicht...00001011
. Also, wenn Sie durchgeführt sign extension, dieser trug1
würde tatsächlich auch weiter nach Links auf unbestimmte Zeit, verändert sich die ganze1
s zu0
s auf dem Weg.0010001111
aber ich sollte10001111
. Zwei Nullen in der MSB ' s fehlen. Wird es einen Unterschied machen10001111
wäre falsch, da in zweier-Komplement-notation, bezeichnet eine negative Zahl (-113).Booth-Algorithmus ist für Ganzzahlen mit Vorzeichen, d.h. jeder kann entweder positiv oder negativ oder null ist.
Hier ein Beispiel für ein C-Programm, das zeigt sowohl eine Umsetzung und die Zwischenergebnisse der Multiplikation zweier 8-bit signed (2-Komplement) ganze zahlen und bekommen einen 16-bit signed Produkt:
Ausgabe:
Ich denke
x
sollte2
statt3
-- da3
ist11
nur zwei bits lang ist.Unten, eine Implementierung von Booth ' s Algorithmus entsprechend seiner Flussdiagramm, dargestellt in Kapitel 9, in dem so genannten Buch "Computer-Organisation und Architektur, achte Auflage - William-aufschübe.
Dieses Programm multipliziert zwei zahlen in 4 bits.
Wenn VERBOSE == 1, das Programm zeigt die verschiedenen Schritte des Algorithmus.
PS: Das Programm manipuliert die zahlen als strings.
Glück!
Ist es immer empfohlen, um X+1 bits für eine X-bit Anzahl Multiplikation mit Booth-Algorithmus. Extra ein bit wird verwendet, um das Vorzeichen Werte. Das ist ein problem mit deinem Ansatz. Ohne, dass eine Zahl wie 101 (dezimal:5) wirkt als negative 1.
Dem Booth-Algorithmus wird verwendet für die Multiplikation negativer zahlen, entweder eine von Ihnen unterzeichnet werden soll, oder beide von Ihnen unterzeichnet.
wir können nicht für den Booth-Algorithmus für zwei zahlen ohne Vorzeichen.
Dem Booth-Algorithmus wird verwendet für die Multiplikation negativer zahlen, entweder eine von Ihnen unterzeichnet werden soll, oder beide von Ihnen unterzeichnet.
wir können auch den Booth-Algorithmus für zwei zahlen ohne Vorzeichen, aber wir müssen überprüfen, ob die zahlen in einem bestimmten Bereich.
Zum Beispiel, wenn wir an den 4-bit-zahlen wie 2*3 ist möglich .Wenn wir 9*4 oder 9*-4 * oder * -9*-4 ist nicht möglich, da 9 oder -9 ist nicht im Bereich von 4-bit-zahlen, so booth-Algorithmus der Multiplikation ist nicht möglich.