Zahlensysteme

Binärsystem

Das Binärsystem, auch Zweier- oder Dualsystem genannt, ist ein Zahlensystem, welches insbesondere in der Informatik eine enorme Relevanz besitzt. Heutige Computersysteme rechnen fast ausschließlich im Binärsystem. Ohne dieses Zahlensystem wäre die Informatik, wie man sie heute kennt, nicht denkbar. Es ist somit neben dem Dezimalsystem eines der wichtigsten Zahlensysteme.

Im Gegensatz zum Dezimalsystem, bei dem zur Darstellung der Zahlen zehn verschiedene Ziffern verwendet werden, kommen im Binärsystem nur die beiden Ziffern 0 und 1 zum Einsatz. Diese Ziffern werden auch Binärziffern genannt. Daraus leitet sich auch der Name dieses Zahlensystems ab. Binärzahlen werden zur Basis 2 dargestellt.

Wie wir wissen, rechnen Computer mit Bits und Bytes. Ein Bit bezeichnet dabei eine Binärziffer, also 0 oder 1. Ein Byte bezeichnet einen Wert, der aus acht aufeinanderfolgenden Bits besteht. Dabei erfolgt die Darstellung der Zahlen im Binärsystem in ähnlicher Weise wie im Dezimalsystem: \[b_m b_{m-1} \dots b_1 b_0, b_{-1} b_{-2} \dots b_{-n}\] mit \(m, n \in \mathbb{N}\) und \(b_i \in \{0, 1\}, -n \leq i \leq m\).

Im Gegensatz zur Darstellung im Dezimalsystem entfällt hier allerdings das führende Vorzeichen. Binärzahlen sind demnach zunächst immer ohne Vorzeichen. Der Grund dafür ist, dass Computer bekanntlich nur mit Bits, also mit 0 und 1, rechnen und dort erst einmal kein Vorzeichen vorgesehen ist. Auf die Darstellung von negativen Binärzahlen gehen wir später ein.

Der Index \(i\) gibt auch hier wieder den Stellenwert der jeweiligen Ziffer \(b_i\) an. Anders als beim Dezimalsystem ist die Wertigkeit jeder Ziffer nun allerdings keine Zehnerpotenz mehr, sondern eine Zweierpotenz \(2^i\).

Entsprechend bestimmt sich der (dezimale) Wert \(b\) einer Binärzahl aus der Summe von Potenzen der Basis 2. Genau wie bei der Berechnung des Wertes von Dezimalzahlen werden die Ziffern vor dem Komma mit Zweierpotenzen mit nichtnegativen Exponenten und die Ziffern hinter dem Komma mit Zweierpotenzen mit negativen Exponenten multipliziert und aufsummiert. Der Wert jeder Binärzahl lässt sich somit wie folgt berechnen: \[b = \sum\limits_{i = -n}^{m}{b_i \cdot 2^i}\]

Um anzuzeigen, dass es sich um eine Zahl in Binärnotation handelt, verwende wir als tiefgestellten Index eine 2.

Beispiel: Binärsystem

\[1101_2 = 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0\] \[= 1 \cdot 8 + 1 \cdot 4 + 0 \cdot 2 + 1 \cdot 1\] \[= 13_{10}\]

An diesem Beispiel sieht man sehr schön, warum es wichtig ist, zwischen der Darstellung einer Zahl und ihrem tatsächlichen Wert (der wie oben beschrieben stets als Dezimalzahl angegeben wird) zu unterscheiden: Die Binärzahl \(1101_2\) hat den Wert \(13_{10}\). Wenn man \(1101\) hingegen als Dezimalzahl auffassen würde, hätte diese mit \(1101_{10}\) einen völlig anderen Wert. Wir bezeichnen zwei Zahlen als gleich, wenn sie denselben Zahlenwert haben. Somit ist \(1101_2 \not = 1101_{10}\).

Auch Zahlen mit Nachkommastellen lassen sich problemlos im Binärsystem darstellen: \[11,101_2 = 1 \cdot 2^1 + 1 \cdot 2^0 + 1 \cdot 2^{-1} + 0 \cdot 2^{-2} + 1 \cdot 2^{-3}\] \[= 1 \cdot 2 + 1 \cdot 1 + 1 \cdot 0,5 + 0 \cdot 0,25 + 1 \cdot 0,125\] \[= 3,625_{10}\]

Wie oben erwähnt, bezeichnet man eine Folge mit der Länge von acht Bits als ein Byte. Die folgende Zahl wäre somit ein Byte lang: \[10101101_2 = 1 \cdot 2^7 + 0 \cdot 2^6 + 1 \cdot 2^5 + 0 \cdot 2^4 + 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0\] \[= 128 + 32 + 8 + 4 + 1\] \[= 173_{10}\]

In heutigen Computersystemen wird häufig mit 32- oder 64-Bit-Zahlen gerechnet. Wie schon erwähnt, versteht man darunter Binärzahlen mit einer Länge von 32 bzw. 64 Bit, oder anders gesagt mit einer Länge von vier bzw. acht Byte. Zur besseren Lesbarkeit kann man bei sehr langen Binärzahlen zwischen den Bits Leerzeichen einfügen. Häufig unterteilt man dabei die Bits in Päckchen von jeweils vier Ziffern (sogenannten Nibbles oder Halbbytes) und fügt zwischen diesen jeweils einen kurzen Freiraum ein. Zum Beispiel kann die 32-Bit-Zahl \[10100110101101011010110101101111_2\] etwas übersichtlicher als \[1010\:0110\:1011\:0101\:1010\:1101\:0110\:1111_2\] geschrieben werden. Diese Schreibweise hat den Vorteil, dass man sehr schnell durch Abzählen der Nibbles die Länge der Zahl bestimmen kann, ohne tatsächlich jede einzelne Ziffer zählen zu müssen.

