Warum sind 11, 111, 1111, ... äquivalent zu -1 im Zweierkomplement? [Duplikat]

In einer vorzeichenlosen binären Darstellung können nur positive Zahlen dargestellt werden, und das Gewicht jedes Bits einschließlich des höchstwertigen Bits ist eine Zweierpotenz.

Also mit einer Wortgröße von 8 (Byte),

00000000 => 0
01111111 => 127
10000000 => 128
11111111 => 255

Das Zweierkomplement, das für die binäre Notation mit Vorzeichen verwendet wird, codiert sowohl positive als auch negative Zahlen in einer binären Zahlendarstellung. Das Gewicht jedes Bits ist eine Zweierpotenz, mit Ausnahme des höchstwertigen Bits , dessen Gewicht das Negative der entsprechenden Zweierpotenz ist.

00000000 => 0
01111111 => 127
10000000 => -128    (in unsigned notation, this bit was 128, now its -128)
11111111 => -1

Für eine gegebene Wortgröße N stellen alle Einsen im Zweierkomplement -1 dar. Wenn die Wortgröße also nur zwei Bits beträgt, ist 11 -1. Aber wenn die Wortgröße 8 Bit (ein Byte) ist, dann ist 11 einfach 3 und 11111111 ist -1.

Das liegt daran, dass das Zweierkomplement einer n-Bit-Zahl als Komplement zu 2 definiert ist$^{N}$; dh es ist das Ergebnis der Subtraktion der Zahl von 2$^{N}$, was binär eine Eins gefolgt von N Nullen ist.

Wenn also N = 2 (erstes Beispiel), also 2$^{2}$=4,

 100
  -1
 011

Abschneiden auf zwei Bits ergibt 11. ( -2 + 1 = -1)

Für N = 8 (erstes Beispiel), also 2$^{8}$=256,

 100000000
        -1
 011111111

Abschneiden auf acht Bit ergibt 11111111. ( -128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = -1)

Im Zweierkomplement ist das MSb als -(2 ⁿ ) definiert, wobei n die Bitposition des MSb ist. Aufgrund der Funktionsweise von Zahlen addieren sich alle Bits außer dem MSb zu (2 ⁿ )-1. Das Addieren dieser ergibt -1.

Dies ist eine nicht mathematische Erklärung, nur eine intuitive.

Frage dich, wie oft du 1 addieren musst, bis du 0 erreichst.

In all Ihren Beispielen ist die Antwort auf diese Frage 1. Und weil das auch für -1 gilt, sind diese Zahlen gleich -1.

Eine andere Möglichkeit, dies zu sehen (was als Erweiterung der beiden vorherigen Antworten oder als Abzocke meiner eigenen Antwort auf eine ähnliche Frage angesehen werden kann ), ist folgende: Für jedes n werden die n-Bit-Ganzzahlen ohne Vorzeichen (n-Bit-Wörter, die ein darstellen Intervall der natürlichen Zahlen beginnend bei 0) bilden eine zyklische Struktur mit 2 ⁿ Gliedern – wegen Überlauf ist der Nachfolger von 111...1 (was 2 ⁿ -1 darstellt) 000...0 (was 0 darstellt); Anstatt wie die Naturwörter in einer Reihe angeordnet zu sein, sind die n-Bit-Wörter in einem Kreis angeordnet. Diese Struktur ist als zyklische Gruppe Z _{2 ⁿ} bekannt .

Nun stellt sich die Frage: Wie können wir dieselbe zyklische Struktur verwenden, um ein Intervall ganzer Zahlen darzustellen, das sowohl negative als auch positive Zahlen enthält? Eine mögliche Antwort wäre, das Ganze nach links zu „verschieben“ – 000...0 würde die kleinste Zahl im Intervall darstellen, nämlich -2 ⁿ , und 111...1 würde die größte Zahl darstellen, nämlich 2 ⁿ - 1; 0 würde durch 100...0 irgendwo in der Mitte dargestellt werden. Das könnte tatsächlich funktionieren, aber die Implementierung der arithmetischen Logik würde sehr hässlich werden. :)

