Ich bin nur neugierig, ob es einen Grund gibt, warum zur Darstellung von -1 in Binär das Zweierkomplement verwendet wird: Umdrehen der Bits und Hinzufügen von 1?
-1 wird durch 11111111 (Zweierkomplement) und nicht (für mich intuitiver) 10000001 dargestellt, was binär 1 mit dem ersten Bit als negativem Flag ist.
Haftungsausschluss: Ich verlasse mich für meinen Job nicht auf binäre Arithmetik!
Antworten:
Dies geschieht so, dass für die Addition keine spezielle Logik für den Umgang mit negativen Zahlen erforderlich ist. Lesen Sie den Artikel auf Wikipedia .
Angenommen, Sie haben zwei Zahlen, 2 und -1. In Ihrer „intuitiven“ Art und Weise Zahlen repräsentieren, würden sie sein
0010
und1001
jeweils (Ich bin auf 4 Bits für die Größe kleben). In der Art und Weise, wie sich die beiden ergänzen , sind sie0010
und1111
. Nehmen wir an, ich möchte sie hinzufügen.Die Zweierkomplementaddition ist sehr einfach. Sie fügen normalerweise Zahlen hinzu und jedes Übertragsbit am Ende wird verworfen. Sie werden also wie folgt hinzugefügt:
0001
ist 1, was das erwartete Ergebnis von "2 + (- 1)" ist.Bei Ihrer "intuitiven" Methode ist das Hinzufügen jedoch komplizierter:
Welches ist -3, richtig? Einfaches Hinzufügen funktioniert in diesem Fall nicht. Sie müssen beachten, dass eine der Zahlen negativ ist, und in diesem Fall einen anderen Algorithmus verwenden.
Bei dieser "intuitiven" Speichermethode ist die Subtraktion eine andere Operation als die Addition und erfordert zusätzliche Überprüfungen der Zahlen, bevor sie hinzugefügt werden können. Da die grundlegendsten Operationen (Addition, Subtraktion usw.) so schnell wie möglich sein sollen, müssen Sie Zahlen so speichern, dass Sie die einfachsten möglichen Algorithmen verwenden können.
Zusätzlich gibt es bei der "intuitiven" Speichermethode zwei Nullen:
Die intuitiv die gleiche Nummer haben, aber beim Speichern zwei unterschiedliche Werte haben. Jede Anwendung muss zusätzliche Schritte ausführen, um sicherzustellen, dass Werte ungleich Null auch keine negative Null sind.
Es gibt einen weiteren Bonus beim Speichern von Ints auf diese Weise, und dann müssen Sie die Breite des Registers erweitern, in dem der Wert gespeichert wird. Mit dem Zweierkomplement ist das Speichern einer 4-Bit-Zahl in einem 8-Bit-Register eine Frage der Wiederholung höchstwertiges Bit:
Es geht nur darum, das Vorzeichen des kleineren Wortes zu betrachten und es zu wiederholen, bis es die Breite des größeren Wortes auffüllt.
Bei Ihrer Methode müssten Sie das vorhandene Bit löschen. Dies ist eine zusätzliche Operation zusätzlich zum Auffüllen:
Sie müssen diese zusätzlichen 4 Bits in beiden Fällen noch setzen, aber im "intuitiven" Fall müssen Sie auch das 5. Bit löschen. Dies ist ein winziger zusätzlicher Schritt in einer der grundlegendsten und häufigsten Operationen, die in jeder Anwendung vorhanden sind.
quelle
how we arrived at 2s compliment the first place.
cs.cornell.edu/~tomf/notes/cps104/twoscomp.html1
angibt-8
, und die restlichen drei1
s zeigen4
,2
und1
jeweils so-8+4+2+1 = -1
.Wikipedia sagt alles:
Mit anderen Worten, das Hinzufügen ist das gleiche, ob die Zahl negativ ist oder nicht.
quelle
Auch wenn diese Frage alt ist, lassen Sie mich meine 2 Cent eingeben.
Bevor ich dies erkläre, kehren wir zu den Grundlagen zurück. 2'-Komplement ist 1's Komplement + 1. Was ist nun die Ergänzung von 1 und welche Bedeutung hat sie zusätzlich?
Die Summe einer beliebigen n-Bit-Zahl und ihres 1-Komplements ergibt die höchstmögliche Zahl, die durch diese n-Bits dargestellt werden kann. Beispiel:
Was passiert nun, wenn wir versuchen, dem Ergebnis 1 weitere hinzuzufügen? Dies führt zu einem Überlauf.
Das Ergebnis
1 0000
ist 0 (da wir mit 4-Bit-Zahlen arbeiten (die 1 links ist ein Überlauf)So ,
Jemand entschied sich dann, 1s Komplement + 1 als 2'-Komplement zu bezeichnen. Die obige Aussage lautet also: Jede n'bit-Zahl + das Zweierkomplement = 0, was das Zweierkomplement einer Zahl = - (dieser Zahl) bedeutet.
All dies wirft eine weitere Frage auf, warum wir nur das (n-1) der n Bits verwenden können, um eine positive Zahl darzustellen, und warum das am weitesten links stehende n-te Bit ein Vorzeichen darstellt (0 am ganz linken Bit bedeutet + ve Zahl und 1 bedeutet -ve Nummer). zB warum verwenden wir nur die ersten 31 Bits eines int in Java, um eine positive Zahl darzustellen, wenn das 32. Bit 1 ist, seine a -ve Zahl.
1 0000 (Ergebnis ist Null, wobei der Übertrag 1 überläuft)
Somit funktioniert das System von (n + 2'-Komplement von n) = 0 immer noch. Die einzige Mehrdeutigkeit ist hier, dass das 2er-Komplement von 12 0100 ist, was mehrdeutig auch +8 darstellt, außer -12 im 2s-Komplementsystem.
Dieses Problem wird gelöst, wenn positive Zahlen immer eine 0 ganz links haben. In diesem Fall hat das Komplement ihrer 2 immer eine 1 im Bit ganz links, und wir haben nicht die Mehrdeutigkeit des gleichen Satzes von Bits, die die Komplementzahl einer 2 sowie eine + ve-Zahl darstellen.
quelle
Das Zweierkomplement ermöglicht das normale Addieren und Subtrahieren (wie Sie es für vorzeichenlose Zahlen gewickelt haben). Es verhindert auch -0 (eine separate Methode zur Darstellung von 0, die mit der normalen bitweisen Methode zum Vergleichen von Zahlen nicht gleich 0 wäre).
quelle
Dies soll Summen und Zahlenunterschiede vereinfachen. Eine Summe aus einer negativen und einer positiven Zahl, die in den Zweierkomplementen kodifiziert ist, entspricht der normalen Summierung.
quelle
Die übliche Implementierung der Operation ist "Flip the Bits and Add 1", aber es gibt eine andere Art der Definition, die wahrscheinlich die Begründung klarer macht. Das Komplement von 2 ist die Form, die Sie erhalten, wenn Sie die übliche vorzeichenlose Darstellung verwenden, bei der jedes Bit die nächste Potenz von 2 steuert und nur den höchstwertigen Term negativ macht.
Nehmen eines 8-Bit-Werts a 7 a 6 a 5 a 4 a 3 a 2 a 1 a 0
Die übliche vorzeichenlose binäre Interpretation lautet:
2 7 * a 7 + 2 6 * a 6 + 2 5 * a 5 + 2 4 * a 4 + 2 3 * a 3 + 2 2 * a 2 + 2 1 * a 1 + 2 0 * a 0
11111111 = 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 255
Die Komplementinterpretation der beiden lautet:
-2 7 * a 7 + 2 6 * a 6 + 2 5 * a 5 + 2 4 * a 4 + 2 3 * a 3 + 2 2 * a 2 + 2 1 * a 1 + 2 0 * a 0
11111111 = -128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = -1
Keines der anderen Bits ändert überhaupt seine Bedeutung, und das Übertragen in eine 7 ist "Überlauf" und es wird nicht erwartet, dass es funktioniert, so dass so ziemlich alle arithmetischen Operationen ohne Modifikation funktionieren (wie andere angemerkt haben). Die Vorzeichengröße überprüft im Allgemeinen das Vorzeichenbit und verwendet eine andere Logik.
quelle
Mit dem Zweierkomplement können negative und positive Zahlen ohne spezielle Logik addiert werden.
Wenn Sie versucht haben, 1 und -1 mit Ihrer Methode
10000001 (-1)
+00000001 (1)
zu
addieren, erhalten Sie 10000010 (-2)
Stattdessen können wir durch Verwendung des Zweierkomplements hinzufügen
11111111 (-1)
+00000001 (1) erhalten Sie
00000000 (0)
Gleiches gilt für die Subtraktion.
Wenn Sie versuchen, 4 von 6 zu subtrahieren (zwei positive Zahlen), können Sie 2 zu 4 ergänzen und die beiden addieren 6 + (-4) = 6 - 4 = 2
Dies bedeutet, dass die Subtraktion und Addition sowohl positiver als auch negativer Zahlen durch dieselbe Schaltung in der CPU erfolgen kann.
quelle
Um andere Antworten zu erweitern:
In Zweierkomplement
Die Teilung erfordert einen anderen Mechanismus.
All dies ist wahr, weil das Zweierkomplement nur eine normale modulare Arithmetik ist, bei der wir einige Zahlen durch Subtrahieren des Modulos als negativ betrachten.
quelle
unsigned mul(unsigned short x, unsigned short y) { return x*y; }
[16-Bit kurz; 32-Bit int] generiert gelegentlich Code, der eine Fehlfunktion aufweist, wenn das Produkt größer als 2147483647 ist.Als ich die Antworten auf diese Frage las, stieß ich auf diesen Kommentar [bearbeitet].
Meiner Meinung nach ist die in diesem Kommentar gestellte Frage sehr interessant, und deshalb möchte ich sie zunächst umformulieren und dann eine Antwort und ein Beispiel geben.
FRAGE - Wie kann das System feststellen, wie ein oder mehrere benachbarte Bytes interpretiert werden müssen? Wie kann das System insbesondere feststellen, ob eine gegebene Folge von Bytes eine einfache Binärzahl oder eine Zweierkomplementzahl ist?
ANTWORT - Das System legt fest, wie eine Folge von Bytes durch Typen interpretiert wird. Typen definieren
BEISPIEL - Nachfolgend nehmen wir das an
char
sind 1 Byte langshort
sind 2 Bytes langint
's undfloat
' s sind 4 Bytes langBitte beachten Sie, dass diese Größen für mein System spezifisch sind. Obwohl sie ziemlich häufig sind, können sie von System zu System unterschiedlich sein. Wenn Sie neugierig sind, was sich auf Ihrem System befindet, verwenden Sie den Operator sizeof .
Zunächst definieren wir ein Array mit 4 Bytes und initialisieren alle mit der Binärzahl
10111101
, die der Hexadezimalzahl entsprichtBD
.Dann lesen wir den Array-Inhalt mit verschiedenen Typen.
unsigned char
undsigned char
unsigned short
undshort
unsigned int
,int
undfloat
Die 4 Bytes in RAM (
l_Just4Bytes[ 0..3 ]
) bleiben immer genau gleich. Das einzige, was sich ändert, ist, wie wir sie interpretieren.Wieder sagen wir dem System, wie sie durch Typen interpretiert werden sollen .
Zum Beispiel haben wir oben die folgenden Typen verwendet, um den Inhalt des
l_Just4Bytes
Arrays zu interpretierenunsigned char
: 1 Byte in einfacher Binärdateisigned char
: 1 Byte im 2er-Komplementunsigned short
: 2 Bytes in einfacher binärer Notationshort
: 2 Bytes im 2er-Komplementunsigned int
: 4 Bytes in einfacher binärer Notationint
: 4 Bytes im 2er-Komplementfloat
: 4 Bytes in IEEE 754-Notation mit einfacher Genauigkeit[BEARBEITEN] Dieser Beitrag wurde nach dem Kommentar von user4581301 bearbeitet. Vielen Dank, dass Sie sich die Zeit genommen haben, diese wenigen hilfreichen Zeilen zu löschen!
quelle
int x = -4
, und ich mache dann,printf("%d" , x)
wie es interpretiert wird. Auch was ist der Unterschied zwischenunsigned int
undsigned int
und%d
und%u
... das nervt mich schon lange. Danke.int
Typen ist dersigned
Modifikator Standard. Dies bedeutet, dassint
undsigned int
genau der gleiche Typ sind. Somit haben die beiden Definitionenint i = -4;
undsigned int i = -4;
die gleiche Bedeutung.int
ist 4 Bytes im Zweierkomplement und anunsigned int
ist 4 Bytes in einfacher binärer Notation (überprüfen Sie die tatsächliche Typgröße auf Ihrem System mit demsizeof
Operator).Sie können Professor Jerry Cain aus Stanford in der zweiten Vorlesung (die Erklärung zur Ergänzung der 2 beginnt gegen 13:00 Uhr) in der Vorlesungsreihe mit dem Titel Programmierparadigmen, die auf dem YouTube-Kanal von Standford zu sehen ist, in der zweiten Vorlesung (die Erklärung zur Ergänzung der beiden beginnt) ansehen. Hier ist der Link zur Vorlesungsreihe: http://www.youtube.com/view_play_list?p=9D558D49CA734A02 .
quelle
Das Zweierkomplement wird verwendet, weil es einfacher in Schaltkreisen zu implementieren ist und auch keine negative Null zulässt.
Wenn es x Bits gibt, reicht das Zweierkomplement von + (2 ^ x / 2 + 1) bis - (2 ^ x / 2). Das Komplement eines Menschen läuft von + (2 ^ x / 2) bis - (2 ^ x / 2), erlaubt jedoch eine negative Null (0000 ist gleich 1000 im Komplementsystem eines 4-Bit-1).
quelle
Nun, Ihre Absicht ist es nicht wirklich, alle Bits Ihrer Binärzahl umzukehren. Es ist eigentlich ein glücklicher Zufall, dass das Subtrahieren von 1 von 1 zu 0 und das Subtrahieren von 0 von 1 zu 1 führt. Das Umdrehen von Bits führt diese Subtraktion also effektiv aus.
Aber warum finden Sie den Unterschied jeder Ziffer von 1? Nun, das bist du nicht. Ihre eigentliche Absicht ist es, die Differenz der angegebenen Binärzahl von einer anderen Binärzahl zu berechnen, die die gleiche Anzahl von Ziffern hat, aber nur Einsen enthält. Wenn Ihre Nummer beispielsweise 10110001 lautet und Sie alle diese Bits umdrehen, berechnen Sie effektiv (11111111 - 10110001).
Dies erklärt den ersten Schritt bei der Berechnung von Two's Complement. Lassen Sie uns nun den zweiten Schritt - Hinzufügen von 1 - ebenfalls in das Bild aufnehmen.
Addiere 1 zu der obigen binären Gleichung:
11111111 - 10110001 + 1
Was bekommst du? Dies:
100000000 - 10110001
Dies ist die endgültige Gleichung. Und indem Sie diese beiden Schritte ausführen, versuchen Sie, diesen endgültigen Unterschied zu finden: Die Binärzahl wird von einer anderen Binärzahl mit einer zusätzlichen Ziffer subtrahiert und enthält Nullen, außer an der Bitposition mit der höchsten Bedeutung.
Aber warum sehnen wir uns wirklich nach diesem Unterschied? Nun, von hier an wäre es wohl besser, wenn Sie den Wikipedia-Artikel lesen .
quelle
Wir führen nur Additionsoperationen sowohl für Addition als auch für Subtraktion durch. Wir fügen den zweiten Operanden zum Hinzufügen zum ersten Operanden hinzu. Zur Subtraktion addieren wir das Zweierkomplement des zweiten Operanden zum ersten Operanden.
Bei der 2er-Komplementdarstellung benötigen wir keine separaten digitalen Komponenten für die Subtraktion - es werden nur Addierer und Komplementäre verwendet.
quelle
Es ist anzumerken, dass bei einigen frühen Addiermaschinen vor den Tagen digitaler Computer die Subtraktion durchgeführt wird, indem der Bediener Werte mit einem andersfarbigen Satz von Legenden auf jedem Schlüssel eingibt (so dass jeder Schlüssel neun minus der zu zahlenden Zahl eingibt subtrahiert), und drücken Sie eine spezielle Taste, um einen Übertrag in eine Berechnung anzunehmen. Um auf einer sechsstelligen Maschine 1234 von einem Wert zu subtrahieren, drückte der Bediener Tasten, die normalerweise "998.765" anzeigen, und drückte eine Taste, um diesen Wert plus eins zur laufenden Berechnung hinzuzufügen. Die Zweierkomplementarithmetik ist einfach das binäre Äquivalent der früheren "Zehnerkomplement" -Arithmetik.
quelle
Der Vorteil der Durchführung einer Subtraktion durch das Komplementverfahren besteht in der Verringerung der Hardwarekomplexität.
Die unterschiedlichen digitalen Schaltungen für Addition und Subtraktion sind nicht erforderlich. Sowohl Addition als auch Subtraktion werden nur durch Addierer durchgeführt.
quelle
Ein Hauptvorteil der Zweierkomplementdarstellung, der hier noch nicht erwähnt wurde, besteht darin, dass die unteren Bits einer Zweikomplementsumme, -differenz oder -produkt nur von den entsprechenden Bits der Operanden abhängen . Der Grund dafür, dass der vorzeichenbehaftete 8-Bit-Wert für -1 darin
11111111
besteht, dass eine beliebige Ganzzahl mit den niedrigsten 8 Bits00000001
von jeder anderen Ganzzahl mit den niedrigsten 8 Bits subtrahiert wird0000000
eine Ganzzahl ergibt, deren niedrigste 8 Bits sind11111111
. Mathematisch gesehen wäre der Wert -1 eine unendliche Folge von Einsen, aber alle Werte innerhalb des Bereichs eines bestimmten Ganzzahltyps sind entweder alle Einsen oder alle Nullen nach einem bestimmten Punkt, so dass es für Computer praktisch ist, die Vorzeichen zu erweitern höchstwertiges Bit einer Zahl, als ob es eine unendliche Zahl von Einsen oder Nullen darstellt.Das Zweierkomplement ist fast die einzige Darstellung mit vorzeichenbehafteten Zahlen, die bei Typen, die größer als die natürliche Wortgröße einer Binärmaschine sind, gut funktioniert, da Code beim Durchführen von Addition oder Subtraktion den niedrigsten Block jedes Operanden abrufen und den niedrigsten Block von berechnen kann das Ergebnis und speichern Sie das, laden Sie dann den nächsten Block jedes Operanden, berechnen Sie den nächsten Block des Ergebnisses und speichern Sie das usw. Somit kann sogar ein Prozessor, der alle Additionen und Subtraktionen benötigt, ein einzelnes 8-Bit-Register durchlaufen kann mit 32-Bit-Vorzeichen relativ effizient umgehen (langsamer als mit einem 32-Bit-Register, aber immer noch funktionsfähig).
Wenn Sie andere vom C-Standard zugelassene vorzeichenbehaftete Darstellungen verwenden, kann jedes Bit des Ergebnisses möglicherweise von einem beliebigen Bit der Operanden beeinflusst werden. Daher muss entweder ein ganzer Wert gleichzeitig in den Registern gespeichert werden, oder es müssen Berechnungen mit einem zusätzlichen Wert durchgeführt werden Schritt, der zumindest in einigen Fällen das Lesen, Ändern und Umschreiben jedes Teils des Ergebnisses erfordern würde.
quelle
Es gibt verschiedene Arten von Darstellungen:
- Darstellung nicht signierter Zahlen, die nur positive Zahlen darstellt
- Vorzeichenbehaftete Darstellung, die sowohl positive als auch negative Zahlen darstellt. In der vorzeichenbehafteten Zahlendarstellung repräsentiert das MSB-Bit das Vorzeichenbit und die Ruhebits die Zahl. Wenn MSB 0 ist, bedeutet dies, dass die Zahl positiv ist, und wenn MSB 1 ist, bedeutet dies, dass die Zahl negativ ist.
Problem bei der Darstellung vorzeichenbehafteter Zahlen ist, dass es zwei Werte für 0 gibt.
Das Problem bei der Komplementdarstellung ist, dass es zwei Werte für 0 gibt.
Wenn wir jedoch die Zweierkomplementdarstellung verwenden, gibt es nur einen Wert für 0, weshalb wir negative Zahlen in der Zweierkomplementform darstellen.
Quelle: Warum negative Zahlen in Zweierkomplementformbytes von Gigabyte gespeichert werden
quelle
Eine zufriedenstellende Antwort darauf, warum das Komplement von Two2 eher zur Darstellung negativer Zahlen als des Komplementsystems von One verwendet wird, besteht darin, dass das Komplementsystem von Two das Problem der Mehrfachdarstellung von 0 und die Notwendigkeit des End-Around-Carry löst, die im Komplementsystem des Einen zur Negativdarstellung bestehen Zahlen.
Weitere Informationen finden Sie unter https://en.wikipedia.org/wiki/Signed_number_representations
Für End-around-Carry besuchen Sie https://en.wikipedia.org/wiki/End-around_carry
quelle