Wikipedia · einfach zusammengefasst · Stand
Einerkomplement
Das Einerkomplement, auch (b−1)-Komplement, ist eine arithmetische Operation, die meist im Dualsystem angewendet wird. Dabei werden alle Ziffern bzw.
Inhalt4 Abschnitte
Grundidee und Anwendungen
Das Einerkomplement, auch (b−1)-Komplement, ist eine arithmetische Operation, die meist im Dualsystem verwendet wird. Bei einer Binärzahl werden alle Bits invertiert: Aus 0 wird 1 und aus 1 wird 0. Jede Ziffer und die entsprechende Ziffer des Einerkomplements ergänzen sich dadurch zu 1.
Ist z eine n-stellige Binärzahl, lautet ihr Einerkomplement (2^n−1)−z. Diese Subtraktion kommt ohne Überträge aus. Die Operation heißt auch bitweise Negation; in verschiedenen Programmiersprachen wird sie mit der Tilde ~ bezeichnet. Dabei wird die Zahl als Bitkette aufgefasst.
Eine direkte Anwendung ist die gezielte Veränderung einzelner Bits. Sollen in einer Bitkette Zahl alle Bits gelöscht werden, die in der Bitkette Maske gesetzt sind, wird Zahl mit dem Einerkomplement von Maske bitweise UND-verknüpft: Zahl &= ~Maske;.
Das Einerkomplement kann außerdem zur Darstellung negativer Ganzzahlen dienen. Gegenüber der heute üblichen Zweierkomplementdarstellung bietet es Vorteile nur bei der ohnehin meist langsamen Division, bei der Multiplikation mit doppelt langem Ergebnis sowie bei der Bildung einfacher Prüfsummen.
Einerkomplementdarstellung negativer Zahlen
Bei binären Kodierungen vorzeichenbehafteter Ganzzahlen wird eine konstante Anzahl n von Stellen verwendet. Das höchstwertige Bit (most significant bit) gibt das Vorzeichen an: 0 steht für Plus, 1 für Minus. Positive Zahlen werden genauso wie vorzeichenlose Zahlen dargestellt; kleinere Zahlen ergänzt man links mit Nullen.
Ist das höchstwertige Bit 1, ist die Zahl in der Einerkomplementdarstellung negativ. Ihr Betrag entsteht durch Komplementbildung. Beispielsweise ist 1010 wegen der führenden 1 negativ. Das Einerkomplement lautet ~1010 = 0101, also beträgt der Betrag 5.
Daraus folgen zwei wichtige Eigenschaften: Die Zahl 0 besitzt zwei Darstellungen, +0 = 0000 und −0 = 1111. Außerdem reichen positive und negative Zahlen symmetrisch bis zum gleichen Betrag. Bei einer Wortbreite von n = 4 Bit reicht der Bereich von −7 bis +7; die positive 7 lautet 0111.
Allgemein beträgt der größte darstellbare Betrag 2^(n−1)−1. Für 8 Bit ergibt sich der Maximalbetrag 127, für 16 Bit 32767. Zum Vergleich zeigt die Belegung eines Nibbles (4 Bit), dass 1000 im Einerkomplement −0 bedeutet, während 1001 bis 1110 die Werte −1 bis −6 und 1111 den Wert −7 darstellen. In der Zweierkomplementdarstellung entsprechen dieselben Bitmuster dagegen anderen Werten, etwa 1000 = −8 und 1111 = −1.
Addition, Subtraktion und Probleme
Die einfachste Rechenoperation in der Einerkomplementdarstellung ist die arithmetische Negation, also der unäre --Operator. Man bildet lediglich das bitweise Komplement. Dadurch kann die Subtraktion auf eine Addition zurückgeführt werden: 3 − 4 = 3 + (−4).
Für 3 − 4 ergibt ein für vorzeichenlose Zahlen konstruiertes Addierwerk direkt das richtige Ergebnis:
1011 (−4)
- 0011 (+3) Überträge 0011 = 1110 (−1)
Problematisch ist eine Operation, bei der die Null durchschritten wird. Bei −4 + 6 = +2 entsteht zunächst:
1011
- 0110 Überträge 1110 = 0001 (Zwischenergebnis)
0001 steht jedoch für +1 und nicht für +2. Deshalb muss der am weitesten links stehende Übertrag ausgewertet werden. Ist er 1, wird er noch zum Zwischenergebnis addiert:
0001 (Zwischenergebnis) + 1 (Übertrag) = 0010.
Im ersten Beispiel war dieser Übertrag 0; deshalb war das Zwischenergebnis bereits korrekt.
Ein zweites Problem ist die Redundanz der Null. Wegen +0 und −0 wird bei einer begrenzten Bitanzahl ein Datenwort nicht für eine zusätzliche Zahl genutzt. Der darstellbare Zahlenraum verringert sich um 1, während jede andere Zahl eindeutig bleibt. Mit 4 Bit gibt es 2^4 = 16 Bitkombinationen, aber nur 15 verschiedene Zahlen, nämlich −7 bis 7. Beide Probleme vermeidet die Zweierkomplementdarstellung.
Das Hinzuaddieren des Übertrags ist bei einfachen Prüfsummen nützlich, weil es die Empfindlichkeit gegenüber mehrfachen Bitfehlern verbessert. Eine Prüfsumme mit Überträge ignorierender Modulo-Arithmetik würde bei häufig fehlerhaftem höchstwertigem Bit, etwa wenn es konstant 0 ist, mit 50 % Wahrscheinlichkeit keinen Übertragungsfehler anzeigen. TCP verwendet deshalb eine Prüfsumme in Einerkomplement-Arithmetik. RFC 1071 beschreibt eine effiziente Berechnung auf Hardware ohne Einerkomplement-Rechenwerk.
Verallgemeinerung auf andere Zahlensysteme
Das Prinzip lässt sich auf jedes b-adische System mit dem Standardziffernvorrat {0, 1, …, b−1} übertragen. Für jede Ziffer z lautet die Komplementziffer (b−1)−z. Im Dualsystem mit b = 2 ergibt das die Invertierung von 0 und 1.
Im Dezimalsystem mit b = 10 wird jede Ziffer von 9 abgezogen. Dieses Verfahren heißt Neunerkomplement; allgemein wird auch die Bezeichnung (b−1)-Komplement verwendet. Für die dreistellige Dezimalzahl 456 lautet es:
(9−4)(9−5)(9−6) = 543.
Damit gilt: 543 = 999 − 456. Ist x eine n-stellige Dezimalzahl, lautet ihr Neunerkomplement allgemein (10^n−1)−x. Auch diese Subtraktion kommt ohne Überträge aus.