Stattdessen nutzen wir die zyklische Struktur. Wir lassen die Wörter 000 ... 0 bis 011 ... 1, die die nicht negative Seite unseres Intervalls darstellen, nämlich 0 bis 2 ⁿ -1, und "verschieben" die Wörter 100 ... 0 bis 111 ... 1 auf die negative Seite, was -2 ⁿ bis -1 darstellt. Das geht gut: Der Nachfolger von 111...1 ist tatsächlich 000...0 (also -1+1=0). Wir können jetzt die gesamte Additionslogik gegenüber vorzeichenloser Arithmetik unverändert lassen, und auch andere Operationen sind einfach anzupassen.

Diese Art von Frage wurde schon früher beantwortet, aber es sieht so aus, als ob diese spezielle Formulierung der Frage in vielen Suchergebnissen auftaucht, also werde ich meine Antwort von hier aus erneut posten .

Es könnte einfacher sein, dies in Dezimalzahlen zu verstehen. Stellen Sie sich vor, wir rechnen mit dreistelligen Zahlen zur Basis 10: 445, 900, 132, 042, 007 usw. Wir können die Zahlen addieren, aber das Ergebnis wird immer auf drei Ziffern gekürzt. Hier ist ein Beispiel:

$900 + 132 = 1032 \to 032$

Schauen Sie sich nun an, was passiert, wenn wir 999 zu einer Zahl addieren:

$042 + 999 = 1041 \to 041$

$041 + 999 = 1040 \to 040$

$040 + 999 = 1039 \to 039$

Solange wir die vierte Ziffer weglassen, funktioniert das Addieren von 999 (der größtmöglichen dreistelligen Zahl) genauso wie das Subtrahieren von 1!

Binär funktioniert genauso. Bei 4-Bit-Zahlen funktioniert das Addieren der größtmöglichen 4-Bit-Zahl genauso wie das Subtrahieren von 1. Auch dies liegt daran, dass wir den Übertrag vom High-Bit weglassen.

$0110 + 1111 = 10101 \to 0101$

$0101 + 1111 = 10100 \to 0100$

$0100 + 1111 = 10011 \to 0011$

$0011 + 1111 = 10010 \to 0010$

Dies wird Zweierkomplement-Arithmetik genannt . Mit diesem System können Sie das "Negative" jeder n-Bit-Binärzahl berechnen, indem Sie es davon subtrahieren$2^n$. Für Vier-Bit-Zahlen funktioniert es wie folgt:

$-1 = 2^4 - 1 = 10000 - 0001 = 1111$

$-5 = 2^4 - 5 = 10000 - 0101 = 1011$

Das Addieren von 1011 zu einer Vier-Bit-Zahl ist also genauso wie das Subtrahieren von 5, solange Sie den letzten Übertrag weglassen.

Es gibt einen schnelleren und gebräuchlicheren Weg, das Zweierkomplement zu berechnen – alle Bits invertieren und dann eins addieren. Auf diese Weise können Sie mithilfe von Inversion und Addition ein 4-Bit-Negativ berechnen, anstatt eine 5-Bit-Subtraktion zu benötigen. So berechnen Sie -1 und -5 mit dieser Methode:

$-1 = \lnot 0001 + 1 = 1110 + 1 = 1111$

$-5 = \lnot 0101 + 1 = 1010 + 1 = 1011$

Mehrere Antworten spielen auf modulare Arithmetik an , ohne sie tatsächlich zu diskutieren. Ich glaube, das ist eine wertvolle Perspektive und macht das Zweierkomplement viel einfacher zu verstehen.

Sowohl vorzeichenlose als auch Zweierkomplement-Arithmetik auf n -Bit-Zahlen können natürlich als Operationen modulo 2 ⁿ betrachtet werden .

Modulararithmetik

Für diejenigen, die mit modularer Arithmetik nicht vertraut sind, es ist ein Zahlensystem, bei dem addiert oder subtrahiert wird$m$ändert den Wert einer Zahl nicht. Dies bedeutet, dass das System "kreisförmig" ist und einmal durchlaufen wird$m$Schritte landest du wieder da, wo du angefangen hast.

Nehmen wir ein Beispiel. Wenn wir mit 2-Bit-Zahlen arbeiten, nehmen wir$m=2^2 = 4$. Wir sagen, wir arbeiten "modulo 4". In diesem System ändert das Addieren oder Subtrahieren von 4 den Wert einer Zahl nicht.

Das bedeutet 5 = 1, 6 = 2 und so weiter. Tatsächlich haben wir:

... = -8 = -4 = 0 = 4 = 8 = 12 = ...
... = -7 = -3 = 1 = 5 = 9 = 13 = ...
... = -6 = -2 = 2 = 6 = 10 = 14 = ...
... = -5 = -1 = 3 = 7 = 11 = 15 = ...

