Wikipedia · einfach zusammengefasst · Stand
Zweierkomplement
Das Zweierkomplement kann als eine Interpretationsweise formatierter binärer Bitfolgen gesehen werden, welche für negative Werte von Integer-Variablen auftritt, …
Inhalt5 Abschnitte
Grundidee und Wertebereich
Das Zweierkomplement ist eine Darstellungsweise für positive und negative Integer-Zahlen im Dualsystem, die kein zusätzliches Plus- oder Minuszeichen benötigt. Es ist besonders in der Digitaltechnik und in Computern wichtig, weil sich die Subtraktion auf eine Addition zurückführen lässt und dadurch mit einem Addierwerk ausgeführt werden kann.
Die Darstellung setzt eine festgelegte Bit-Länge voraus. Das höchstwertige Bit hat dabei eine besondere Bedeutung: Ist es 0, wird die Bitfolge als positive Zahl oder als 0 interpretiert; ist es 1, als negative Zahl. Eine getrennte Aufteilung in Vorzeichenbit und Betragsbits ist nicht nötig. Das vereinfacht die Verarbeitung in digitalen Schaltungen. Bei vorzeichenlosen Integer-Zahlen („unsigned integer“) tritt das Zweierkomplement nicht auf.
Für n Bits ist der Wertebereich, sofern nichts anderes vereinbart wurde, −2ⁿ⁻¹ bis 2ⁿ⁻¹−1.
Beispiele:
- 8 Bit: −128 bis +127
- 16 Bit: −32768 bis +32767
- 32 Bit: −2147483648 bis +2147483647
- 64 Bit: −9223372036854775808 bis +9223372036854775807
Bei 4 Bit reichen positive Zweierkomplementzahlen von 0000 = 0 bis 0111 = 7. Danach beginnen die negativen Werte: 1000 = −8, 1001 = −7, bis 1111 = −1. Anders als beim Einerkomplement gibt es keine zweite Darstellung für die Null.
Umwandlung und Interpretation
Positive Zahlen werden binär dargestellt und mit einer führenden 0 auf die festgelegte Bit-Länge gebracht. Für eine negative Zahl wird zunächst der Betrag binär dargestellt, anschließend werden alle Bits invertiert und schließlich 1 addiert.
Beispiel für −4 mit 8 Bit:
- 4₁₀ = 00000100₂
- Invertieren: 11111011
- 1 addieren: 11111011 + 00000001 = 11111100
Damit gilt: 11111100₂ = −4₁₀.
Für eine schnelle Umwandlung von Hand schreibt man von rechts aus alle Nullen und die erste Eins unverändert ab. Alle weiter links stehenden Bits werden invertiert. Diese Regel funktioniert in beide Richtungen beim Wechsel zwischen einer Zahl und ihrer Gegenzahl.
Eine weitere Interpretation weist dem höchstwertigen Bit die negative Wertigkeit −2ⁿ⁻¹ zu, während die übrigen Bits ihre üblichen positiven Wertigkeiten behalten. Bei 8 Bit sind die Wertigkeiten daher −128, 64, 32, 16, 8, 4, 2 und 1. Zum Beispiel:
- 00011010₂ = 16 + 8 + 2 = +26
- 11100110₂ = −128 + 64 + 32 + 4 + 2 = −26
Zur Umwandlung einer negativen Zweierkomplementzahl ins Dezimalsystem kann man 1 subtrahieren und anschließend alle Bits invertieren; alternativ invertiert man zuerst und addiert danach 1. Die so erhaltene positive Binärzahl wird ins Dezimalsystem umgerechnet und erhält ein Minuszeichen. Beispiel: 11111101₂ → nach der Umwandlung 00000011₂ = 3, also −3.
Direkt gilt für eine n-stellige Bitfolge aₙ₋₁aₙ₋₂…a₁a₀ die Formel:
xdezimal = −2ⁿ⁻¹ · aₙ₋₁ + 2ⁿ⁻² · aₙ₋₂ + … + 2¹ · a₁ + 2⁰ · a₀.
Formal wird eine negative Zahl x mit n Stellen durch xz = 2ⁿ − |x| dargestellt. Daher gilt xz + |x| = 2ⁿ; 2ⁿ erscheint bei der Rechnung als Übertrag in der (n+1)-sten Stelle.
Restklassen und Vorzeichenwechsel
Das Zweierkomplement kann als geschickte Auswahl von Repräsentanten in einem Restklassenring verstanden werden. Ein Rechner mit 8 Bit arbeitet modulo 256, also im Ring ℤ/256ℤ. Die Bitfolgen 0 bis 255 können als Repräsentanten verwendet werden; gleichwertig kann man die Werte −128 bis 127 zuordnen. Die Rechenoperationen selbst unterscheiden nicht zwischen positiven und negativen Zahlen.
Für −3 und −7 können beispielsweise die Repräsentanten 253 und 249 gewählt werden:
−3 ≡ 253 mod 256, −7 ≡ 249 mod 256.
Dann gilt:
−3 · −7 ≡ 253 · 249 ≡ 62997 ≡ 21 mod 256.
Die Darstellung von −3 entsteht, indem man zu −3 die Zahl 256 addiert und den Repräsentanten 253 erhält. Beim Bilden des Zweierkomplements von 3 wird 3 bitweise invertiert: 00000011 → 11111100, danach wird 1 addiert: 11111101 = 253. Damit entspricht die Bitfolge dem Wert −3.
Das bei einer Rechnung entstehende Carrybit kann dabei als −256 interpretiert werden. Im Restklassenring darf man beliebig oft 256 addieren oder subtrahieren, ohne die Kongruenzklasse zu verlassen. Eine 9-Bit-Folge 1 11111101 kann daher als −256 + 253 = −3 gelesen werden.
Der Vorzeichenwechsel folgt formal aus der bitweisen Invertierung. Für eine n-stellige Zahl xz gilt:
(2ⁿ − 1) − xz = x̄z,
wobei x̄z das bitweise Komplement ist. Modulo 2ⁿ folgt daraus:
−xz ≡ x̄z + 1 mod 2ⁿ.
Das Vorzeichen wird somit immer durch zwei Schritte gewechselt: alle Bits invertieren und 1 addieren.
Addition, Subtraktion und Überlauf
Addition und Subtraktion benötigen keine Fallunterscheidung zwischen positiven und negativen Zahlen. Eine Subtraktion wird als Addition der Zweierkomplementdarstellung des Subtrahenden ausgeführt. Ein zusätzlicher Übertrag über die festgelegte Bit-Länge wird verworfen.
Beispiele mit 8 Bit:
- −4 + 3: 11111100 + 00000011 = 11111111 = −1
- +4 + (−4): 00000100 + 11111100 = 100000000; die vorderste, neunte Stelle wird ignoriert, sodass 00000000 = 0 bleibt.
- +4 − 3: 00000100 + 11111101 = 100000001; nach Weglassen der neunten Stelle bleibt 00000001 = +1.
- −4 − 3: 11111100 + 11111101 = 111111001; nach Weglassen der neunten Stelle bleibt 11111001 = −7.
Das Verfahren funktioniert, solange das Ergebnis im gültigen n-stelligen Bereich liegt. Bei 8 Bit ist das der Bereich −128 bis +127. Wird er verlassen, tritt ein Überlauf auf. Überlauf und Übertrag sind nicht dasselbe. Beispielsweise ergibt 50 + 80 = 130; 130 liegt außerhalb des 8-Bit-Zweierkomplementbereichs, obwohl die Bitfolge noch in einer 8-Bit-Variable gespeichert werden kann. Das gesetzte höchstwertige Bit lässt das Ergebnis dann fälschlich negativ erscheinen. Manche Mikroprozessoren, etwa der 6502, melden dies mit dem Overflow-Bit O.
Zur sicheren Addition werden die Operanden vor der Rechnung vorzeichenerweitert: Das oberste Bit wird dupliziert und die Bit-Länge dadurch vergrößert. Bei 8 Bit wird die achte Stelle auf eine neunte Stelle kopiert. Unterscheiden sich danach die beiden höchstwertigen Stellen des Ergebnisses, liegt ein Überlauf vor. Stimmen sie überein, kann das Ergebnis wieder auf die ursprüngliche Bit-Länge verkürzt werden. So können etwa +4 + (−3) = +1 und −4 + (−3) = −7 korrekt auf 8 Bit reduziert werden, während +4 + 127 = +131 und −4 − 127 = −131 nicht in 8 Bit darstellbar sind.
Multiplikation, Festkommazahlen und andere Basen
Auch Multiplikationen lassen sich in Zweierkomplementdarstellung mit Multiplizierwerken ausführen. Bei einem Parallelmultiplizierer werden die Faktoren auf die Produktlänge vorzeichenerweitert, die Teilprodukte verschoben und addiert. Für Faktoren mit n beziehungsweise m Bit ist das Produkt n+m Bit lang. Weitere Verfahren beruhen auf dem Booth-Algorithmus oder dem Bit-Pair-Verfahren.
Beispiel: (−7) · (−3) = +21. Die 4-Bit-Darstellungen 1001 und 1101 werden auf 8 Bit erweitert und die verschobenen Teilprodukte addiert. Durch die Vorzeichenerweiterung kann die Berechnung verkürzt werden: Eine bestimmte letzte Zeile wird subtrahiert, ohne dass eine besondere Vorzeichenkorrektur des Produkts erforderlich ist. Das Verfahren funktioniert auch bei unterschiedlichen Vorzeichen, etwa (−7) · 3 = −21.
Das Zweierkomplement gilt auch für Festkommazahlen. Dabei wird die Position des Kommapunkts fest vereinbart, aber nicht mitgespeichert. Bei ganzen Zahlen liegt der Kommapunkt rechts hinter der letzten Stelle; dann ist k = 0 und nach dem Invertieren wird 2⁰ = 1 addiert. Liegt der Kommapunkt zwei Stellen weiter links und gibt es zwei Nachkommastellen, ist k = −2; dann wird 2⁻² = 0,25 addiert.
Eine fünf Bit lange Zahl mit drei Vorkommastellen und zwei Nachkommastellen kann Werte von −4 bis +3,75 in Schritten von 0,25 darstellen. 2,25 entspricht 010,01₂. Invertieren und Addieren von 0,25 ergibt 101,11₂ = −2,25.
Das Prinzip lässt sich auf jede Basis b verallgemeinern. Bei n Stellen werden zunächst die Werte 0 bis bⁿ−1 dargestellt. Eine größere Zahl x kann als Darstellung der negativen Zahl x−bⁿ aufgefasst werden. Zur Negation ersetzt man jede Ziffer z durch (b−1)−z und addiert 1. Bei Basis 5 und drei Stellen wird 1 als 001 dargestellt, zu 443 invertiert und nach Addition von 1 als 444 geschrieben; damit steht 444 für −1. Wird 222 als größte positive Zahl festgelegt, reicht der Bereich von −62 bis +62 im Dezimalsystem. Für Basis 10 und zwei Stellen gilt beispielsweise 99 = −01 und 50 = −50. Dieses zusätzliche Gegenstück zur 0 tritt bei jeder geraden Basis auf. Mit unendlich vielen Stellen erhält man die Möglichkeit, p-adische ganze Zahlen darzustellen.
