Einerkomplement

Das Einerkomplement, auch (B-1)-Komplement, ist eine arithmetische Operation, die meist im Dualsystem angewendet wird. Dabei werden alle Ziffern bzw. Bits einer Dualzahl invertiert, das heißt: Aus 0 wird 1 und umgekehrt. Das hat zur Folge, dass jede Ziffer der Dualzahl und ihre korrespondierende Ziffer des Einerkomplements sich „zu 1 ergänzen“, was der Operation ihren Namen gibt. Die Operation wird auch als bitweise Negation bezeichnet und der Operator in verschiedenen Programmiersprachen als Tilde ~ notiert.

Prinzipiell werden Zahlen im Register eines Computers als 0 und 1 dargestellt. Das Einerkomplement ist eine von mehreren bekannten Möglichkeiten, diesen gespeicherten Wert als Dezimalzahl zu interpretieren und in Rechenoperationen zu verarbeiten.

Eine Anwendung des Einerkomplements ist die gleichzeitige Manipulation einzelner Bits in einem Datenwort. Will man zum Beispiel im Wort Zustand alle Bits löschen, die im Wort Maske gesetzt sind, so muss man Zustand mit dem Einerkomplement von Maske bitweise und-verknüpfen, in C-Syntax Zustand &= ~Maske;

Eine andere Anwendung ist die Einerkomplementdarstellung, ein Verfahren zur binären Darstellung negativer Ganzzahlen. Zwar lässt sie sich leicht beschreiben – das Komplement der Darstellung einer negativen Zahl ist die normale Binärdarstellung ihres Betrags –, aber die Implementation einer Recheneinheit für so dargestellte Zahlen ist umständlich. Vorteile gegenüber der heute üblichen Zweierkomplement-Darstellung hat sie nur bei der ohnehin meist langsamen Division, bei der Multiplikation mit doppelt langem Ergebnis sowie bei der Bildung einfacher Prüfsummen.

Einerkomplementdarstellung

