B-1-Komplement

Das Einerkomplement ist eine arithmetische Operation auf Dualzahlen. Dabei werden alle Ziffern bzw. Bits negiert, das heißt aus 0 wird 1 und umgekehrt. Dieses wird auch als arithmetische Nicht-Verknüpfung bezeichnet. In den Programmiersprachen C, C++, C#, Perl, PHP oder Java wird diese Operation mit dem Symbol ~ dargestellt.

Das Einerkomplement ist insbesondere dann von Bedeutung, wenn man einzelne Bits manipulieren will. Will man zum Beispiel in dem Wert X alle Bits löschen, die im Wert Y gesetzt sind, so muss man X mit dem Einerkomplement von Y bitweise und-verknüpfen.

Eine Anwendungsmöglichkeit für das Einerkomplement ist die Einerkomplementdarstellung, ein Verfahren, um negative Zahlen im Binärsystem darzustellen, ohne auf zusätzliche Symbole wie + und − angewiesen zu sein. Dies ist vor allem für Computer wichtig, deren Logik allein auf Bits ausgerichtet ist, das heißt, Folgen von 0 und 1. (Hinweis für den Leser: Im Folgenden wird auch dargelegt, warum es zwar ein mögliches Verfahren ist, es aber in der Computertechnik keine weite Verbreitung hat.)

Da bei binären Kodierungen von negativen Zahlen sowohl Vorzeichen als auch die eigentliche Zahl durch Bits dargestellt werden, ist es wichtig zu wissen, welches Bit wofür verwendet wird. Im Binärsystem wird dies normalerweise erreicht, indem sämtliche Zahlen eine konstante Stellenzahl haben und bei Bedarf mit führenden Nullen aufgefüllt werden. Bei der Einerkomplementdarstellung wird das erste Bit eines n-Bit-Datenworts zur Kodierung des Vorzeichens verwendet und die n−1 folgenden zur Kodierung der Zahl. Dabei werden positiven Zahlen führende Nullen, negativen hingegen führende Einsen hinzugefügt. Die unten angeführten Beispiele verwenden je 3 Ziffern für die Kodierung des Betrags und eine Ziffer für die Kodierung des Vorzeichens (das Beispiel ist also eine 4-Bit- bzw. 1-Nibble-(Halbbyte)-Darstellung).

Verwendet man die Einerkomplementdarstellung zur Kodierung von Zahlen, so haben positive Zahlen immer eine führende 0 zur Kodierung des Plus. Negative Zahlen werden durch Negation des kompletten Bitmusters der entsprechenden positiven Zahl dargestellt und beginnen deshalb mit einer 1 zur Kodierung des Minus. Das erste Bit ist also für das Vorzeichen reserviert. Es sollte nie eine Einerkomplementdarstellung mit einer vorzeichenlosen Dualzahl verwechselt werden; beispielsweise repräsentiert 1010 im ersten Fall −5, während im letzteren Fall +10 gemeint ist.

Die Einerkomplementdarstellung von Ganzzahlen zieht in den meisten Fällen erhebliche Probleme in der Implementierung einer Recheneinheit nach sich, weswegen sie nur noch selten verwendet wird. Geringe Vorteile hat sie nur bei der ohnehin meist langsamen Division sowie bei erweiterten Multiplikationen mit doppeltlangem Ergebnis.

Beispiel im 4-Bit-Format

Darstellbare Zahlen bei einer Wortlänge von 4 bit:

0000 = +010  1111 = −010
0001 = +110  1110 = −110
0010 = +210  1101 = −210
0011 = +310  1100 = −310
0100 = +410  1011 = −410
0101 = +510  1010 = −510
0110 = +610  1001 = −610
0111 = +710  1000 = −710

Durch die Negation kann eine Fallunterscheidung für positive und negative Zahlen entfallen: Um −4 + 3 = −1 darzustellen, müssen nur die entsprechenden Zahlen addiert werden. Die Addition erfolgt durch Addition der Einerkomplementdarstellungen als vorzeichenlose Dualzahlen.

Beispiel:

 −4 + 3 = −1 führt zu
          1011
       +  0011
Übertrag 0011
         —————
       =  1110

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 eineindeutig. 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, die auf der Einerkomplementdarstellung aufbaut, vermieden.

Beispiel Kodierung positive Zahl mittels Horner-Schema:

 610
 
 6/2 = 3 Rest 0 (Least-Significant-Bit – LSB)
 3/2 = 1 Rest 1
 1/2 = 0 Rest 1 (Most-Significant-Bit – MSB)
 
 es ergibt sich die Zahl 110= 0000.0110

Beispiel Kodierung negative Zahl:

 1. Negierung der positiven
    110->001
 2. führende Einsen hinzufügen
    1111.1001

