Binärsystem

Alles Gute zum 11. Geburtstag!

Wir sind gewohnt, Zahlen im "Dezimalsystem" darzustellen. Wir verwenden dabei zehn verschiedene Symbole (0,1,2,3,4,5,6,7,8,9) und wenn wir eine größere Zahl als 9 darstellen möchten, wechseln wir einfach auf die nächste Stelle links, wo statt der (nicht geschriebenen) 0 das nächste Symbol 1 hinkommt. An der Einerstelle fangen wir wieder mit dem ersten Symbol 0 an. Einfach gesagt: Nach "9" (bzw. "09") kommt "10".
Dies ist die Beschreibung des Algorithmus, wie wir zählen.

Aber es ginge auch anders. Angenommen, wir verwenden nur zwei Symbole, 0 und 1. Dann müssen wir schon bald auf die nächste Stelle links wechseln (denn nach 0 und 1 gibt es kein Symbol mehr zum Weiterzählen), aber wir machen es einfach genauso wie oben beschrieben. An die nächste Stelle links kommt das nächste Symbol 1 hin. An der Einerstelle fangen wir wieder mit dem ersten Symbol 0 an. Auf "1" folgt also "10".
So zählen Computer. Sie verwenden nicht das Dezimalsystem, sondern das Binärsystem. Es ist sogar so, dass alles, was in einem Computer gespeichert ist, Programme, Dateien, Musik, Bilder in Einsen und Nullen codiert ist, also im Binärsystem dargestellt ist. (Glücklicherweise gibt es Programme, die diese Übersetzungen machen, sodass wir Menschen davon nichts mitbekommen.)

Ich zähle binär: "0", "1", "10", "11", "100", "101", "110", "111", "1000", "1001", "1010", "1011". Halt! Das kann man ja auch "01011" schreiben. Eine nicht brennende Kerze, eine brennende, eine nicht brennende, zwei brennende.
Wie übersetzt man das in das für uns gewohnte Dezimalsystem?

Im Dezimalsystem bedeuten die Stellen von rechts her 1, 10, 100, 1000, u.s.w.
Im Binärsystem bedeuten die Stellen von rechts her 1, 2, 4, 8, 16, u.s.w.
Die Zahl 357 im Dezimalsystem ist eigentlich 3 x 100 + 5 + 10 + 7 x 1.
Und die Zahl 1011 im Binärsystem ist 1 x 8 + 0 x 4 + 1 x 2 + 1 x 1 = 8+0+2+1 = 11.

Auf einer Geburtstagstorte benutzen wir oft für jedes Lebensjahr eine Kerze. Für den 11. Geburtstag würden wir 11 Kerzen benötigen. Auf der oben abgebildeten Geburtstagstorte benötigen wir nur 4 Kerzen! (Die fünfte ganz links stellt 0 dar und kann eigentlich weggelassen werden.) Mit diesen 4 Kerzen kommen wir bis zum 15. Geburtstag aus. Und mit 5 Kerzen kommen wir bis zum 31. Geburtstag aus! Du siehst: Man spart viele Kerzen (und viel Platz auf der Torte), wenn man das Alter binär darstellt.

Umsetzung in Scratch

So, jetzt brauchen wir noch ein Scratch-Programm, das vom Binärsystem ins Dezimalsystem umrechnet. Du erinnerst dich: 1011₂ = 11₁₀, weil 1 x 8 + 0 x 4 + 1 x 2 + 1 = 8+0+2+1 = 11.
Ich drehe die Multiplikationen um: 8 x 1 + 4 x 0 + 2 x 1 + 1
Das ist das gleiche wie 2 x (4 x 1 + 2 x 0 + 1 x 1) + 1 = 2 x (2 x (2 x 1 + 0) + 1) + 1
Das heißt, man muss nur von links her die Ziffern der Binärzahl durchgehen: mit 2 multiplizieren und die nächste Stelle addieren. Und das dreimal. (Bei größeren Zahlen entsprechend öfter.)

Definiere Dezimalzahl von (Binärzahl)
setze [Umrechnungsergebnis v] auf (Zeichen (1) von (Binärzahl))
setze [Stelle v] auf [2]
wiederhole bis <(Stelle) > (Länge von (Binärzahl))>
setze [Umrechnungsergebnis v] auf (((Umrechnungsergebnis) * (2)) + (Zeichen (Stelle) von (Binärzahl)))
ändere [Stelle v] um (1)
ende

Und auch gleich den Weg zurück:

Definiere Binärzahl von (Dezimalzahl)
setze [Umrechnungsergebnis v] auf [] // leer, kein Leerzeichen
setze [Dezimalzahl v] auf (Dezimalzahl)
wiederhole bis <(Dezimalzahl) = [0]>
setze [Ziffer v] auf ((Dezimalzahl) mod (2))
setze [Umrechnungsergebnis v] auf (verbinde (Ziffer) (Umrechnungsergebnis))
setze [DezimalZahl v] auf (((Dezimalzahl) - (Ziffer)) / (2)
end

Wie rechnet der Computer mit Binärzahlen?

Mit Binärzahlen kann man genauso rechnen wie mit den Dezimalzahlen. Machen wir ein Beispiel: 1100₂ (12₁₀) plus 101₂ (5₁₀). Dazu schreibt man zuerst ganz normal die beiden Zahlen untereinander:

 1100
+ 101

Dann geht man wie üblich von rechts nach links vor: 0 + 1 ergibt 1, also ist die letzte Ziffer des Ergebnisses 1. 0 + 0 ergibt 0, die zweitletzte Ziffer ist also 0. 1 + 1 ergibt im Binärsystem natürlich nicht 2 (denn diese Ziffer gibt es im Binärsystem nicht), sondern 10, also eine 0 mit Übertrag 1. Also fügt man eine 0 links an das Ergebnis an, und die 1 merkt man sich. Zum Schluss kommt 1 + 1, der Übertrag von eben. Das ergibt wieder 10, eine 0 mit Übertrag 1, aber da diese Rechnung die letzte ist, kann man 10 so wie es ist links an das Ergebnis anfügen. Als Ergebnis erhält man:

  1100
 + 101
  11     
 10001

10001₂ ist 17₁₀, also stimmt die Rechnung, denn 12 + 5 ergibt 17.

Übrigens

Du bist vielleicht schon einmal auf den folgenden Satz gestoßen (er steht auch auf T-Shirts):
"Es gibt 10 Arten von Menschen: Solche, die Binärzahlen lesen können, und die anderen."
Du verstehst das jetzt, oder? "10", gelesen "eins null" ist im Dezimalsystem 2.

Weiterführende Informationen

• Der oben dargestelle Algorithmus zur Umwandlung der Binärzahl in eine Dezimalzahl folgt dem "Hornerschema" (siehe Wikipedia: https://de.wikipedia.org/wiki/Horner-Schema)
• Wenn man bei der Binären Suche die Ja-Antworten mit 1 darstellt und die Nein-Antworten mit 0, erhält man die Binärdarstellung der gesuchten Zahl.
• Dies entspricht auch dem Pfad in einem Binären Suchbaum.
• Ein effizienter Algorithmus zum Potenzieren basiert auf der Darstellung des Exponenten als Binärzahl.
• Die sogenannte "Ägyptische Multiplikation" beruht auf dem Binärsystem. Siehe Wikipedia: https://de.wikipedia.org/wiki/Russische_Bauernmultiplikation