Vergleich der Darstellung eines Nibbles (4 Bit) als vorzeichenloser Wert (0's), als Betrag und Vorzeichen (BuV), im Einerkomplement (1'S) und im Zweierkomplement (2'S)
Gespeicherter Wert		Dezimale Interpretation
Bin	Hex	0's	BuV	1'S	2'S
0000	0	0	0	0	0
0001	1	1	1	1	1
0010	2	2	2	2	2
0011	3	3	3	3	3
0100	4	4	4	4	4
0101	5	5	5	5	5
0110	6	6	6	6	6
0111	7	7	7	7	7
1000	8	8	−0	−7	−8
1001	9	9	−1	−6	−7
1010	A	10	−2	−5	−6
1011	B	11	−3	−4	−5
1100	C	12	−4	−3	−4
1101	D	13	−5	−2	−3
1110	E	14	−6	−1	−2
1111	F	15	−7	−0	−1

Binäre Kodierungen vorzeichenbehafteter Ganzzahlen haben meist folgende Eigenschaften:

verwendet wird eine konstante Anzahl n von Stellen,
das höchstwertige Bit (most significant bit) zeigt das Vorzeichen an: 0 für Plus, 1 für Minus,
sie stimmen für positive Zahlen überein mit der vorzeichenlosen Darstellung, in der kleine Zahlen vorne mit Nullen ergänzt werden.

Unterschiede bestehen bei gesetztem höchstwertigen Bit. In diesem Fall ergibt sich bei der Einerkomplementdarstellung der Betrag durch Komplementbildung. Zum Beispiel erweist sich 1010 durch die führende 1 als negativ und der Betrag ist ~1010, also 0101 = 5. Durch diese Definition ergeben sich folgende weitere Eigenschaften der Einerkomplementdarstellung:

es existieren für die Zahl 0 zwei Darstellungen, +0 = 0000 und −0 = 1111,
positive und negative Zahlen reichen symmetrisch bis zum gleichen Betrag, hier 7 = 0111.

Die Beispiele sind hier für eine Wortbreite von n = 4 bit angegeben. Für 8 und 16 bit ergeben sich die Maximalbeträge 127 bzw. 32767, allgemein $2^{n-1}-1.$

Rechenoperationen und Probleme

Die in Einerkomplementdarstellung einfachste Rechenoperation ist die arithmetische Negation (unärer --Operator). Es ist lediglich das bitweise Komplement zu bilden. Dadurch lässt sich die Subtraktion (binärer --Operator) direkt auf die Addition zurückführen: 3 − 4 = 3 + (−4). Für die Durchführung dieser Addition ergibt ein für vorzeichenlose Zahlen konstruiertes Addierwerk das richtige Ergebnis:

          1011 (−4)
       +  0011 (+3)
Übertrag 0011
         —————
       =  1110 (−1)

Nachteil der Einerkomplementdarstellung ist die Behandlung des Falls, wenn bei einer Operation die Null durchschritten wird. Beispiel: Beim Berechnen von −4 + 6 = +2 erscheint nach einer einfachen Dualzahl-Addition der beiden Einerkomplementdarstellungen zunächst ein falsches Zwischenergebnis:

 −4 + 6 = +2 führt zu
          1011
       +  0110
Übertrag 1110
         —————
       =  0001 (Zwischenergebnis)

Die 0001 stünde für +1, nicht für +2. Damit ein korrektes Ergebnis erscheint, muss der am weitesten links stehende Übertrag ausgewertet werden (hier 1) und ggf. das Ergebnis um 1 erhöht werden. Mit anderen Worten muss der Übertrag noch zum Zwischenergebnis hinzuaddiert werden:

          0001 (Zwischenergebnis)
       +     1 (Übertrag der vorhergehenden Operation)
         —————
       =  0010

Beim ersten Beispiel oben ist der Übertrag 0, daher entspricht das Zwischenergebnis dort schon dem Endergebnis.

Ein weiterer Nachteil ist das Entstehen einer Redundanz: Es existieren für die Null zwei Darstellungen: 0000 (+0) und 1111 (−0). Zum einen wird bei einer begrenzten Anzahl von Bits nicht die maximale Ausdehnung des Betrags der darstellbaren Zahlen ausgenutzt. Der darstellbare Zahlenraum verringert sich um 1; da die Null zweimal vorhanden ist, fällt ein Datenwort für den Zahlenraum weg. Die Darstellung jeder anderen Zahl bleibt aber eindeutig. Im Beispiel hier mit 4 Bits werden mit den 2⁴ = 16 verschiedenen Bitkombinationen nur 15 verschiedene Zahlen (von −7 bis 7) dargestellt.

Beide geschilderten Probleme werden bei der Kodierung von Zahlen in der Zweierkomplementdarstellung vermieden.

Das Hinzuaddieren des Übertrags verbessert die Empfindlichkeit einer einfachen Prüfsumme gegen mehrfache Bitfehler. So würde eine Prüfsumme mit der Überträge ignorierenden Modulo-Arithmetik mit einer Wahrscheinlichkeit von 50 % keinen Übertragungsfehler anzeigen, wenn das höchstwertige Bit oft falsch ist, z.B. konstant null. Das TCP verwendet eine Prüfsumme in Einerkomplement-Arithmetik, die diesen Mangel nicht aufweist und deren effiziente Berechnung auf Hardware ohne Einerkomplement-Rechenwerk in der RFC 1071: Computing the Internet Checksum beschrieben ist.

Verallgemeinerung auf B-adische Systeme

Die nur im Binärsystem mögliche Invertierung entspricht der Rechenvorschrift $\overline {a}~=~(B-1)-a$ mit der Basis B des Stellenwertsystems. Im Dezimalsystem muss die Ziffer also von 9 abgezogen werden. Einige Autoren sprechen dann vom Neunerkomplement und allgemein vom (B-1)-Komplement

Beispiel für das Dezimalsystem (dreistellig):

-456₁₀ = ((9-4)(9-5)(9-6))_9K = (543)_9K

Und eine Beispielrechnung:

 112        112
-  3        996
-  4        995
-  5        994
————       ————
 100     (3)097 = 100 (Übertrag zum Ergebnis hinzuaddieren)

Basierend auf einem Artikel in:

Wikipedia.de