In der Digitaltechnik werden Bits zur Speicherung von Zuständen benutzt. Eine 1 bedeutet im Allgemeinen, dass der Zustand gesetzt ist, eine 0, dass der Zustand nicht gesetzt ist. Häufig setzt man diese Werte mit den aus der Logik bekannten Wahrheitswerten true und false gleich. Für Informatiker ist es häufig wichtig zu wissen, wie viele Zustände in einer Binärzahl mit einer bestimmten Länge gespeichert werden können. Die Anzahl der möglichen Zustände für Binärzahlen entspricht stets einer Zweierpotenz. Diese Zweierpotenzen sind so wichtig und werden so häufig benutzt, dass die meisten Informatiker zumindest die ersten zehn bis zwölf Potenzen aus der folgenden Tabelle auswendig kennen und nicht mehr berechnen müssen. Sie kommen in unterschiedlichsten Bereichen vor, z.B. bei der Angabe von Festplattenspeicherplatz, Arbeitsspeichergrößen, Datentypen für Programmiersprachen oder Übertragungsgeschwindigkeiten.

Darstellung negativer Binärzahlen im Zweierkomplement

Im Folgenden wollen wir kurz die Frage beleuchten, wie man negative Binärzahlen in einem Computersystem darstellen kann. Der Einfachheit halber wollen wir uns dabei auf Zahlen ohne Nachkommastellen beschränken. Es gibt hierfür verschiedene Möglichkeiten. Die am einfachsten verständliche und gebräuchlichste ist das sogenannte Zweierkomplement. Dieses Verfahren bietet die Möglichkeit, negative Zahlen im Binärsystem darzustellen, ohne auf zusätzliche Symbole wie + und - zurückgreifen zu müssen. Dies hat den Vorteil, dass in digitalen Schaltungen keine zusätzlichen Steuerlogiken notwendig sind. Die Grundidee ist folgende:

Man legt zunächst eine konstante Anzahl von Stellen fest, die alle Binärzahlen haben müssen. Im 8-Bit Zweierkomplement verwendet man beispielsweise, wie der Name schon sagt, Zahlen mit acht Stellen. Bei Bedarf werden kürzere Zahlen dann mit führende Nullen aufgefüllt, d.h. \(10110_2\) wird dann z.B. als \(0001\:0110_2\) dargestellt.

Das höchstwertige Bit, also das am weitesten links stehende, zeigt an, ob es sich um eine negative Zahl handelt. Ist dieses Bit 0, liegt eine nichtnegative Zahl vor. Bei negativen Zahlen hat dieses Bit den Wert 1.

Im 8-Bit Zweierkomplement sind somit alle Zahlen zwischen \(0000\:0000_2\) und \(0111\:1111_2\) nichtnegative Zahlen. Alle Zahlen zwischen \(1000\:0000_2\) und \(1111\:1111_2\) sind negativ.

Die Bestimmung des (dezimalen) Wertes von Zahlen im Zweierkomplement verläuft geringfügig anders als oben für allgemeine Binärzahlen beschrieben. Bei der Rechnung wird implizit berücksichtigt, dass das höchstwertige Bit das Vorzeichen darstellt, indem die höchste Potenz mit einem negativen Vorzeichen versehen ist. Der Wert \(b\) einer (n + 1)-stelligen Binärzahl \(b_n \dots b_0\) im Zweierkomplement berechnet sich wie folgt: \[b = b_n \cdot (-2^n) + \sum\limits_{i = 0}^{n - 1}{b_i \cdot 2^i}\]

Die nachstehende Tabelle zeigt den Wertebereich von achtstelligen Binärzahlen, einmal als vorzeichenlose Dezimalzahl und einmal als Interpretation im 8-Bit Zweierkomplement. Wie man sieht, ist die größte darstellbare positive Zahl im Zweierkomplement nicht mehr 255, sondern nur noch 127. Dafür sind nun allerdings zusätzlich die negativen Zahlen bis einschließlich -128 darstellbar. Der Wertebereich hat sich also durch die Verwendung des Zweierkomplements von 0 ... 255 zu -128 ... 127 verschoben. Im Allgemeinen ist es deshalb wichtig zu wissen, wie der Wert einer Binärzahl interpretiert werden soll.

Man überlegt sich leicht, dass sich dieses Verfahren problemlos auf längere Binärzahlen, z.B. 32 Bit oder 64 Bit, übertragen lässt.

Beispiel: Darstellung negativer Binärzahlen im Zweierkomplement

Wie man Binärzahlen in das Dezimalsystem umrechnet, um ihren Wert als vorzeichenlose Dezimalzahl zu bestimmen, wissen wir bereit. Nachfolgend zeigen wir einige Beispiele für die Interpretation der Werte von negativen Binärzahlen im 8-Bit Zweierkomplement:

