Ganze Zahlen, auch negative
Für Temperaturen wie −5 braucht man ganze Zahlen mit Vorzeichen. Dafür verwenden wir Integer im Zweierkomplement. Die Bitfolge legt fest, welche ganze Zahl gemeint ist.
Lernpfad Datentypen
Datentypen & Datenstrukturen
Zahlen darstellen, Daten ordnen – verstehen, ausprobieren und üben.
Etappe 1
Vom Binärsystem zu Datentypen
Du kennst bereits die Stellenwerte 1, 2, 4, 8 …: 0101₂ = 4 + 1 = 5. Dabei liest du die Bits als eine ganze Zahl ohne Vorzeichen. Wie speichert der Computer aber −5 oder 5.5?
Im Speicher gibt es nur Nullen und Einsen. Ein Minuszeichen oder ein Komma kann dort nicht einfach als zusätzliches Zeichen stehen. Deshalb vereinbaren wir, was bestimmte Bits bedeuten. Eine solche Regel gehört zum Datentyp.
Bruchteile und verschiedene Grössen
Messwerte wie 0.25 oder 125000.5 haben Nachkommastellen. Ein Gleitkommaformat wie binary32 speichert die Ziffern einer Zahl und zusätzlich, wo ihr Binärkomma liegt.
Dasselbe Bitmuster kann je nach Regel verschiedene Werte bedeuten. Beim folgenden Beispiel ergeben die beiden Integer-Regeln denselben Wert, weil die Zahl positiv ist; die Gleitkommaregel ergibt einen anderen:
00111111 10000000 00000000 00000000
Integer: ganze Zahlen
Bei 8 Bit kann 11111111 ohne Vorzeichen 255 bedeuten. Mit der Zweierkomplement-Regel bedeutet es dagegen −1.
8 Bit im Zweierkomplement: −1binary32: Gleitkommazahlen
32 Bit werden in drei Felder aufgeteilt: Vorzeichen, Exponent und Ziffern. Damit lassen sich viele Zahlen mit Nachkommastellen speichern.
0 | 01111111 | 000…0 = 1.0Byte 3
00111111Byte 210000000Byte 100000000Byte 000000000Merksatz: Ein Datentyp ist eine Interpretationsregel für ein Bitmuster. Er bestimmt Wertebereich, Rechenoperationen und Speicherbedarf.
Etappe 2
Wie speichern wir negative ganze Zahlen?
Im gewöhnlichen Binärsystem bedeutet 00000101 die Zahl 5. Für −5 brauchen wir eine Regel, die auch negative Werte zulässt. Die übliche Regel dafür heisst Zweierkomplement.
Wir behalten die Stellenwerte 1, 2, 4 … bei. Nur die linke Stelle erhält ein negatives Gewicht: Bei 8 Bit wird aus +128 nun −128. Damit können dieselben acht Bits Werte von −128 bis +127 darstellen.
Bit 7−128
Bit 664
Bit 532
Bit 416
Bit 38
Bit 24
Bit 12
Bit 01
Beispiel: 11111011 bedeutet −128 + 64 + 32 + 16 + 8 + 2 + 1 = −5. Es ist also nicht einfach „Minuszeichen plus 5“. Signed heisst „mit Vorzeichen“, unsigned „ohne Vorzeichen“.
Der kurze Weg von +5 zu −5
- +5 mit acht Bits schreiben:
00000101. - Alle Bits umkehren: 0 wird 1 und 1 wird 0. Das ergibt
11111010. - Eins addieren:
11111011.
„Bits umkehren“ wird auch invertieren genannt. Mit dieser Methode findest du die Bitfolge der Gegenzahl.
Eine Operation mit fester Breite
„Das Zweierkomplement bilden“ bedeutet: alle Bits der festgelegten Breite invertieren und 1 addieren. Bei 6 Bit gilt beispielsweise:
001101 → 110011 → 001101
Zweimaliges Anwenden führt zurück zum Ausgangsmuster; Null bleibt Null.
Addition und Subtraktion
Gerechnet wird immer innerhalb der festen Bitbreite. Subtraktion wird als Addition der Gegenzahl ausgeführt:
A − B = A + Zweierkomplement(B)
Passt das mathematische Ergebnis nicht in den Wertebereich, entsteht ein Überlauf.
Weshalb gerade diese Regel?
Der Computer kann dieselbe binäre Addition für positive und negative Zahlen verwenden. Beispielsweise soll −5 + 5 genau 0 ergeben:
11111011 + 00000101 = (1)00000000
Bei acht Bits fällt der Übertrag in Klammern weg. Übrig bleibt 00000000, also 0. Ausserdem gibt es nur eine Darstellung für Null.
Allgemein gilt bei n Bits der Wertebereich −2ⁿ⁻¹ … 2ⁿ⁻¹−1. Eine Zahl ausserhalb dieses Bereichs passt nicht in die gewählte Bitbreite.
Beispiel 6 Bit: Der signed-Wertebereich ist −32 … +31. Das linke Bit signalisiert bei der Interpretation einen negativen Wert; es ist aber kein separates Vorzeichen, sondern besitzt das Gewicht −32.
Bit-Labor
Integer codieren und Bits verändern
Klicke danach einzelne Bits an. Die Auswertung wird sofort aktualisiert.
Überlauf bei 8 Bit
127 + 1 wird zu −128
Das Bitmuster 01111111 springt zu 10000000. Die mathematische 128 liegt ausserhalb des darstellbaren Bereichs.
Etappe 3
Zahlen mit Nachkommastellen: binary32
Integer speichern nur ganze Zahlen. Für Messwerte mit Nachkommastellen brauchen wir eine weitere Regel. Das Binärsystem selbst kann Bruchteile darstellen: Rechts vom Komma haben die Stellen die Werte ½, ¼, ⅛ …
Zum Beispiel bedeutet 0.101₂ = ½ + ⅛ = 0.625. Man könnte das Komma immer an dieselbe Stelle setzen. Dann müsste man sich aber auf einen festen Bereich für ganze Zahlen und Nachkommastellen festlegen.
Bei einer Gleitkommazahl wird die Position des Kommas mitgespeichert. Das ist ähnlich wie 1250 = 1.25 × 10³. Im Binärsystem verwenden wir dafür Potenzen von 2. binary32 ist eine festgelegte Regel aus dem Standard IEEE 754, die insgesamt 32 Bit verwendet.
1 BitVorzeichen s
8 BitExponent E
23 BitFraction f
Die drei Felder sind zur besseren Lesbarkeit vergrössert. Die Angaben 1, 8 und 23 zeigen die tatsächliche Anzahl Bits.
1. Vorzeichen
Dieses Bit legt fest, ob die Zahl positiv oder negativ ist: 0 für positiv, 1 für negativ.
2. Exponent: die Grössenordnung
Der Exponent gibt an, mit welcher Zweierpotenz wir multiplizieren. Ein positiver Exponent macht die Zahl grösser, ein negativer kleiner: 2³ = 8, aber 2⁻³ = ⅛.
Damit auch negative Exponenten gespeichert werden können, addieren wir beim Speichern 127. Dieser Zuschlag heisst Bias. Aus Exponent 3 wird E = 3 + 127 = 130. Die acht Bits speichern E ohne Vorzeichen. Beim Lesen ziehen wir 127 wieder ab.
3. Fraction: die Ziffern
Bei normalen Zahlen verschieben wir das Binärkomma hinter die erste 1, sodass die Zahl mit 1. beginnt. Diese 1 steht dann schon fest und muss nicht gespeichert werden. Die 23 Bits danach heissen Fraction.
Die ganze Folge 1.f heisst Signifikand, in vielen Unterlagen auch „Mantisse“. Mit der führenden 1 haben normale Zahlen 24 signifikante Binärstellen. Null und sehr kleine Zahlen sind Sonderfälle, die wir in Etappe 4 ansehen.
Für normale binary32-Zahlen lassen sich die drei Teile so zusammensetzen. (−1)ˢ liefert das Vorzeichen, 1.f die Binärziffern und 2ᴱ⁻¹²⁷ die Grössenordnung:
Wert =(−1)s×1.f×2E − 127
Schritt für Schritt
10.625 in binary32
- Ganze Zahl und Nachkommateil in Binär umrechnen
10 = 8 + 2 wird zu
1010₂. 0.625 = ½ + ⅛ wird zu0.101₂. Zusammen:10.625₁₀ = 1010.101₂ - Komma hinter die erste 1 verschieben (normalisieren)
Drei Stellen nach links machen die Zahl um den Faktor 8 kleiner. Mit × 2³ gleichen wir das aus:
1.010101₂ × 2³ - Exponent mit dem Zuschlag 127 speichern
E = 3 + 127 = 130 = 10000010₂ - Führende 1 weglassen und auf 23 Fraction-Bits mit Nullen auffüllen
01010100000000000000000
01000001001010100000000000000000
Ergebnis: 0 10000010 01010100000000000000000. Bei negativen Zahlen wird dasselbe Verfahren mit dem Betrag durchgeführt und das Vorzeichenbit auf 1 gesetzt.
binary32-Labor
Dezimalzahl in 32 Bits umwandeln
sExponentFraction
Auch diese Bits sind editierbar. Beobachte, wie stark ein Exponentenbit den Wert verändert.
Etappe 4
Weshalb muss der Computer manchmal runden?
Manche Brüche enden im Binärsystem nie. So wie ⅓ im Dezimalsystem zu 0.333… wird, braucht 0.1 im Binärsystem unendlich viele Stellen. In 32 Bit passt davon nur ein Teil: Der Computer speichert den nächstliegenden darstellbaren Wert.
Normale binary32-Zahlen haben 24 signifikante Binärstellen. Werden die Zahlen grösser, werden deshalb auch die Abstände zwischen ihren darstellbaren Werten grösser. Probiere diese Abstände im Labor aus.
Nächster darstellbarer Wert
Wie gross ist eine binary32-Lücke?
Wähle einen Ausgangswert und vergleiche ihn mit seinem direkten Nachbarn im Format.
gewünscht
0.1in binary32 gespeichert
0.100000001490116119384765625Mit Rundung rechnen
0.1f + 0.2f
Beide Eingaben und das Resultat werden auf binary32 gerundet.
Berechnete Gleitkommawerte vergleichen: Ein direktes == vergleicht die gespeicherten Werte exakt und arbeitet deterministisch. Wegen vorausgegangener Rundungen entspricht das aber oft nicht der mathematisch erwarteten Gleichheit. Verwende dann beispielsweise |a − b| < ε mit einer zum Problem passenden Toleranz. Für exakte Zählwerte sind Integer meist geeigneter.
±0Exponent 0, Fraction 0Es gibt positive und negative Null.
subnormalExponent 0, Fraction ≠ 0Sehr kleine Werte ohne implizite führende Eins.
±∞Exponent 255, Fraction 0Unendlich, etwa nach einem Float-Überlauf.
NaNExponent 255, Fraction ≠ 0„Not a Number“ für undefinierte Resultate.
Etappe 5
Bit-Training: Abschluss von Teil 1
Acht Aufgaben werden bei jedem Durchlauf neu aus einem Aufgabenpool zusammengestellt. Jede Antwort liefert sofort eine fachliche Erklärung.
Bestwert Bit-Training0 %
Ab 75 % gilt diese Etappe als abgeschlossen. Hinweise helfen, ohne Punkte abzuziehen.
Bereit, Bitmuster zu lesen?
Zweierkomplement, binary32-Felder, Bias, Genauigkeit und Sonderwerte.
Aufgabe 1 von 80 richtig
0 %
Auswertung
Etappe 6
Stack: zuletzt hinein, zuerst heraus
Integer und binary32 beschreiben einzelne Zahlen. Eine Datenstruktur ordnet mehrere Werte und legt fest, wie wir auf sie zugreifen. Die Werte darin können zum Beispiel Zahlen oder Texte sein.
Ein Stack ist wie ein Stapel Teller: Du legst oben etwas dazu und nimmst oben etwas weg. Der zuletzt abgelegte Wert kommt zuerst wieder heraus. Das heisst LIFO – Last In, First Out.
Drei Operationen
push legt einen Wert oben auf den Stapel. pop entfernt den obersten Wert und gibt ihn zurück. peek zeigt ihn nur an, ohne ihn zu entfernen.
Wofür ist das nützlich?
Beim Rückgängigmachen muss zuerst die letzte Aktion rückgängig werden. Auch verschachtelte Funktionsaufrufe werden mit einem Aufrufstapel verwaltet.
Ausprobieren
Ein Stapel zum Anfassen
Oben ist der einzige Zugang. Die Darstellung zeigt keine konkreten Speicheradressen. Höchstens 10 Werte im Labor.
Mini-Auftrag
Starte mit A, B, C (C liegt oben). Ersetze nur C durch D. A und B sollen im Stapel bleiben.
Etappe 7
Queue: zuerst hinein, zuerst heraus
Eine Queue ist eine Warteschlange: Wer zuerst ansteht, kommt zuerst dran. Das heisst FIFO – First In, First Out.
Anders als beim Stack gibt es zwei Enden. Neue Werte kommen hinten dazu. Entnommen wird immer vorne. Die Reihenfolge der Ankunft bleibt erhalten.
Drei Operationen
enqueue reiht hinten einen Wert ein. dequeue entfernt den vordersten Wert und gibt ihn zurück. peek zeigt den vordersten Wert, ohne die Queue zu ändern.
Wofür ist das nützlich?
Eine einfache Druckerwarteschlange bearbeitet Aufträge in der Reihenfolge ihres Eingangs. Eine Queue sortiert nicht automatisch nach Wichtigkeit – dafür wäre eine andere Regel nötig.
Ausprobieren
Wer ist als Nächstes dran?
Links ist vorne, rechts ist hinten. Lange Reihen lassen sich seitlich scrollen. Höchstens 10 Werte im Labor.
Mini-Auftrag
Starte mit A, B, C (A ist vorne). Bediene A und reihe D ein. Am Schluss sollen B, C, D in dieser Reihenfolge warten.
Etappe 8
Verkettete Liste: Werte mit Verweisen verbinden
Eine einfach verkettete Liste besteht aus Knoten. Jeder Knoten enthält einen Wert und einen Verweis auf den nächsten Knoten. head zeigt auf den Anfang; der letzte Verweis ist null, also „kein nächster Knoten“.
Die Knoten müssen im Speicher nicht nebeneinander liegen. Die Verweise bestimmen ihre Reihenfolge. Im Labor sind N1, N2 … symbolische Knoten-IDs, keine echten Speicheradressen. Die Positionen zählen ab 0.
Einfügen und Entfernen
Zwischen A und B einen neuen Knoten X einfügen: A verweist neu auf X, X auf B. Beim Entfernen von X verweist A wieder auf B. Die anderen Werte müssen nicht verschoben werden.
Der Unterschied zum Array
Um einen Knoten zu finden, folgen wir den Verweisen vom Anfang aus. Eine Liste springt nicht direkt zu Position 7. Sind die betreffende Stelle und ihr Vorgänger schon bekannt, ist das Umhängen der Verweise einfach.
Ausprobieren
Verweise beobachten
Die hervorgehobenen Knoten wurden besucht. Beim Suchen gilt der erste passende Wert als Treffer. Lange Listen lassen sich seitlich scrollen. Höchstens 10 Knoten im Labor.
Mini-Auftrag
Starte mit Ada → Ben → Mia. Entferne Ben und füge an derselben Position Leo ein. Ziel: Ada → Leo → Mia.
Etappe 9
Baum: eine verzweigte Hierarchie
Ein Baum ordnet Knoten hierarchisch: Oben steht die Wurzel. Darunter liegen Kindknoten. Ein Knoten ohne Kinder heisst Blatt. Von der Wurzel gibt es zu jedem Knoten genau einen Weg; es gibt keine Kreise.
Ordner mit Unterordnern sind ein Beispiel. Ein allgemeiner Baum darf viele Kinder haben. Ein Binärbaum hat höchstens zwei pro Knoten. Im Labor verwenden wir einen binären Suchbaum: Links stehen nur kleinere, rechts nur grössere Werte – auch in den jeweiligen Unterbäumen.
Schrittweise suchen
Vergleiche den Suchwert mit dem aktuellen Knoten. Kleiner? Gehe nach links. Grösser? Gehe nach rechts. Gleich? Gefunden. Fehlt das passende Kind, ist der Wert nicht vorhanden. Das Labor speichert jede Zahl nur einmal.
Die Form ist wichtig
In einem gut verteilten Baum scheiden bei jedem Schritt viele Werte aus. Fügt man sortierte Zahlen ein, kann daraus aber eine lange Kette werden. Dieser einfache Suchbaum gleicht sich nicht automatisch aus.
Inorder besucht zuerst links, dann den Knoten, dann rechts. Bei einem Suchbaum ergibt das eine sortierte Folge.
Ausprobieren
Einfügen und Suchwege verfolgen
Besuchte Knoten und Kanten werden markiert. Grosse Bäume lassen sich seitlich scrollen. Höchstens 15 Knoten im Labor.
Mini-Auftrag
Starte mit Wurzel 8 und den Kindern 4 und 12. Füge 6 ein und suche anschliessend 6. Über welche Knoten führt der Suchweg?
Etappe 10
Hash-Tabelle: mit einem Schlüssel zum Wert
Eine Hash-Tabelle speichert Schlüssel-Wert-Paare, zum Beispiel einen Namen und die zugehörige Punktzahl. Statt alle Namen nacheinander zu prüfen, berechnet eine Hash-Funktion aus dem Schlüssel ein Tabellenfach.
Unser vereinfachtes Labor hat fünf Fächer (0–4). Die Hash-Funktion addiert die Unicode-Zahlenwerte der Zeichen des Schlüssels und nimmt den Rest bei Division durch 5 (mod 5). Beispiel: Ada → 65 + 100 + 97 = 262 → Rest 2 → Fach 2. Gross- und Kleinschreibung zählen.
Kollisionen sind normal
Verschiedene Schlüssel können im selben Fach landen. Das heisst Kollision. Wir speichern dort eine Kette aller Paare und vergleichen beim Suchen die vollständigen Schlüssel. Ben landet wie Ada in Fach 2 – beide bleiben erhalten.
Schlüssel sind eindeutig
Speicherst du für Ada einen neuen Wert, ersetzt dieser nur den bisherigen Wert von Ada. Gute Hash-Funktionen verteilen Schlüssel möglichst gleichmässig: Zugriffe sind dann oft schnell. Bei vielen Kollisionen müssen wir mehr Paare prüfen. Die Tabelle ist nicht alphabetisch sortiert.
Ausprobieren
Fächer, Schlüssel und Kollisionen
Das berechnete Fach wird markiert. Unsere einfache Hash-Funktion ist zum Lernen gedacht, nicht für den produktiven Einsatz. Höchstens 12 Paare im Labor.
Mini-Auftrag
Starte mit Ada → 4. Speichere zusätzlich Ben → 7. Ändere danach Adas Wert auf 5. Beide Schlüssel sollen im selben Fach erhalten bleiben.