| Home |  | Gleitkommazahlen | | Aufgaben | | Lösungen | | Kontakt | |
Das Duale Zahlensystem
Das binäre Zahlensystem besteht aus 2 Zahlen, gekennzeichnet durch 0 und 1. Man benötigt dieses Zahlensystem in der Informatik, da sich mit technischen Bauteilen sehr leicht die Zustände AN und AUS erzeugen lassen können. Diese Zahlen können entsprechend unserem "normalen" Dezimalsystem verwendet werden. Man kann sie addieren, subtrahieren, multiplizieren und dividieren. Da sie sich also kaum vom "normalen" Rechnen unterscheiden, eignen sie sich hervorragend, um in der EDV eingesetzt zu werden.
Wir beginnen bei 0 und zählen dann 1, 2, 3, usw. bis 9. Jetzt gehen uns die Zahlen aus! Um weiterzählen zu können, beginnt man nun mit einer 1 und fängt wieder bei 0 an. Das ergibt dann 1 und 0 also 10. Weiter geht es mit 11, 12, 13 bis 19. Die Zählerei klappt bis 99, ab jetzt nehmen wir noch eine Zahl dazu, also 100.
Auch hier beginnen wir mit 0 und zählen dann 1. Leider haben wir nur 2 Zahlen, also gehen uns hier die Zahlen aus. Wir machen es jetzt aber genau wie im Dezimalsystem und nehmen eine Stelle dazu. Nach 0 und 1 kommen dann also 10 und 11. Wieder reichen die Stellen nicht! Also noch eine dazu: 100, 101, 110, 111, usw.
Zählen von 0 bis 15 im Dezimal- und Dualsystem
Dezimal Dual
0 0
1 1
2 10
3 11
4 100
5 101
6 110
7 111
8 1000
9 1001
10 1010
11 1011
12 1100
13 1101
14 1110
15 1111
Man kann Zahlen auch anhand ihrer Basis darstellen. Im Dezimalsystem haben wir 10 Zahlen zur Verfügung, von 0 bis 9.
Mit 2 Stellen können wir also 10 * 10 = 100 Zahlen darstellen. 100 Zahlen? Aber 100 hat doch drei Stellen! Dieser Einwand stimmt. Da wir jedoch mit der Zahl 0 beginnen, ist 0 die 1. Zahl, 1 die 2. Zahl, ... 98 die 99. Zahl und 99 die 100. Zahl.
Mit 3 Stellen können wir 10 * 10 * 10 = 1000 Zahlen darstellen. Jede Stelle entspricht einer 10-er Potenz. An einem einfachen Beispiel versuche ich diesen Sachverhalt zu erklären.
Wir nehmen dazu die Zahl 372 und schreiben sie als kleine Rechnung auf:
372 = 3*100 + 7*10 + 2*1.
Das kann man jetzt noch anders darstellen als:
3*102 + 7*101 + 2*100
Auf diese Weise kann man jetzt alle anderen Zahlen auch darstellen:
6574 = 6*103 + 5*102 + 7*101 + 4*100
12032 = 1*104 + 2*103 + 0*102 + 3*101 + 2*100
Verwendung der Potenzschreibweise bei binären Zahlen
Wendet man die Potenzschreibweise bei binären Zahlen an, so muss man eine andere Basis wählen. Es gibt ja nur 2 verschiedene Ziffern, 0 und 1. Also nehmen wir als Basis 2. Die Zahl 1011 schreibt sich dann als 1*23 + 0*22 + 1*21 + 1*20
Die Umrechnung von binären in dezimale Zahlen
Die Potenzschreibweise kann man jetzt zur Umrechnung von binären in dezimale Zahlen benutzen. Wenn wir die kleine Rechnung jetzt ganz normal ausrechnen, bekommen wir den entsprechenden dezimalen Wert: 1011 = 1*23 + 0*22 + 1*21 + 1*20 = 1*8 + 0*4 + 1*2 + 1*1 = 11 Die duale Zahl 1011 entspricht also der dezimalen Zahl 11. (Vergleiche mit obenstehender Tabelle)
Die Umrechnung von dezimalen in binäre Zahlen
Bei der Umrechnung der Dezimalzahlen verwenden wir die "Division mit Rest" aus der Grundschule. Wir teilen die Zahl solange durch 2, bis als Ergebnis 0 herauskommt und merken uns dabei den Rest. Als Beispiel sollen die Zahlen 13 und 14 dienen.
13 / 2 = 6 Rest 1
6 / 2 = 3 Rest 0
3 / 2 = 1 Rest 1
1 / 2 = 0 Rest 1
Die Reste von unten nach oben aneinander gereiht ergeben dann die Dualzahl 1101.
14 / 2 = 7 Rest 0
7 / 2 = 3 Rest 1
3 / 2 = 1 Rest 1
1 / 2 = 0 Rest 1
Hieraus ergibt sich dann die Dualzahl 1110.
Ein Bit ist die kleinste Speichereinheit in der EDV. In einem Bit kann eine Information gespeichert werden. Diese Information kann zwei Zustände haben, nämlich AN oder AUS, also 1 oder 0. Da man jedoch mit dieser Information relativ wenig anfangen kann, hat man Bits zu Bytes zusammengefasst.
Ein Byte ist die Zusammenfassung von 8 Bits. Mit 1 Byte, also 8 Bits, kann man 256 verschiedene Zustände darstellen. Warum 256 verschiedene Zustände? Die kleinste Zahl, die mit 8 Bits dargestellt werden kann ist die dezimale 0, in Dualschreibweise 00000000. Die größte darstellbare Zahl ist die die dezimale 255, in Dualschreibweise 11111111. Wir überprüfen das anhand der Potenzschreibweise: 11111111 = 1*27 + 1*26 + 1*25 + 1*24 + 1*23 + 1*22 + 1*21 + 1*20 = 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 255 Auch hier gilt wieder 1 bis 255 sind 255 Zahlen. Zuzüglich der 0 sind wir bei 256 verschiedenen Zahlen bzw. 256 verschiedenen Zustände. Der Begriff Byte stammt ursprünglich daher, dass ein Prozessor in einem Rechenschritt ein "Biss", also 8 Bit auf einmal aus dem Speicher auslesen konnte. Dieser Begriff ist mit denen neuen Prozessorarchitekturen eigentlich nicht mehr aktuell.
Ein Kilobyte sind ca. tausend Byte. Genauer: 210 Byte = 1.024 Byte
Ein Megabyte sind ca. eine Millionen Byte. Genauer: 220 Byte = 1.048.576 Byte
Ein Gigabyte sind ca. eine Milliarde Byte. Genauer: 230 Byte = 1.073.741.824 Byte
Die Addition funktioniert wie bei der Addition von Dezimalzahlen:
Es gelten die Regeln 0+0=0, 1+0=1, 0+1=1, 1+1=0 Übertrag 1. Im Prinzip also nichts neues. Addiert man im Dezimalsystem 2 Zahlen so kommt bei 5+5 auch 0 Übertrag 1 heraus. Der Übertrag wird bei beiden System jeweils voran gestellt. Also gilt im Dualsystem 1+1=10.
0111
+0100
====
1011
Die Addition ist im Prinzip problemlos. Es gibt allerdings einen Haken an der Sache: Die Addition funktioniert nur innerhalb eines bestimmten Wertebereiches. Woran liegt das? In der Realität können wir beliebig grosse Zahlen darstellen. Das geht leider nicht in der Informatik. Wir haben nur einen begrenzten Raum zur Verfügung. Wir schränken hier die den Wertebereich auf ein Byte ein. Normalerweise verwendet man zur Addition von ganzen Zahlen, einen deutlich größeren Wertebereich, aber um einen überschaubaren Rahmen zu haben, begrenzen wir uns absichtlich auf ein Byte. Unsere größte darstellbare Zahl ist die 11111111, also dezimal 255. Was passiert nun, wenn wir eine 00000001, also 1, addieren? Das verrückte ist: es kommt 00000000, also 0 heraus.
Da bekanntlich 1+1=0 Übertrag 1 gibt, bekommt man als Ergebnis in Wirklichkeit nicht 00000000 sondern 00000000 Übertrag 1. Dieser letzte Übertrag kann jedoch nicht mehr gespeichert werden und wird deshalb einfach ersatzlos gestrichen.
Es ergibt sich daraus jedoch auch eine gewisse Logik. Durch meinen beschränkten Wertebereich komme ich irgendwann an meine obere Grenze. Bei der Addition von 1 fängt dann jedoch der Wertebereich wieder von vorne an, ich bin jetzt an der unteren Grenze, man durchläuft dann wieder den Bereich bis zur oberen Grenze, usw. Wenn wir also immer und immer wieder 1 addieren zählen wir unendlich oft von 0 bis 255, dann wieder 0 bis 255 usw.
Bevor wir zur Subtraktion von Zahlen kommen, müssen wir uns erst mit den Komplementen von Dualzahlen beschäftigen. Man bildet das sogenannte Einerkomplement, indem man jede Zahl durch ihr Gegenteil ersetzt, also die 0 durch die 1 und die 1 durch die 0.
01011010 wird zu 10100101
11101101 wird zu 00010010
Das Zweierkomplement entspricht dem Einerkomplement, nur wird zusätzlich noch 00000001 addiert.
01011010 wird im Einerkomplement zu 10100101 im Zweierkomplement zu 10100110
11101101 wird im Einerkomplement zu 00010010 im Zweierkomplement zu 00010011
Die Subtraktion von Dualzahlen
Hier kommen wir mit unserer normalen Schulmathematik nicht mehr weiter. Bevor wir uns mit dem komplizierten "Warum ist das denn so?" beschäftigen, merken wir uns ersteinmal den Mechanismus. Der Satz lautet: Die Subtraktion von 2 Zahlen erfolgt durch die Addition des Zweierkomplementes.
Als konkretes Beispiel nehmen wir dazu die Rechnung 14-9=5.
- 9 ist im Dualsystem 00001001. Auch hier wäre die richtige Zahl eigentlich 00000101 Übertrag 1, da wir den Übertrag jedoch nicht speichern können, bleiben wir bei 00000101 was ja der Dezimalzahl 5 entspricht.
- Das Einerkomplement zu 00001001 ist 11110110.
- Das Zweierkomplement 11110111.
- Dies addieren wir nun zu 14 also 00001110.
00001110
+11110111
========
00000101
ACHTUNG: Die Subtraktion ist ziemlich schwierig, sie gehört jedoch zum Grundlagenverständnis dazu. Bitte lesen Sie sich dieses Kapitel nochmals intensiv durch. Üben Sie schriftlich mit verschiedenen Zahlen.
Die Multiplikation entspricht einem Verschieben nach links, man spricht auch von einem shift, in diesem Fall ein Links-Shift. Betrachtet man einige einfache Multiplikationen, dann wird das Prinzip deutlich:
00001111 * 00000010 = 00011110
00001111 * 00000100 = 00111100
00001111 * 00001000 = 01111000
00001111 * 00010000 = 11110000
Komplizierter wird es, wenn nicht nur mit 2, sondern mit einer beliebigen Zahl multipliziert werden soll: Für jede 1 im zweiten Operand muss eine Multiplikation ausgeführt werden, und die Ergebnisse anschließen miteinander addiert werden.
00001111 * 00000101 entspricht also 00001111 * 00000100 + 00001111 * 00000001
= 00111100 + 00001111 = 01001011
Auch bei der Multiplikation muss dringend auf den Wertebereich geachtet werden. Denn genauso wie bei der Addition kann es hier zu einem Überlauf kommen, der das Ergebnis verfälscht.
Viele Divisionen haben als Ergebnis eine Zahl mit einer oder mehreren Stellen hinter dem Komma, einige dieser Nachkommazahlen sind sogar unendlich.
Beispiel 1: Teile ich 7 durch 2, so bekomme ich als Ergebnis 3,5 - eine endliche Zahl mit einer Nachkommastelle.
Beispiel 2: Teile ich 10 durch 3, so bekomme ich als Ergebnis 3,33333... - eine unendliche Zahl mit unendlich vielen Nachkommastellen. Diese Zahlen betrachten wir an späterer Stelle nocheinmal genauer, denn hier kommt es zu einem weiteren Problem in der elektronischen Datenverarbeitung: der ungenauen Darstellung von Nachkommazahlen.
Bei der Multplikation wird ein Links-Shift durchgeführt, dementsprechend ist es logisch, dass bei der Division ein Rechts-Shift durchgeführt wird. Teile ich die Zahl 8 durch 2 ergibt das 4, in Dualschreibweise 00001000 / 00000010 = 00000100. Die Division durch 2 entspricht also einem Rechts-Shift von einer Stelle. Die Division von 8 durch 4 ergibt 2, in Dualschreibweise 00001000 / 00000100 = 00000010, also ein Rechts-Shift von zwei Stellen.
Was passiert nun aber mit Nachkommastellen? Schauen wir uns die einfache Division von 3 durch 2 an. 00000011 / 00000010 = 00000001 Der Rechts-Shift bewirkt, dass die letzte 1 rechts aus dem Zahlenbereich "herausfällt". Das bedeutet, dass alle Nachkommastellen abgeschnitten werden. Wichtig: Es wird nicht gerundet, es wird abgeschnitten. Das Ergebnis aus 3 durch 2 ist also 1!!!
Diese Art der Division funktioniert jedoch nur, wenn man durch 2 oder eine Potenz von 2 dividiert. Wir kommen jedoch auch mit unserer ganz normalen "Grundschulmathematik" weiter. Hier ein Beispiel, wie man im Dezimalsystem normalerweise dividiert:
Wenn man diese Art der Division jetzt nach dem gleichen Schema bei binären Zahlen durchführt, dann kommt man auf das gleiche Ergebnis. Rechnet man die Dualzahlen jetzt wiederum in binäre Zahlen um, so kommt man wieder auf 1307/11=18 Rest 9 (siehe oben). Auch hier gilt wieder: Der Rest wird gnadenlos abgeschnitten, nicht gerundet. D.h. Der "Rest" entfällt.
1307/11=118 Rest 9
-11
==
20
-11
==
97
-88
==
9
10100011011/1011=01110110 Rest 1001
- 0|||||||
=====|||||||
10100||||||
- 1011||||||
=====||||||
10010|||||
- 1011|||||
=====|||||
1111||||
- 1011||||
=====||||
1001|||
- 0|||
=====|||
10010||
- 1011||
=====||
1111|
- 1011|
=====|
1001
- 0
====
1001
Die bisherigen Überlegungen lassen uns nur positive Ganzzahlen darstellen. Die kleinste Zahl ist 0, die größte Zahl hängt von der zur Verfügung stehenden Speichermenge ab. Wir haben uns bisher auf ein Byte beschränkt. Normalerweise werden aber je nach Programmiersprache mehrere Bytes zu einer Speicherstelle zusammengefasst. Typischerweise sind das zwei oder vier Bytes. Das bedeutet, dass die größten darstellbaren Dezimalzahlen dann 65535 beziehungsweise 4294967295 sind.
Negative Ganzzahlen - 1. Versuch
Der nächste Schritt ist jetzt die Einführung negativer Zahlen. Dies ist erscheint recht einfach, ist jedoch ziemlich schwer. Ich werde die negativen Zahlen in drei Schritten erklären. Bitte lesen Sie mindestens bis zum dritten Versuch, denn erst dort werden die "richtigen" negativen Zahlen beschrieben.
Wir beschränken uns der Einfachheit halber wieder auf ein Byte. Selbstverständlich ist das Prinzip wieder auf mehrere Bytes als Speicherbereich übertragbar.
Wir kennzeichnen negative Zahlen einfach mit einem führenden Bit. Diese Bits nennt man manchmal auch "flags".
Aus 1 = 00000001 wird dann -1 = 10000001.
Aus 17 = 00010001 wird dann -17 = 10010001.
Negative Ganzzahlen - 2. Versuch
Die Version 1 der negativen Ganzzahlen hat jedoch einen entscheidenden Nachteil. Bei den positiven Ganzzahlen erreiche ich durch die Addition von 1 jeweils die nächst größere Zahl. Bin ich bei der maximalen Zahl angekommen, so führt die Addition von 1 durch den Überlauf dazu, dass ich wieder am unteren Ende ankomme (siehe Kapitel "Vorsicht Überlauf"). Bei negativen Zahlen laut Version 1 führt die Addition von 1 jedoch nicht - mathematisch richtig - zur größeren Zahl, sondern zur kleineren. Beispiel: 10000001 + 00000001 = 10000010 dies ist jedoch mathematisch falsch, denn in dezimaler Schreibweise steht hier -1 + 1 = -2 !!! Aus diesem Grund stellt man negative Zahlen nicht nur durch die Kennzeichnung mit dem ersten Bit dar, sondern man verwendet dazu die oben schon eingeführte Komplementbildung.
Die Bildung des Einerkomplementes hilft uns das Problem zu lösen. Aus der Zahl 1 = 00000001 wird dann -1 = 11111110. Aus der Zahl 4 = 00000100 wird dann -4 = 11111011. Versuchen wir eine Addition. -4 + 1 muss ja -3 ergeben. 11111011 + 00000001 = 11111100. Die Zahl 3 = 00000011 umgewandelt mit dem Einerkomplement ergibt 11111100! Wunderbar. Das scheint also zu funktionieren. Doch auch hier gibt es ein Problem.
Durch die Bildung des Einerkomplementes besitzt unser Wertebereich plötzlich zwei Nullen, nämlich 00000000 und 11111111. Addiere ich zu -1 = 11111110 die 1 = 00000001, so bekomme ich 11111111. D. h. wir haben noch einen logischen Fehler in unseren Überlegungen. Diesen Fehler bessern wir durch die Bildung des Zweierkomplementes aus. Das Zweierkomplement der Null ergibt dann wieder Null. Aus 00000000 wird im Einerkomplement 11111111 und durch die Addition von 00000001 und den Überlauf wieder zu 00000000.
Negative Ganzzahlen - 3. Versuch
Geschafft! Die negativen Zahlen werden also durch Bildung des Zweierkomplementes dargestellt. Hier ein paar Beispiele:
1 = 00000001 wird zu -1 = 11111111
5 = 00000101 wird zu -5 = 11111011
17 = 00010001 wird zu -17 = 11101111
Ich kann also immer noch am ersten Bit erkennen, ob eine Zahl negativ oder positiv ist.
Wertebereich von negativen Ganzzahlen
Nehme ich ein Byte als Speichergrenze, so bekomme ich folgende interessante Zahlen
00000000 = 0
01111111 = 127
10000000 = -128
Mein ehemaliger Wertebereich von 0 bis 255 verändert sich also zu -128 bis +127. Auch hier habe ich wieder insgesamt 256 verschiedene Zahlen. Unsere Interpretation der Zahlen ändert sich.
Letzte Änderung 09.06.2008