\[1010\:0101_2 = 1 \cdot (-2^7) + 1 \cdot 2^5 + 1 \cdot 2^2 + 1 \cdot 2^0\] \[= -128 + 32 + 4 + 1\] \[= -91_{10}\]

\[1000\:0111_2 = 1 \cdot (-2^7) + 1 \cdot 2^2 + 1 \cdot 2^1 + 1 \cdot 2^0\] \[= -128 + 4 + 2 + 1\] \[= -121_{10}\]

\[1100\:0000_2 = 1 \cdot (-2^7) + 1 \cdot 2^6\] \[= -128 + 64\] \[= -64_{10}\]

\[1100\:1100_2 = 1 \cdot (-2^7) + 1 \cdot 2^6 + 1 \cdot 2^3 + 1 \cdot 2^2\] \[= -128 + 64 + 8 + 4\] \[= -52_{10}\]

Rechnen im Binärsystem

In diesem Abschnitt wollen wir kurz beschreiben, wie man im Binärsystem rechnen kann. Wir gehen dabei auf die Grundrechenarten Addition, Subtraktion und Multiplikation ein. Man wird sehen, dass die Durchführung dieser Rechenoperationen im Binärsystem sehr einfach ist und sich deshalb effizient mit logischen Schaltungen realisieren lässt, was einen enormen Gewinn für die Informatik darstellt. Um den Rahmen nicht zu sprengen, werden wir die etwas komplizierte Division von Binärzahlen nicht betrachten.

Die Addition funktioniert genau wie die schriftliche Addition, die in der Grundschule gelehrt wurde. Die Zahlen werden übereinander geschrieben und dann von rechts nach links stellenweise addiert. Für die Addition der einzelnen Ziffern gelten dabei folgende Regeln: \[0_2 + 0_2 = 0_2\] \[0_2 + 1_2 = 1_2\] \[1_2 + 0_2 = 1_2\] \[1_2 + 1_2 = 10_2\] Die vierte Formel bedeutet, dass wir an der entsprechenden Stelle einen Übertrag von 1 haben, der auf die nächste Stelle addiert wird.

Machen wir einige Beispiele zur Addition:

1. Seien \(b_1 := 1011_2\) und \(b_2 := 0011_2\). Wir addieren die Zahlen stellenweise von rechts nach links.
   
   

   \(b_1:\)	\(1011_2\)
   \(b_2:\)	\(+\:0011_2\)
   Übertrag:	\(+\)
   Ergebnis:	\(\)

   
   Bit 0 ist bei beiden Zahlen 1. Gemäß obiger Regel lautet das Ergebnis somit \(1_2 + 1_2 = 10_2\). Bit 0 des Ergebnisses ist also 0 und wir notieren für Bit 1 einen Übertrag von 1.
   
   

   \(b_1:\)	\(1011_2\)
   \(b_2:\)	\(+\:0011_2\)
   Übertrag:	\(+\:10_2\)
   Ergebnis:	\(0_2\)

   
   Bit 1 ist bei beiden Zahlen wieder 1. Die Summe davon ist wieder \(1_2 + 1_2 = 10_2\). Zusätzlich müssen wir allerdings auch noch den Übertrag berücksichtigen, der sich durch die Addition bei Bit 0 ergab. Das Ergebnis lautet somit \(1_2 + 1_2 + 1_2 = 10_2 + 1_2 = 11_2\). Somit ist Bit 1 des Ergebnisses 1 und wir haben darüber hinaus einen Übertrag für Bit 2.
   
   

   \(b_1:\)	\(1011_2\)
   \(b_2:\)	\(+\:0011_2\)
   Übertrag:	\(+\:110_2\)
   Ergebnis:	\(10_2\)

   
   Bit 2 ist bei beiden Zahlen 0, allerdings müssen wir noch das Übertragsbit hinzuaddieren. Es ist also \(0_2 + 0_2 + 1_2 = 1_2\). Somit ist Bit 2 des Ergebnisses 1. Einen Übertrag zum nächsten Bit gibt es diesmal nicht.
   
   

   \(b_1:\)	\(1011_2\)
   \(b_2:\)	\(+\:0011_2\)
   Übertrag:	\(+\:0110_2\)
   Ergebnis:	\(110_2\)

   
   Bit 3 von \(b_1\) ist 1, Bit 3 von \(b_2\) ist 0. Die Summe von \(1_2 + 0_2 = 1_2\). Da kein Übertrag hinzukommt, bleibt es bei diesem Ergebnis für Bit 3.
   
   

   \(b_1:\)	\(1011_2\)
   \(b_2:\)	\(+\:0011_2\)
   Übertrag:	\(+\:0110_2\)
   Ergebnis:	\(1110_2\)

   
   Es ist also \(1011_2 + 0011_2 = 1110_2\).


