Codierung natürlicher Zahlen

Stellenwertsystem Ein Stellenwertsystem ermöglicht die eindeutige Darstellung jeder natürlichen Zahl unter Verwendung einer begrenzten Menge von Zahlzeichen. Das Stellenwertsystem zur Basis $b$ besitzt $b$ verschiedene Zahlzeichen. Da sich jede natürliche Zahl $n\in\mathbb{N}$ schreiben lässt als $$n = a_0\cdot b^0 + a_1\cdot b^1 + a_2\cdot b^2 + \ldots + a_k\cdot b^k\ (k\in\mathbb{N}),$$ wobei die Koeffizienten $a_0, a_1, \ldots, a_k$ jeweils aus der Menge ${0, 1, \ldots, b - 1}$ stammen. Jeder Koeffizient lässt sich daher eindeutig durch eines der $b$ Zahlzeichen darstellen und die Zahl $n$ durch Hintereinanderschreiben der den Koeffizienten $a_k, a_{ k-1 }, ..., a_0$ zugeordneten Zahlzeichen.
Das alles ist auf den ersten Blick sicher etwas abstrakt, es wird aber klar, wenn wir es am uns am Stellenwertsystem zur Basis $10$, dem uns vertrauten Zehnersystem, veranschaulichen:

Zehnersystem
Das Zehnersystem hat die Basis $b = 10$ und die Zahlzeichen $0, 1, 2, 3, 4, 5, 6, 7, 8, 9$. Jede natürliche Zahl $n\in\mathbb{N}$ lässt sich darstellen als Summe $$n = a_0\cdot10^0 + a_1\cdot10^1 + a_2\cdot10^2 + \ldots + a_k\cdot10^k\ (k\in\mathbb{N})$$ Zur Angabe von $n$ reicht es also, die Koeffizienten $a_0, a_1, \ldots, a_k$ anzugeben. Man schreibt sie einfach direkt hintereinander auf.
Beispiel:
Die Anzahl $n$ der blauen Punkte rechts lässt sich schreiben als $$n = 5\cdot10^0 + 3\cdot10^1$$ Wir nehmen daher das 6. und das 4. Zahlzeichen und schreiben sie (beginnend mit dem höherwertigsten) hintereinander an. So gelangen wir zur Darstellung "$35$" für diese Zahl.

Hexadezimalsystem
Stell dir vor, wir wären mit insgesamt sechzehn Fingern (acht an jeder Hand) auf die Welt gekommen! Dann würden wir unsere Zahlen in einem Stellenwertsystem mit sechzehn Zahlzeichen darstellen. Es ist üblich, dazu die zehn uns bekannten Zahlzeichen mit den ersten sechs Buchstaben zu ergänzen: $0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F$. Die Basis dieses Stellenwertsystems ist natürlich 16. Zur Darstellung einer Zahl $n\in\mathbb{N}$ schreiben wir sie als Summe $$n = a_0\cdot 16^0 + a_1\cdot 16^1 + a_2\cdot 16^2 + \ldots + a_k\cdot 16^k\ (k\in\mathbb{N})$$ Beispiel:
Die Anzahl der roten Kreise im Bild rechts lässt sich schreiben als $$13\cdot 16^0 + 2\cdot 16^1$$ Entsprechend verwenden wir zur Darstellung das 14. und das 3. Zahlzeichen: "2D". Du wirst Dich jetzt fragen, wie man auf die Koeffizienten 13 und 2 kommt. Um ehrlich zu sein merke ich mir einfach die Wertigkeiten der Stellen auswendig: $1, 16, 256, 4096, \ldots$. Dann beginne ich mit der höchsten Wertigkeit, die in die Zahl reinpasst ($16$), dividiere sie ($45\ :\ 16 = 2) und habe schon den ersten Koeffizienten. Es bleiben $45 - 2\cdot 16 = 13$ übrig.

Binärsystem
16 verschiedene Zahlzeichen sind aufs Erste recht unhandlich (obgleich das in der Informatik sehr vorteilhaft ist, dazu später mehr). Versuchen wir es daher mal mit einer möglichst kleinen Basis. Die Zahl 1 lässt sich nicht verwenden (überlege selbst, warum!), aber mit $b = 2$ funktioniert es schon! Wir brauchen in diesem Fall nur zwei Zahlzeichen $0$ und $1$. Die Wertigkeiten der Stellen sind $2^0, 2^1, 2^2, \ldots$, also $1, 2, 4, 8, 16, 32, \ldots$.

Beispiel:
Wir wollen die Zahl der blauen Kreise oben ("25" im Zehnersystem) im Zweiersystem darstellen. Beginnen wir mit der niedrigsten Wertigkeit, die reinpasst ($16$): $$25 = 1\cdot 16 + 9$$ $$9 = 1\cdot 8 + 1$$ $$1 = 0\cdot 4 + 1$$ $$1 = 0\cdot 2 + 1$$ $$1 = 1\cdot 1 + 1$$ Wir gelangen so zur Summe $$25 = 1\cdot 2^0 + 0\cdot 2^1 + 0\cdot 2^2 + 1\cdot 2^3 + 1\cdot 2^4$$ und damit zur Darstellung "11001" der Zahl im Binärsystem.