Dadurch entstehen vier "Klassen" von Zahlen: die einzigen Möglichkeiten, die im Modulo-4-Universum "existieren". Das passt, denn es gibt nur 4 Möglichkeiten, die eine 2-Bit-Zahl annehmen kann!

Abgesehen von der Division ist es genau wie gewöhnliche Arithmetik. 1 + 2 = 3, 2 + 2 = 4 (aber wir können 4 durch 0 ersetzen). Bedenken Sie, dass bei einer 2-Bit-Zahl 2 + 2 auf 0 überläuft, also ist das nicht so seltsam, wie Sie vielleicht zunächst denken!

Beachten Sie auch, dass das Hinzufügen von 1 Sie eine Zeile nach unten bringt und das Subtrahieren von 1 Sie eine Zeile nach oben bringt, es sei denn, Sie befinden sich am Rand, in diesem Fall wickeln Sie um.

(Ja, die Verwendung des =-Zeichens ist ein bisschen ein Schreibfehler, aber es ist eine schnelle Möglichkeit, den Punkt zu vermitteln.)

Vorzeichenlose Arithmetik

Bei vorzeichenloser Arithmetik wählen wir die fettgedruckte Darstellung, wenn wir Zahlen drucken oder vergleichen.

... = -8 = -4 = 0 = 4 = 8 = 12 = ... [00b]
... = -7 = -3 = 1 = 5 = 9 = 13 = ... [01b]
... = -6 = -2 = 2 = 6 = 10 = 14 = ... [10b]
... = -5 = -1 = 3 = 7 = 11 = 15 = ... [11b]

Wie Sie sehen können, ist dies nur eine bekannte vorzeichenlose Arithmetik!$2+2$wird auf 0 überlaufen (umlaufen).$0-1$wird auf 3 überlaufen.

Zweierkomplement-Arithmetik

Bei der Zweierkomplement-Arithmetik wählen wir diese fettgedruckte Darstellung immer dann, wenn wir Zahlen drucken oder vergleichen.

... = -8 = -4 = 0 = 4 = 8 = 12 = ... [00b]
... = -7 = -3 = 1 = 5 = 9 = 13 = ... [01b]
... = -6 = -2 = 2 = 6 = 10 = 14 = ... [10b]
... = -5 = -1 = 3 = 7 = 11 = 15 = ... [11b]

Beachten Sie, dass wir zur negativen Darstellung wechseln, wenn das äußerst linke Bit der Zahl eine 1 ist, was genau auf halber Höhe auftritt.

Um nun zu veranschaulichen, warum das Zweierkomplement 11111111b = -1 ist, beachten Sie, dass die All-1s-Zahl einen "vorzeichenlosen" Wert hat$2^n - 1$(Beweis siehe unten), aber in der Zweierkomplementschreibweise müssen wir subtrahieren$2^n$weil das Vorzeichenbit gesetzt ist, was ergibt$-1$.

Vielleicht ist es einfacher zu sehen, dass das Subtrahieren von 1 von 0 (obere Reihe) einen Umlauf in die untere Reihe bewirkt und die untere Reihe binär nur 1 ist, also die Darstellung von -1 ist.

Anhang

Dieser Beweis ist eigentlich ganz einfach.

Theorem: Eine n -Bit-Binärzahl, die nur aus Einsen besteht, hat einen Wert$v = 2^n - 1$.

Beweis: Durch Addition der Stellenwerte aller Bits erhalten wir:$v = 2^{n-1} + 2^{n-2} + \ldots + 2^{1} + 2^0$.

Beachten Sie, dass:

$2v-v = (2^{n} + 2^{n-1} + \ldots + 2^{2} + 2^1) - (2^{n-1} + 2^{n-2} + \ldots + 2^{1} + 2^0)$.

Stornieren, bekommen wir$v = 2^n-1$, und wir sind fertig!

Um herauszufinden, was das Minus einer Zahl in zwei ist, ergänzen Sie "invertieren und eins addieren". -1 bedeutet also, den Wert 0000 ... 000001 umzukehren, was 11111 ... 11110 ergibt, dann eins hinzuzufügen, was 1111 ... 1111 ergibt. also per Definition zwei oder mehr Bitzahlen ist der Wert von -1 alle Einsen.