2. Seien \(b_1 := 1101_2\) und \(b_2 := 1001_2\). Wir addieren die Zahlen wieder stellenweise von rechts nach links.
   
   

   \(b_1:\)	\(1101_2\)
   \(b_2:\)	\(+\:1001_2\)
   Übertrag:	\(+\)
   Ergebnis:	\(\)

   
   Die Addition der Bits an Stelle 0 ergibt \(1_2 + 1_2 = 10_2\). Bit 0 des Ergebnisses ist also 0 und wir haben einen Übertrag von 1.
   
   

   \(b_1:\)	\(1101_2\)
   \(b_2:\)	\(+\:1001_2\)
   Übertrag:	\(+\:10_2\)
   Ergebnis:	\(0_2\)

   
   Für Bit 1 ergibt sich dementsprechend \(0_2 + 0_2 + 1_2 = 1_2\). Einen Übertrag gibt es nicht.
   
   

   \(b_1:\)	\(1101_2\)
   \(b_2:\)	\(+\:1001_2\)
   Übertrag:	\(+\:010_2\)
   Ergebnis:	\(10_2\)

   
   Bit 2 von \(b_1\) ist 1, Bit 2 von \(b_2\) ist 0. Einen Übertrag gibt es nicht. Somit ergibt sich für Bit 2 des Ergebnisses \(1_2 + 0_2 + 0_2 = 1_2\).
   
   

   \(b_1:\)	\(1101_2\)
   \(b_2:\)	\(+\:1001_2\)
   Übertrag:	\(+\:0010_2\)
   Ergebnis:	\(110_2\)

   
   Bit 3 ist bei beiden Zahlen 1. Einen Übertrag gibt es nicht. Somit ergibt sich \(1_2 + 1_2 = 10_2\). Bit 3 des Ergebnisses ist also 0 und es kommt eine weiter Stelle im Ergebnis hinzu, die auf 1 gesetzt wird.
   
   

   \(b_1:\)	\(1101_2\)
   \(b_2:\)	\(+\:1001_2\)
   Übertrag:	\(+\:0010_2\)
   Ergebnis:	\(10110_2\)

   
   Es ist somit \(1101_2 + 1001_2 = 10110_2\). Wie man sieht, kann das Ergebnis der Addition also durchaus mehr Stellen haben als die beiden Summanden.

Betrachten wir die Subtraktion. Diese funktioniert ähnlich wie die Addition. Auch hier werden die Zahlen stellenweise von rechts nach links subtrahiert und auch hier gibt es vier Regeln: \[0_2 - 0_2 = 0_2\] \[0_2 - 1_2 = -1_2\] \[1_2 - 0_2 = 1_2\] \[1_2 - 1_2 = 0_2\]

\(0_2 - 1_2 = -1_2\) bedeutet, dass wir diesmal einen negativen Übertrag haben können. Anstatt also wie bei der Addition auf die folgende Stelle den Wert 1 zu addieren, ziehen wir bei der Subtraktion im Fall eines negativen Übertrags von der nächsten Stelle den Wert 1 ab. Gleichzeitig wird als Ergebnis an die aktuelle Stelle eine 1 geschrieben. Das Vorgehen ist analog zur schriftlichen Subtraktion von Dezimalzahlen.

Machen wir auch hierzu einige Beispiele:

1. Seien \(b_1 := 1011_2\) und \(b_2 := 0111_2\). Wir subtrahieren die Zahlen stellenweise von rechts nach links.
   
   

   \(b_1:\)	\(1011_2\)
   \(b_2:\)	\(-\:0111_2\)
   Übertrag:	\(-\)
   Ergebnis:	\(\)

   
   Für Bit 0 ergibt sich \(1_2 - 1_2 = 0_2\). Einen Übertrag haben wir nicht.
   
   

   \(b_1:\)	\(1011_2\)
   \(b_2:\)	\(-\:0111_2\)
   Übertrag:	\(-\:00_2\)
   Ergebnis:	\(0_2\)

   
   Für Bit 1 ergibt sich \(1_2 - 1_2 = 0_2\). Auch diesmal gibt es keinen Übertrag.
   
   

   \(b_1:\)	\(1011_2\)
   \(b_2:\)	\(-\:0111_2\)
   Übertrag:	\(-\:000_2\)
   Ergebnis:	\(00_2\)

   
   Für Bit 2 ergibt sich \(0_2 - 1_2 = -1_2\). Diesmal haben wir also einen Übertrag von -1 auf die nächste Stelle und notieren 1 als Ergebnis auf die atuelle Stelle.
   
   

   \(b_1:\)	\(1011_2\)
   \(b_2:\)	\(-\:0111_2\)
   Übertrag:	\(-\:1000_2\)
   Ergebnis:	\(100_2\)

   
   Für Bit 3 ergibt sich schließlich unter Berücksichtigung des Übertrags \(1_2 - 0_2 - 1_2 = 0_2\).
   
   

   \(b_1:\)	\(1011_2\)
   \(b_2:\)	\(-\:0111_2\)
   Übertrag:	\(-\:1000_2\)
   Ergebnis:	\(0100_2\)

   
   Es ist also \(1011_2 - 0111_2 = 0100_2\).


