Das Binärsystem

Bis wieviel kannst du an einer Hand mit den Fingern zählen? Vermutlich bis 5. Dabei kannst du zum Beispiel die 2 auf verschiedene Arten und Weisen darstellen. Du kannst Daumen und Zeigefinger oder auch Zeigefinger und Mittelfinger verwenden. Insgesamt gibt es zehn Möglichkeiten, auch wenn einige davon weniger praktikabel sind. Ringfinger und kleiner Finger sind eine kleine Herausfordernug für die Hand, während Daumen und Mittelfinger missverstanden werden könnte. Das soll uns hier aber nicht weiter stören.

Jedenfalls ist es doch ziemlich ineffizient, dass man die gleiche Zahl auf so viele verschiedene Weisen zeigen kann. Stattdessen könnte man beispielsweise definieren, dass Zeigefinger und Mittelfinger zusammen eine 6 bedeuten soll und schon kann man ohne Probleme bis 6 zählen. Wir wollen das hier aber etwas systematischer machen und sehen, was möglich ist.

Wir beschränken uns darauf, dass man jeden Finger ausstrecken kann oder eben nicht. Ansonsten gibt es ja beliebig viele Handpositionen und wir könnten auch beliebig viele Zahlen darstellen, wobei man dann aber sehr genau hinschauen müsste. Damit ich im Folgenden nicht immer die Finger benennen muss, verwenden wir die folgende Notation. Eine 1 steht für einen ausgestreckten Finger, eine 0 steht für einen nicht ausgestreckten Finger. Eine fünfstellige Ziffernkombination aus 0en und 1en steht dann für eine Handposition, wobei die Stelle rechts für den Daumen und die Stelle ganz links für den kleinen Finger steht. Also steht 01101 dafür, dass Daumen, Mittelfinger und Ringfinger ausgestreckt sind. Du kannst die Notation am Besten mit deiner rechten Hand mit der Handfläche zu dir simulieren.

Wie viele Handstellungen gibt es?

Zunächst sollten wir klären, wie viele verschiedene Möglichkeiten es gibt, Finger auszustrecken. Für jeden einzelnen Finger gibt es 2 Möglichkeiten und diese sind unabhängig, also können wir 2\cdot2\cdot2\cdot2\cdot2=32 verschiedene Stellungen erreichen. Der Plan ist jetzt, jeder dieser Positionen eine Zahl zuzuorden. Dann können wir nämlich bis 32 zählen. Wir haben auch die Stellung 00000, also eine Faust, betrachtet. Diese sollte vielleicht der Null entsprechen, weil wir auch keinen Finger verwenden. Also ist es sinnvoller von 0 bis 31 zu zählen.

Als Zuordnung nehmen wir eine möglichst einfache. Wir sortieren diese fünfstelligen Ziffernkombinationen wie sie auch in einem Lexikon sortiert wären und ordnen aufsteigend die Zahlen von 0 bis 31 zu. Dabei wird passenderweise auch 00000 der Null zugeordnet.

Die Zuordnungen sehen also folgendermaßen aus:

• 00000: 0
• 00001: 1
• 00010: 2
• 00011: 3
• 00100: 4
• 00101: 5
• 00110: 6
• 00111: 7
• 01000: 8
• 01001: 9
• 01010: 10
• 01011: 11
• 01100: 12
• 01101: 13
• 01110: 14
• 01111: 15
• 10000: 16
• 10001: 17
• 10010: 18
• 10011: 19
• 10100: 20
• 10101: 21
• 10110: 22
• 10111: 23
• 11000: 24
• 11001: 25
• 11010: 26
• 11011: 27
• 11100: 28
• 11101: 29
• 11110: 30
• 11111: 31

Muss man jetzt also immer eine Tabelle mitführen, um zu wissen, wie man jetzt die 23 darstellt? Oder bei 0 anfangen und hochzählen, obwohl man eigentlich nur eine Zahl darstellen möchte? Wir haben bis jetzt gesehen, dass es möglich ist, an einer Hand bis 31 zu zählen, nun soll es darum gehen, das System dahinter zu verstehen, um es praktikabler zu machen.