Beispiel Addition:

 +4 +(− 4) = 0 führt zu
          00000100
       +  11111011
Übertrag 00000000
         —————————
       =  11111111

Der Übertrag wird bei der Addition und Subtraktion auf die 1 weiter links stehende Ziffer addiert.

Beispiel Addition:

 +10 +(−3) = 7 führt zu
          00001010
       +  11111100
Übertrag 11111000
         —————————
       = 100000110 -> 9 belegte Stellen bei 8 möglichen -> End-Around-Carry tritt auf
   Carry         1
         —————————
       =  00000111

Tritt ein Übertrag am Most-Significant-Bit (dem 1.) auf, so wird der Übertrag als End-Around-Carry zum Least-Significant-Bit (dem letzten) addiert.

Aber auch weiterhin können Fehler bei der Addition auftreten.

Beispiel Überlauf:

          0111 (+7)
       +  0111 (+7)
Übertrag 0111 
         —————
       =  1110 (−1)

Erhält man die 1 als MSB bei Addition zweier positiver Zahlen, so tritt ein Überlauf auf.


Beispiel Überlauf

          1011 (−4)
       +  1011 (−4)
Übertrag 1011
         —————
       =  0110
   Carry     1
       =  0111 (+7)

Beispiel kein Überlauf

          1110 (−1)
       +  1110 (−1)
Übertrag 1110
         —————
       =  1100
   Carry     1
       =  1101 (−2)

Erhält man die 0 als MSB bei Addition zweier negativer Zahlen, so tritt ein Überlauf auf.

Sind beide Zahlen verschieden Vorzeichens, so tritt kein Überlauf ein.


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Komplement — Vervollständigung; Ergänzung; Umkehrung; Gegenwort; Gegensatzwort; Gegenteil; Antonym; Gegentum (umgangssprachlich) * * * Kom|ple|mẹnt 〈n. 11〉 Ergänzungsstück [<frz. complément <lat. compleme …   Universal-Lexikon

  • B-Komplement — Das Zweierkomplement (auch 2 Komplement, Zweikomplement, B(inär) Komplement, Basiskomplement, two s complement) ist eine arithmetische Operation auf Dualzahlen. Dabei werden zunächst alle Ziffern bzw. Bits negiert, das heißt aus 0 wird 1 und… …   Deutsch Wikipedia

  • komplement — komplèment m <G mn nātā> DEFINICIJA 1. dopuna kojom se kompletira, upotpunjuje dodatak [vježbe su komplement predavanja na sveučilištu; odgovarajući softver je komplement hardveru]; upotpunjenje 2. gram. a. svaka dopuna nekom elementu… …   Hrvatski jezični portal

  • Komplement (Mengenlehre) — Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen. Bitte hilf mit, die Mängel dieses… …   Deutsch Wikipedia

  • Komplement (Mengen) — In der Mengentheorie und anderen Teilgebieten der Mathematik sind zwei verschiedene Komplemente definiert: Das relative Komplement und das absolute Komplement. Inhaltsverzeichnis 1 Relatives Komplement 2 Absolutes Komplement // …   Deutsch Wikipedia

  • 2er Komplement — Das Zweierkomplement (auch 2 Komplement, Zweikomplement, B(inär) Komplement, Basiskomplement, two s complement) ist eine arithmetische Operation auf Dualzahlen. Dabei werden zunächst alle Ziffern bzw. Bits negiert, das heißt aus 0 wird 1 und… …   Deutsch Wikipedia

  • Zweier-Komplement — Das Zweierkomplement (auch 2 Komplement, Zweikomplement, B(inär) Komplement, Basiskomplement, two s complement) ist eine arithmetische Operation auf Dualzahlen. Dabei werden zunächst alle Ziffern bzw. Bits negiert, das heißt aus 0 wird 1 und… …   Deutsch Wikipedia

  • Schur-Komplement — In der linearen Algebra bezeichnet das Schur Komplement eine Matrix, die sich aus den einzelnen Blöcken einer größeren Matrix berechnet. Das Schur Komplement ist nach Issai Schur benannt. Inhaltsverzeichnis 1 Definition 2 Interpretation als… …   Deutsch Wikipedia

  • Typ-1-Sprache — Chomsky Hierarchie, gelegentlich Chomsky–Schützenberger Hierarchie, (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger) ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine Hierarchie von Klassen… …   Deutsch Wikipedia

  • Beschränkter Verband — In der Mathematik ist ein Verband eine bestimmte algebraische Struktur mit zwei Verknüpfungen bzw. eine halbgeordnete Menge mit bestimmten Eigenschaften. Inhaltsverzeichnis 1 Definition 2 Verbandsordnung 2.1 Hasse Diagramme 3 Spezielle Verbänd …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”