Einerkomplement

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Das Einerkomplement, auch (B-1)-Komplement[1], ist eine arithmetische Operation, die meist im Dualsystem angewendet wird. Dabei werden alle Ziffern bzw. Bits invertiert, das heißt: Aus 0 wird 1 und umgekehrt. Eine Ziffer und ihr Einerkomplement ergänzen sich zu 1, daher der Name. Die Operation wird auch als bitweise Negation bezeichnet und der Operator in verschiedenen Programmiersprachen als Tilde ~ notiert.

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[Bearbeiten | Quelltext bearbeiten]

Interpretation einer 4-Bit-Zahl
Bitmuster als Einer-komplement ohne Vorzeichen
0000 +00 0
0001 1 1
0010 2 2
0011 3 3
0100 4 4
0101 5 5
0110 6 6
0111 7 7
1000 −70 8
1001 −60 9
1010 −50 100
1011 −40 110
1100 −30 120
1101 −20 130
1110 −10 140
1111 −00 150

Binäre Kodierungen vorzeichenbehafteter Ganzzahlen haben meist folgende Eigenschaften:

  • verwendet wird eine konstante Anzahl n von Stellen,
  • das höchstwertige 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

Rechenoperationen und Probleme[Bearbeiten | Quelltext bearbeiten]

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), 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 24 = 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[2] beschrieben ist.

Verallgemeinerung auf B-adische Systeme[Bearbeiten | Quelltext bearbeiten]

Die nur im Binärsystem mögliche Invertierung entspricht der Rechenvorschrift mit der Basis B des Stellenwertsystems. Im Dezimalsystem muss die Ziffer also von 9 abgezogen werden. Einige Autoren sprechen dann vom Neunerkomplement[3] und allgemein vom (B-1)-Komplement

Beispiel für das Dezimalsystem (dreistellig):

-45610 = ((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)

Weiterführende Informationen[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Helmut Herold: Grundlagen der Informatik. Pearson Studium, München 2007, ISBN 978-3-8273-7305-2, S. 59
  2. RFC 1071: Computing the Internet Checksum
  3. Neunerkomplement bei Rechnerlexikon.de, abgerufen am 6. April 2015.