2. Seien \(b_1 := 0100_2\) und \(b_2 := 0011_2\). Wir subtrahieren die Zahlen wieder stellenweise von rechts nach links.
   
   

   \(b_1:\)	\(0100_2\)
   \(b_2:\)	\(-\:0011_2\)
   Übertrag:	\(-\)
   Ergebnis:	\(\)

   
   Für Bit 0 ergibt sich mit \(0_2 - 1_2 = -1_2\) eine 1 als Ergebnis an dieser Stelle und ein Übertrag auf die nächste Stelle.
   
   

   \(b_1:\)	\(0100_2\)
   \(b_2:\)	\(-\:0011_2\)
   Übertrag:	\(-\:10_2\)
   Ergebnis:	\(1_2\)

   
   Beim nächsten Bit müssen wir aufpassen! Bit 1 von \(b_1\) ist 0, Bit 1 von \(b_2\) ist 1. Damit ergäbe sich \(0_2 - 1_2 = -1_2\). Allerdings müssen wir zusätzlich noch den Übertrag berücksichtigen. Wir haben also wie im vorherigen Fall einen Übertrag auf die nächste Stelle, müssen als Ergebnis für dieses Bit allerdings eine 0 statt einer 1 notieren.
   
   

   \(b_1:\)	\(0100_2\)
   \(b_2:\)	\(-\:0011_2\)
   Übertrag:	\(-\:110_2\)
   Ergebnis:	\(01_2\)

   
   Für Bit 2 müssen wir erneut den Übertrag von der vorherigen Stelle berücksichtigen. Es ergibt sich \(1_2 - 0_2 - 1_2 = 0_2\). Diesmal haben wir keinen Übertrag auf die nächste Stelle.
   
   

   \(b_1:\)	\(0100_2\)
   \(b_2:\)	\(-\:0011_2\)
   Übertrag:	\(-\:0110_2\)
   Ergebnis:	\(001_2\)

   
   Bit 3 ist für beide Zahlen 0. Da wir keinen Übertrag haben, ergibt sich somit \(0_2 - 0_2 = 0_2\) als Ergebnis für Bit 3.
   
   

   \(b_1:\)	\(0100_2\)
   \(b_2:\)	\(-\:0011_2\)
   Übertrag:	\(-\:0110_2\)
   Ergebnis:	\(0001_2\)

   
   Es ist also \(0100_2 - 0011_2 = 0001_2\).

Bei der Subtraktion ist zu beachten, dass das obige Verfahren nur funktioniert, wenn die erste Zahl (der Minuend) größer ist als die zweite Zahl (der Subtrahend). Sollte dies nicht der Fall sein, muss die Subtraktion durch die Addition des Zweierkomplements dieser Zahlen erfolgen.

Als nächstes wollen wir die Multiplikation betrachten. Auch hierfür gibt es wieder vier Rechenregeln: \[0_2 \cdot 0_2 = 0_2\] \[0_2 \cdot 1_2 = 0_2\] \[1_2 \cdot 0_2 = 0_2\] \[1_2 \cdot 1_2 = 1_2\] Die schriftliche Multiplikation für Binärzahlen funktioniert exakt so, wie man es von den Dezimalzahlen kennt: Man schreibt beide Zahlen mit einem \(\cdot\) verknüpft nebeneinander. Dann beginnt man mit der letzten Ziffer des zweiten Faktors und multipliziert diese mit dem ersten Faktor. Das Ergebnis schreibt man rechtsbündig unter den zweiten Faktor. Nun multipliziert man die vorletzte Ziffer des zweiten Faktors mit dem ersten Faktor und schreibt das Ergebnis unter das erste Ergebnis, allerdings um eine Bitstelle nach links verschoben. Die letzte Stelle füllt man mit einer Null auf. Dieses Verfahren setzt man iterativ fort, bis alle Ziffern des zweiten Faktors einmal mit dem ersten Faktor multipliziert wurden. Dabei steht jedes Zwischenergebnis um eine Stelle weiter links als das Ergebnis darüber. Anschließend werden die Einzelergebnisse, die nun untereinander stehen, aufsummiert. Dadurch ergibt sich das Gesamtergebnis der Multiplikation.

Verdeutlichen wir dieses Vorgehen mit einigen Beispielen:

1. Seien \(b_1 := 1010_2\) und \(b_2 := 1011_2\). Wir schreiben diese verknüpft durch ein \(\cdot\) nebeneinander und lassen darunter etwas Platz für das Ergebnis.
   
   

   \(1010_2 \cdot 1011_2\)

   
   Nun multiplizieren wir zunächst die letzte Ziffer der zweiten Zahl - also die 1 - der Reihe nach mit allen Ziffern der ersten Zahl. Es gilt \(1_2 \cdot 0_2 = 0_2, 1_2 \cdot 1_2 = 1_2, 1_2 \cdot 0_2 = 0_2\) und \(1_2 \cdot 1_2 = 1_2\). Das erste Zwischenergebnis lautet somit
   
   

   \(1010_2 \cdot 1011_2\)

   \(1010_2\)

   
   Nun wiederholen wir diesen Vorgang mit der vorletzten Ziffer der zweiten Zahl, die ebenfalls eine 1 ist. Das Ergebnis schreiben wir nun um eine Stelle nach links verschoben unter das erste Zwischenergebnis, wobei wir die letzte Stelle mit einer 0 auffüllen.
   
   

   \(1010_2 \cdot 1011_2\)

   \(1010_2\) \(10100_2\)

   
   Die nächse Ziffer der zweiten Zahl ist die 0. Dementsprechend ist das gesamte Zwischenergebnis 0. Dieses schreiben wir - um eine weitere Stelle nach links verschoben - unter das vorherige Ergebnis. Die letzten beiden Stellen füllen wir mit 0 auf.
   
   

   \(1010_2 \cdot 1011_2\)

   \(1010_2\) \(10100_2\) \(000000_2\)

   
   Die letzte Ziffer der zweiten Zahl ist eine 1. Somit ergibt sich \(1010_2\) als Zwischenergebnis. Ernet schreiben wir dieses unter das vorherige Ergebnis, wobei wir wieder um eine Stelle weiter nach links aufrücken und die letzten drei Stellen mit 0 auffüllen.
   
   

   \(1010_2 \cdot 1011_2\)

   \(1010_2\) \(10100_2\) \(000000_2\) \(1010000_2\)

   
   Das Ergebnis der Multiplikation ergibt sich nun als Summe der Einzelergebnisse, die wir mit der Addition von oben berechnen können.
   
   

   \(1010_2 \cdot 1011_2\)

   \(1010_2\) \(10100_2\) \(000000_2\) \(1010000_2\)

   \(1101110_2\)

   
   Es ergibt sich \(1010_2 \cdot 1011_2 = 1101110_2\).