Welche Zahlen werden denn durch genau einen Finger dargestellt? Das sind die Zahlen 1, 2, 4, 8 und 16, also genau die Zweierpotenzen. Die 12 wird durch den Ringfinger und Mittelfinger dargestellt. Wenn man diese Finger einzeln verwenden würde, stehen sie für 8 bzw. 4. Es liegt die Vermutung nahe, dass sich die weiteren Zahlen als Summe der Zweierpotenzen schreiben lassen und sich dadurch die entsprechenden Finger ergeben. Tatsächlich ist die Vermutung für alle Zahlen richtig.

Wie kann man eine Zahl darstellen?

Damit wir sinnvoll bis 31 zählen können brauchen wir also eine Methode, um eine gegebene Zahl in eine Fingerkonstellation umzuwandeln, also eine Summe von (verschiedenen) Zweierpotenzen zu finden, die diese Zahl ergibt. Andererseits benötigen wir einen Weg, um die angezeigte Zahl abzulesen. Letzteres ist relativ klar, wir addieren die entsprechenden Zweierpotenzen. Bei 11010 rechnen wir 16+8+2=26.

Für die andere Richtung nehmen wir einfach immer die größtmögliche Zweierpotenz, die nicht größer als die Zahl ist, subtrahieren diese und wiederholen den Schritt. Wenn wir 21 umwandeln möchten nehmen wir zunächst die 16 (32 wäre schon zu groß). Es verbleiben 5, also nehmen wir als nächstes die 4. Der Rest von 1 ist schon eine Zweierpotenz (2^0=1). Also ist 21=16+4+1 und wir erhalten 10101.

Warum funktioniert dieses Verfahren? Zunächst einmal muss es irgendwann aufhören, weil wir immer wieder eine positive Zahl abziehen. Es bleibt also nur noch zu zeigen, dass wir jede Zweierpotenz maximal einmal nehmen. Es ist klar, dass die Zweierpotenz in einem Schritt nicht größer wird, weil wir immer die größtmögliche Zweierpotenz wählen und die betrachtete Zahl kleiner wird. Es kann also nur noch sein, dass wir die gleiche Zweierpotenz 2^n zweimal hintereinander nehmen. Angenommen das passiert tatsächlich. Dann war die ursprüngliche Zahl vor diesem Schritt aber mindestens 2\cdot2^n=2^{n+1}. Damit hätten wir also nicht 2^n, sondern 2^{n+1} gewählt. Das ist ein Widerspruch. Damit wird die gleiche Zweierpotenz nicht zweimal hintereindander gewählt. Dementsprechend werden die Zweierpotenzen immer kleiner. Also kann jede Zahl mit diesem Verfahren als Summe von verschiedenen Zweierpotenzen geschrieben werden.

Für das Zählen bis 31 hätte es auch gereicht, das Verfahren für alle Zahlen zu überprüfen. Wir haben jetzt sogar mehr bewiesen. Schließlich muss man dieses System nicht auf fünf Stellen einschränken. Wir können uns beliebige Zahlen aus 0en und 1en anschauen. Die letzte Stelle steht für eine 1, die vorletzte für eine 2, die drittletzte für ein 4, usw. Das ist das Binärsystem. Es stehen nur die Ziffern 0 und 1 zur Verfügung und die Wertigkeit der Stellen sind Zweierpotenzen. Im gewöhnlichen Zehnersystem stehen uns die Ziffern 0 bis 9 zur Verfügung und die Wertigkeit der Stellen sind Zehnerpotenzen.

Das obige Verfahren zeigt, dass man jede natürliche Zahl im Binärsystem darstellen kann. Wir werden noch beweisen, dass das auch eindeutig ist. Es tritt also nicht auf, dass es für die gleiche Zahl verschiedene Darstellungen im Binärsystem gibt.

Die geometrische Reihe

Beim Beweis werden wir uns unter anderem die Summe der ersten Zweierpotenzen anschauen. Wir suchen also nach einer geschlossenen Formel für

1+2+4+\cdots+2^n\;.

Nennen wir diese Summe mal A_n. Man kann durch Ausprobieren erraten, dass wahrscheinlich A_n=2^{n+1}-1 gilt und dann einen Beweis mit vollständiger Induktion durchführen (probier das doch mal aus!). Alternativ kann man einen Trick anwenden und sich 2A_n anschauen. Auch das sind wieder Zweierpotenzen. Wenn man also die Differenz betrachtet, wird viel wegfallen:

