Akademik

Komplement

 

[lat. complementum »aufgefüllt«], Logik: in der booleschen Algebra andere Bezeichnung für Negation.

Komplement,

 Zahlendarstellung: gemeinsame Bezeichnung für zwei Operationen an binären (bzw. allgemein in einem bestimmten Zahlensystem dargestellten) Zahlen. Allgemein versteht man in einem Zahlensystem zur Basis b (Binärsystem: b = 2, Dezimalsystem: b = 10, Hexadezimalsystem: b = 16) unter dem b-Komplement einer n-stelligen Zahl z diejenige Zahl z', für die gilt z + z' = bⁿ. Beispielsweise ist das dezimale 10-Komplement (Zehnerkomplement) der Zahl 123 (b = 10, n = 3) 877, denn es gilt 123 + 877 = 1000 = 10³. Dagegen definiert man das (b - 1)-Komplement von z über die Gleichung z + z' = bⁿ - 1 - im obigen Beispiel ist also das dezimale 9-Komplement (Neunerkomplement) von 123 die Zahl 876. Im Hexadezimalsystem spricht man dementsprechend vom Fünfzehner- und Sechzehnerkomplement.

 

In der Informatik interessieren im Wesentlichen nur das binäre Einser- bzw. Zweierkomplement. Mit den obigen Definitionen ist z. B. das Einserkomplement von 101 (dezimal 5) die Zahl 10 (dezimal 2), denn 101 + 010 = 111; das Zweierkomplement von 101 ist 011. Dieses Beispiel demonstriert die allgemeine Regel, dass man das Einserkomplement einer binären Zahl ganz einfach dadurch erhält, dass jede 1 durch eine 0 und jede 0 durch eine 1 ersetzt wird. Das Zweierkomplement bekommt man dann einfach durch Addition der Zahl 1 zum Einserkomplement. Dies erklärt auch, warum in der booleschen Algebra das Komplement als Synonym für den Negationsoperator gebraucht wird.

 

Durch Komplementbildung lässt sich sehr einfach ein Vorzeichenwechsel von Binärzahlen erreichen, wodurch die Subtraktion zweier Binärzahlen auf eine binäre Addition zurückgeführt werden kann. Da Additionen besonders leicht durch logische Schaltungen realisiert werden können, ist die Komplementbildung für die Grundlagen der Computerarithmetik sehr wichtig. Der Zusammenhang zwischen dem Vorzeichen einer Binärzahl und der Komplementbildung ergibt sich aus der Konvention für die Speicherung negativer ganzer Zahlen. Demnach werden bei einem n Byte langen Speicher (z. B. 2 Byte bzw. 16 bit) alle Zahlen von 1 bis 2^n-1 - 1 (im Beispiel 2¹⁵ - 1 = 32 767) als positive Zahlen interpretiert, die Zahlen von 2^n-1 bis 2ⁿ - 1 (32 768 bis 65 535) als negative Werte. Das 16. Bit dient also nur zur Unterscheidung von positiven und negativen Werten, es heißt deswegen auch Vorzeichenbit. Durch Nachrechnen kann man nun sehen, dass ein Vorzeichenwechsel in dieser Darstellung genau der Bildung des Zweikomplements - Vertauschung von Nullen und Einsen mit anschließender Addition von 1 - entspricht (eine zur Einserkomplementbildung äquivalente Definition ist formal ebenfalls möglich, kommt aber praktisch nicht vor).

 

Die Zurückführung der Subtraktion auf die Addition geschieht nun mit dem Gesagten ganz einfach: Für jede beliebige Subtraktion gilt, dass a - b = a + (-b). Eine binäre Subtraktion bedeutet damit, dass man alle Nullen des Subtrahenden (der abzuziehenden Zahl b) in Einsen und alle Einsen in Nullen umwandelt, anschließend addiert man noch die Zahl Eins. Dieser Wert wird zum Minuenden (der Zahl, von der abgezogen wird, a) addiert. Wichtig ist, dass ein etwaiger Übertrag in die am weitesten links stehende Stelle, welcher über den Speicherbereich hinausgehen würde (etwa in die 17. Stelle), ignoriert wird.