2. Machen wir noch ein weiteres Beispiel zur Multiplikation mit \(b_1 := 1101_2\) und \(b_2 := 0010_2\).
   
   

   \(1101_2 \cdot 0010_2\)

   
   Es ergibt sich:
   
   

   \(1101_2 \cdot 0010_2\)

   \(0000_2\) \(11010_2\) \(000000_2\) \(0000000_2\)

   \(0011010_2\)

   
   Wieder addieren wir die Einzelergebnisse und erhalten damit \(1101_2 \cdot 0010_2 = 11010_2\). Dieses Beispiel illustriert einen schönen Sonderfall, nämlich die Multiplikation einer positiven Dualzahl mit \(10_2 = 2_{10}\). In einem solchen Fall gestaltet sich die Berechnung als extrem einfach, weil man lediglich an die positive Dualzahl eine 0 als letzte Stelle anhängen muss.

Umwandlung von Dezimalzahlen ins Binärsystem

Wie man eine Binärzahl in das Dezimalsystem umrechnet, um ihren Wert als Dezimalzahl darzustellen, wissen wir bereits. Untersuchen wir nun die umgekehrte Richtung und überlegen uns, wie wir Dezimalzahlen ins Binärsystem überführen können. Betrachten wir zunächst den einfacheren Fall der nichtnegativen Zalen. Das Verfahren funktioniert iterativ und lässt sich wie folgt beschreiben:

Sei \(d \in \mathbb{N}\) die umzuwandelnde Dezimalzahl und sei \(b\) die zu bestimmende Binärzahl.

Schritt 1: Setze \(b := 0\).

Schritt 2: Bestimme die Zweierpotenz \(2^i\) mit \(i \in \mathbb{N}_0\), sodass \(2^i \leq d\) und \(2^{i+1} \gt d\) ist.

Schritt 3: Setze das Bit mit Index \(i\) in \(b\) auf 1. (Dabei ist zu beachten, dass die Indizierung bei 0 beginnt, d.h. der Index des niedrigsten Bits ist 0 und nicht 1.)

Schritt 4: Setze \(d := d - 2^i\).

Schritt 5: Falls \(d \gt 0\), wiederhole das Verfahren ab Schritt 2 mit geänderten \(d\). Falls \(d = 0\), ist \(b\) die gesuchte Binärzahl und das Verfahren wird beendet.

Illustrieren wir diesen Algorithmus an einigen Beispielen:

1. Sei \(d := 14_{10}\). Wir wandeln \(d\) in eine Binärzahl \(b\) um.
   
   
   1. Schritt 1: Wir setzen \(b := 0\).
   2. Schritt 2: Es ist \(2^3 = 8 \leq 14 \lt 16 = 2^4\). Somit ist \(i = 3\).
   3. Schritt 3: Wir setzen das Bit mit Index 3 auf 1, also \(b := 1000_2\).
   4. Schritt 4: Wir setzen \(d := 14 - 2^3 = 14 - 8 = 6\).
   5. Schritt 5: Es ist \(d = 6 \gt 0\), somit wiederholen wir das Verfahren ab Schritt 2.
   6. Schritt 2: Es ist \(2^2 = 4 \leq 6 \lt 8 = 2^3\). Somit ist \(i = 2\).
   7. Schritt 3: Wir setzen das Bit mit Index 2 auf 1, also \(b := 1100_2\).
   8. Schritt 4: Wir setzen \(d := 6 - 2^2 = 6 - 4 = 2\).
   9. Schritt 5: Es ist \(d = 2 \gt 0\), somit wiederholen wir das Verfahren ab Schritt 2.
   10. Schritt 2: Es ist \(2^1 = 2 \leq 2 \lt 4 = 2^2\). Somit ist \(i = 1\).
   11. Schritt 3: Wir setzen das Bit mit Index 1 auf 1, also \(b := 1110_2\).
   12. Schritt 4: Wir setzen \(d := 2 - 2^1 = 2 - 2 = 0\).
   13. Schritt 5: Es ist \(d = 0\). Somit endet das Verfahren und die Binärdarstellung von \(14_{10}\) lautet \(1110_2\).
   
   Verifizieren wir kurz, dass wir richtig gerechnet haben! Tatsächlich ist \[1110_2 = 1 \cdot 2^3 + 1 \cdot 2^2 + 1 \cdot 2^1 + 0 \cdot 2^0\] \[= 8 + 4 + 2\] \[= 14_{10}\] also \(14_{10} = 1110_2\).