\begin{aligned}2A_n-A_n &= 2(1+2+\cdots+2^n)-(1+2+\cdots+2^n)\\&=(2+4+8+\cdots+2^{n+1})-(1+2+\cdots+2^n)\\&=2^{n+1}-1\end{aligned}

Also gilt tatsächlich A_n=2^{n+1}-1. Man kann diesen Trick auch für allgemeine Potenzen anwenden und damit beweisen:

1+x+x^2+\cdots+x^n=\frac{x^{n+1}-1}{x-1}\;.

Wie können wir das jetzt anwenden? Nehmen wir doch einmal an, dass es zwei verschiedene Darstellungen im Binärsystem für eine Zahl n gibt. Wir wählen das n dabei so, dass es die kleinste Zahl ist, die mehr als eine Darstellung hat. Dann können wir die Zahl auf zwei Weisen als Summe von verschiedenen Zweierpotenzen schreiben. Es gilt dann also

\begin{aligned}n&=2^{a_1}+2^{a_2}+\cdots+2^{a_k}\\&=2^{b_1}+2^{b_2}+\cdots+2^{b_l}\end{aligned}

Wir schreiben die Summe dabei so, dass die Zweierpotenzen absteigend sortiert sind, also a_1\gt a_2 \gt \cdots \gt a_k und analog b_1 \gt b_2 \gt \cdots \gt b_l. Es folgt, dass a_1\neq b_1, ansonsten gäbe es für n-2^{a_1} auch mindestens zwei Darstellungen, indem man die erste Zweierpotenz weglässt. Wir hatten aber schon das kleinste n betrachtet. Damit ist insbesondere a_1~\gt~ b_1 oder b_1~\gt ~a_1.

Wir betrachten den Fall a_1 \gt b_1, der andere Fall ist komplett analog, weil man die Darstellungen einfach vertauschen kann. Wir wissen jetzt aber

\begin{aligned}n&=2^{b_1}+2^{b_2}+\cdots+2^{b_l} \\&\leq 2^{b_1}+2^{b_1-1}+\cdots+4+2+1\\&=2^{b_1+1}-1 \\&\lt 2^{b_1+1} \\&\leq 2^{a_1} \\&\leq n \;.\end{aligned}

Also haben wir n \lt n gefolgert, ein Widerspruch. Damit war die Annahme falsch und es gibt eine eindeutige Darstellung.

Rechnen mit dem Binärsystem

Mit dem Binärsystem kann man eigentlich genauso rechnen wie auch mit unserem Dezimalsystem. Ein Übertrag entsteht nicht erst bei 10, sondern eben bei 2. Wenn man also 110100 und 1101 addiert (die 0en am Anfang lassen wir wie beim Dezimalsystem auch weg), kann man von hinten nach vorne vorgehen. Wenn das Ergebnis größer als 1 ist, hat man einen Übertrag. Das tritt zum ersten Mal bei der drittletzten Stelle auf, danach in jedem Schritt. Man erhält 1000001. Im Dezimalsystem wäre das die Rechnung 52+13=65 gewesen.

Besonders einfach ist das Verdoppeln. Wir hängen eine 0 am Ende an. Damit verschieben sich alle Zweierpotenzen um eine Stelle. Also verdoppeln sich alle Zweierpotenzen und somit auch die Zahl. Verdoppeln im Binärsystem ist das Analogon der Multiplikation mit 10 im Dezimalsystem.

Wozu braucht man das Binärsystem?

Das Binärsystem ist nicht nur nützlich, um auf eine umständliche Art bis 31 zählen zu können. Tatsächlich arbeiten Computer mit dem Binärsystem, weil man für jede Ziffer nur zwei Zustände benötigt und diese können durch elektrische Schalter dargestellt werden. Dabei stehen 64 Bit dafür, dass 64 Stellen im Binärsystem zur Verfügung stehen. Mit den Fingern sind wir auf gerade einmal 5 Bit gekommen. Beachte dabei, dass ein zusätzliches Bit die Anzahl der darstellbaren Zahlen verdoppelt. Es ist 2^{64}~=~18.446.744.073.709.551.616 und 2^5~=~32.

Jetzt verstehst du wahrscheinlich auch diesen Witz:

Es gibt 10 Sorten von Menschen. Die, die das Binärsystem verstehen und die, die es nicht verstehen.

Im nächsten Artikel werde ich eine Methode zeigen, mit der man sich die Reihenfolge eines Kartendecks einfach merken kann.