Einerkomplement

Das Einerkomplement, auch (b−1)-Komplement, ist eine arithmetische Operation, die meist im Dualsystem angewendet wird. Dabei werden alle Ziffern bzw. Bits einer Binärzahl (Dualzahl) invertiert, das heißt: Aus 0 wird 1 und umgekehrt. Das hat zur Folge, dass jede Ziffer der Binärzahl und ihre korrespondierende Ziffer des Einerkomplements sich „zu 1 ergänzen“, was der Operation ihren Namen gibt. Ist also $z$ eine $n$-stellige Binärzahl, dann ist ihr Einerkomplement

$(2^{n}\!-\!1)-z,$

eine Subtraktion, bei der keine Überträge vorkommen. Die Operation wird auch als bitweise Negation bezeichnet und der Operator in verschiedenen Programmiersprachen als Tilde ~ notiert. Dabei wird die Zahl als Bitkette aufgefasst.

Eine Anwendung des Einerkomplements ist die gleichzeitige Manipulation einzelner Bits in einer Bitkette. Will man zum Beispiel in der Bitkette Zahl alle Bits löschen, die in der Bitkette Maske gesetzt sind, so kann man Zahl mit dem Einerkomplement von Maske bitweise UND-verknüpfen, in C-Syntax Zahl &= ~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)
Überträge 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 Binärzahl-Addition der beiden Einerkomplementdarstellungen zunächst ein falsches Zwischenergebnis:

 −4 + 6 = +2 führt zu
           1011
        +  0110
Überträge 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), siehe vorzeichenbehaftete Null. 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 RFC 1071 beschrieben ist.

Verallgemeinerung auf b-adische Systeme

In einem b-adischen System mit dem Standardziffernvorrat $\{0,1,\ldots ,b\!-\!\!1\}$ entspricht der binären Invertierung pro Ziffer $z$ die Rechenvorschrift ${\bar {z}}~=~(b\!-\!\!1)-z$. Im Dezimalsystem mit b=10 muss also jede Ziffer von 9 abgezogen werden. Einige Autoren sprechen dann vom Neunerkomplement und allgemein vom (b−1)-Komplement. Beispielsweise ist das Neunerkomplement der dreistelligen Dezimalzahl 456dez

${\begin{aligned}{\overline {456}}_{\mathrm {dez} }&=((9-4)(9-5)(9-6))_{\mathrm {dez} }\\&=543_{\mathrm {dez} }\\&=999_{\mathrm {dez} }-456_{\mathrm {dez} }.\end{aligned}}$

Ist also $x$ eine $n$-stellige Dezimalzahl, dann ist ihr Neunerkomplement

$(10^{n}\!-\!1)-x,$

eine Subtraktion, bei der Überträge nicht vorkommen.

Weblinks

• John Walker: Minus Zero. UNIVAC Memories – Einerkomplement auf UNIVAC 1100 Computern. fourmilab.ch (englisch)