2. Sei \(d := 1234_{10}\). Wir wandeln \(d\) in eine Binärzahl \(b\) um.
   
   
   1. Schritt 1: Wir setzen \(b := 0\).
   2. Schritt 2: Es ist \(2^{10} = 1024 \leq 1234 \lt 2048 = 2^{11}\). Somit ist \(i = 10\).
   3. Schritt 3: Wir setzen das Bit mit Index 10 auf 1, also \(b := 0100\:0000\:0000_2\).
   4. Schritt 4: Wir setzen \(d := 1234 - 2^{10} = 1234 - 1024 = 210\).
   5. Schritt 5: Es ist \(d = 210 \gt 0\), somit wiederholen wir das Verfahren ab Schritt 2.
   6. Schritt 2: Es ist \(2^7 = 128 \leq 210 \lt 256 = 2^8\). Somit ist \(i = 7\).
   7. Schritt 3: Wir setzen das Bit mit Index 7 auf 1, also \(b := 0100\:1000\:0000_2\).
   8. Schritt 4: Wir setzen \(d := 210 - 2^7 = 210 - 128 = 82\).
   9. Schritt 5: Es ist \(d = 82 \gt 0\), somit wiederholen wir das Verfahren ab Schritt 2.
   10. Schritt 2: Es ist \(2^6 = 64 \leq 82 \lt 128 = 2^7\). Somit ist \(i = 6\).
   11. Schritt 3: Wir setzen das Bit mit Index 6 auf 1, also \(b := 0100\:1100\:0000_2\).
   12. Schritt 4: Wir setzen \(d := 82 - 2^6 = 82 - 64 = 18\).
   13. Schritt 5: Es ist \(d = 18 \gt 0\), somit wiederholen wir das Verfahren ab Schritt 2.
   14. Schritt 2: Es ist \(2^4 = 16 \leq 18 \lt 32 = 2^5\). Somit ist \(i = 4\).
   15. Schritt 3: Wir setzen das Bit mit Index 4 auf 1, also \(b := 0100\:1101\:0000_2\).
   16. Schritt 4: Wir setzen \(d := 18 - 2^4 = 18 - 16 = 2\).
   17. Schritt 5: Es ist \(d = 2 \gt 0\), somit wiederholen wir das Verfahren ab Schritt 2.
   18. Schritt 2: Es ist \(2^1 = 2 \leq 2 \lt 4 = 2^2\). Somit ist \(i = 1\).
   19. Schritt 3: Wir setzen das Bit mit Index 1 auf 1, also \(b := 0100\:1101\:0010_2\).
   20. Schritt 4: Wir setzen \(d := 2 - 2^1 = 2 - 2 = 0\).
   21. Schritt 5: Es ist \(d = 0\). Somit endet das Verfahren und die Binärdarstellung von \(1234_{10}\) lautet \(0100\:1101\:0010_2\).
   
   Vergewissern wir uns wieder, dass wir richtig gerechnet haben: \[0100\:1101\:0010_2 = 0 \cdot 2^{11} + 1 \cdot 2^{10} + 0 \cdot 2^9 + 0 \cdot 2^8 + 1 \cdot 2^7 + 1 \cdot 2^6 + 0 \cdot 2^5 + 1 \cdot 2^4 + 0 \cdot 2^3 + 0 \cdot 2^2 + 1 \cdot 2^1 + 0 \cdot 2^0\] \[= 1024 + 128 + 64 + 16 + 2\] \[= 1234_{10}\] also \(1234_{10} = 0100\:1101\:0010_2\).

Schauen wir uns abschließend an, wie wir Dezimalzahlen in das Zweierkomplement überführen können. Hierbei müssen wir unbedingt beachten, dass es bei zu großen Zahlen zu einem sogenannten Überlauf kommen kann. Dies ist ein bekanntes Problem in der Informatik, das immer dann auftritt, wenn man eine Zahl in einem Datenbehälter (z.B. einer Variablen) speichern möchte, aber der Wert dieser Zahl außerhalb der Grenzen des Wertebereichs des Datenbehälters liegt. Wir haben oben gesehen, dass eine Binärzahl im 8-Bit Zweierkomplement nur Werte zwischen -128 ... 127 annehmen kann. Wenn wir nun also versuchen, einen Wert > 127 oder < -128 in einer solchen 8-Bit-Zahl zu speichern, wird dies offensichtlich zu Problemen führen, da die obersten Bits einer solchen Zahl schlicht und ergreifend durch die zur Verfügung stehende Stellenanzahl nicht mehr dargestellt werden können. Dies verfälscht das Ergebnis. Deshalb sollte man die zu konvertierende Zahl zunächst kurz betrachten und sich vergewissern, dass sie tatsächlich in den zur Verfügung stehenden Wertebereich hineinpasst. Möchte man eine Zahl \(x \in \mathbb{Z}\) mit \(-128 \leq x \leq 127\) in das Zweierkomplement überführen, so kann man hierfür das 8-Bit Zweierkomplement wählen. Falls \(x \lt -128\) oder \(x \gt 127\) ist, würde man stattdessen auf das 16-Bit Zweierkomplement zurückgreifen. Damit kann man Zahlen im Wertebereich -32768 ... 32767 darstellen. Für noch größere oder kleinere Zahlen kann man entsprechende Zweierkomplemente mit noch mehr Stellen wählen.

Der Algorithmus zur Überführung von Dezimalzahlen in das Zweierkomplement lautet wie folgt:

Sei \(d \in \mathbb{Z}\) die umzuwandelnde Dezimalzahl und sei \(b\) die zu bestimmende Binärzahl im Zweierkomplement. Die Wahl des Zweierkomplements (8-Bit, 16-Bit usw.) richtet sich nach der Größe von \(d\).

Schritt 1: Ignoriere das Vorzeichen und überführe die Zahl mit dem oben beschriebenen Algorithmus ins Binärsystem. Speichere das Ergebnis in \(b\).

Schritt 2: Falls \(d \lt 0\) ist, fahre mit Schritt 3 fort. Falls \(d \geq 0\) ist, enthält \(b\) bereits die gesuchte Binärzahl in Zweierkomplement-Darstellung und der Algorithmus wird beendet.

Schritt 3: Invertiere alle Bits von \(b\), indem sämtliche Nullen durch Einsen ersetzt werden und umgekehrt.

Schritt 4: Addiere den Wert \(1_{10}\), also \(0000 ... 0001_2\), zu \(b\). Das Ergebnis ist die gesuchte Binärzahl in Zweierkomplement-Darstellung.

Der Algorithmus nimmt also eine Fallunterscheidung vor: Positive Zahlen können wie oben beschrieben konvertiert werden und müssen ansonsten nicht weiter verändert werden. Falls es sich um eine negative Zahl handelt, müssen wir zusätzlich die Binärstellen negieren und den Wert \(1_{10}\) addieren. Illustrieren wir auch diesen Algorithmus an einigen Beispielen:

1. Sei \(d := 14_{10}\). Weil \(-128 \leq d \leq 127\) ist, können wir das 8-Bit Zweierkomplement wählen.
   
   
   1. Schritt 1: Wir überführen die Zahl mit dem obigen Algorithmus ins Binärsystem. Wir haben im Beispiel oben bereits gesehen, dass \(14_{10} = 1110_2\) ist. Also ist \(b := 0000\:1110_2\). Die führenden Nullen sind zu beachten! Diese haben wir hinzugefügt, da wir \(b\) als Zahl im 8-Bit Zweierkomplement, also als Binärzahl mit acht Stellen, darstellen wollen.
   2. Schritt 2: Es ist \(d \geq 0\), also sind wir fertig und \(b = 0000\:1110_2\) ist die gesuchte Zahl in 8-Bit Zweierkomplement-Darstellung.



2. Sei \(d := -27_{10}\). Weil \(-128 \leq d \leq 127\) ist, können wir das 8-Bit Zweierkomplement wählen.
   
   
   1. Schritt 1: Wir überführen \(d\) ohne Berücksichtigung des Vorzeichens ins Binärsystem und erhalten \(b := 0001\:1011_2 = 27_{10}\).
   2. Schritt 2: Es ist \(d \lt 0\), also fahren wir mit Schritt 3 fort.
   3. Schritt 3: Wir invertieren alle Bits in \(b\) und erhalten \(b := 1110\:0100_2\).
   4. Schritt 4: Wir addieren den Wert \(0000\:0001_2\) und erhalten \(b := 1110\:0101_2\).
   
   Vergewissern wir uns, dass das Ergebnis stimmt: Es ist \[1110\:0101_2 = 1 \cdot (-2^7) + 1 \cdot 2^6 + 1 \cdot 2^5 + 0 \cdot 2^4 + 0 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0\] \[= -128 + 64 + 32 + 4 + 1\] \[= -27_{10}\]



3. Sei \(d := -375_{10}\). Weil \(-375 \lt -128\) ist, reicht das 8-Bit Zweierkomplement nicht mehr aus. Wir müssen also das 16-Bit Zweierkomplement zur Darstellung wählen.
   
   
   1. Schritt 1: Wir überführen \(d\) ohne Berücksichtigung des Vorzeichens ins Binärsystem und erhalten \(b := 0000\:0001\:0111\:0111_2 = 375_{10}\).
   2. Schritt 2: Es ist \(d \lt 0\), also fahren wir mit Schritt 3 fort.
   3. Schritt 3: Wir invertieren alle Bits in \(b\) und erhalten \(b := 1111\:1110\:1000\:1000_2\).
   4. Schritt 4: Wir addieren den Wert \(0000\:0000\:0000\:0001_2\) und erhalten \(b := 1111\:1110\:1000\:1001_2\).
   
   Wir wollen uns erneut vergewissern, dass das Ergebnis richtig ist: \[1111\:1110\:1000\:1001_2\] \[= 1 \cdot (-2^{15}) + 1 \cdot 2^{14} + 1 \cdot 2^{13} + 1 \cdot 2^{12} + 1 \cdot 2^{11} + 1 \cdot 2^{10} + 1 \cdot 2^9 + 0 \cdot 2^8 + 1 \cdot 2^7 + 0 \cdot 2^6 + 0 \cdot 2^5 + 0 \cdot 2^4 + 1 \cdot 2^3 + 0 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0\] \[= -32768 + 16384 + 8192 + 4096 + 2048 + 1024 + 512 + 128 + 8 + 1\] \[= -375_{10}\]