Zahlen im Rechner: Stellenwertsysteme, negative Zahlen, Gleitkomma

Tippe in fast jeder Programmiersprache $0{,}1 + 0{,}2$ ein und lass das Ergebnis anzeigen. Heraus kommt nicht $0{,}3$, sondern $0{,}30000000000000004$.

Das ist kein Fehler der Sprache und kein Defekt des Rechners. Es ist eine unvermeidliche Folge davon, wie Zahlen im Speicher stehen, und wer das versteht, vermeidet eine ganze Klasse von Fehlern.

In diesem Kapitel geht es um drei Fragen: Wie stellt ein Rechner überhaupt Zahlen dar? Wie kommen negative Zahlen dazu, wenn es nur Nullen und Einsen gibt? Und wo genau entstehen die Ungenauigkeiten?

Vorausgesetzt wird aus Codierung: Zeichen, Zahlen und Bilder und Digitale Darstellung, dass jede Information im Rechner als Folge von Bits vorliegt und dass sich Dezimalzahlen ins Dualsystem umrechnen lassen.

Neu ist hier alles, was über nichtnegative ganze Zahlen hinausgeht.

Unser Dezimalsystem hat nichts Zwingendes an sich; die Zehn stammt von den Fingern. Allgemein gilt für ein System mit der Basis $b$:

$$z = \sum_{i} z_i \cdot b^i$$

Jede Ziffer $z_i$ liegt zwischen $0$ und $b-1$, und ihre Stelle bestimmt die Potenz.

$$247_{10} = 2 \cdot 10^2 + 4 \cdot 10^1 + 7 \cdot 10^0$$ $$1011_{2} = 1 \cdot 8 + 0 \cdot 4 + 1 \cdot 2 + 1 \cdot 1 = 11_{10}$$

Der Rechner benutzt $b = 2$, weil sich zwei Zustände technisch zuverlässig unterscheiden lassen: Spannung liegt an oder nicht.

Dualzahlen sind für Menschen unhandlich lang. $255_{10}$ ist $11111111_2$; man verzählt sich sofort.

Das Hexadezimalsystem mit $b = 16$ löst das elegant. Es braucht sechzehn Ziffern, deshalb kommen $\texttt{A}$ bis $\texttt{F}$ für 10 bis 15 dazu.

🔴 Der entscheidende Punkt: $16 = 2^4$. Deshalb entspricht genau eine Hexadezimalziffer genau vier Bits, und die Umrechnung ist reines Ablesen in Vierergruppen, ohne jede Rechnung.

$$\underbrace{1111}_{\texttt{F}}\ \underbrace{1111}_{\texttt{F}} = \texttt{FF}_{16} = 255_{10}$$

Genau deshalb siehst du Hexadezimal überall dort, wo Bitmuster gemeint sind: bei Farbangaben wie $\texttt{\#FF8800}$, bei Speicheradressen und bei MAC-Adressen. Es ist keine andere Information, nur eine lesbarere Schreibweise derselben Bits.

Im Speicher gibt es kein Minuszeichen, nur Bits. Die Darstellung negativer Zahlen muss also aus den Bits selbst hervorgehen.

Der naheliegende Weg wäre, das erste Bit als Vorzeichen zu benutzen. Diese Vorzeichen-Betrag-Darstellung hat aber zwei Nachteile:

• Es gäbe $+0$ ($00000000$) und $-0$ ($10000000$), also zwei Nullen. Jeder Vergleich auf null müsste beide Fälle prüfen.
• Die Addition würde eine Fallunterscheidung nach den Vorzeichen brauchen, also zusätzliche Schaltung.

Deshalb benutzen Rechner das Zweierkomplement. Die Bildungsregel für $-x$ bei $n$ Bits:

Alle Bits umkehren (0 wird 1, 1 wird 0). Eins addieren.

Beispiel für $-5$ bei 8 Bit:

  5      = 0000 0101
umkehren = 1111 1010
  + 1    = 1111 1011   →  -5

Warum funktioniert das? Weil die Regel genau die Zahl erzeugt, die bei der Addition zu $x$ null ergibt:

  0000 0101   (  5)
+ 1111 1011   ( -5)
-----------
1 0000 0000

Das Ergebnis hat neun Stellen. Bei 8 Bit fällt die vorderste heraus, übrig bleibt $00000000$, also null. Genau das soll $x + (-x)$ leisten.

Damit sind beide Nachteile behoben. Es gibt nur eine Null, und die Addition funktioniert für positive und negative Zahlen mit derselben Schaltung. Der Prozessor muss die Vorzeichen gar nicht ansehen.

Das vorderste Bit zeigt trotzdem das Vorzeichen an: 0 heißt nicht negativ, 1 heißt negativ. Das ist aber eine Folge der Konstruktion und nicht ihre Grundlage.

Bei $n$ Bits gibt es $2^n$ verschiedene Bitmuster, also auch nur $2^n$ darstellbare Zahlen.

Fällt dir die Unsymmetrie auf? Bei 8 Bit reicht der Bereich von $-128$ bis $+127$, also eine negative Zahl mehr als positive. Der Grund: Die Null belegt einen der 256 Plätze, und sie zählt zur nichtnegativen Seite. Bleiben 127 positive und 128 negative.

Wird der Bereich verlassen, entsteht ein Überlauf. Bei 8 Bit im Zweierkomplement:

$$127 + 1 = 01111111_2 + 1 = 10000000_2 = -128$$

Die größte positive Zahl plus eins ergibt die kleinste negative. Der Rechner meldet das nicht von sich aus; er rechnet einfach weiter. Genau solche Überläufe stecken hinter Programmfehlern, die erst bei großen Werten auftreten, etwa bei Zeitstempeln oder Zählerständen.

Dieser Abschnitt gehört zum erhöhten Anforderungsniveau.

Ganze Zahlen reichen nicht. Für $3{,}14$ oder $6{,}022 \cdot 10^{23}$ braucht es eine andere Darstellung.

Man könnte das Komma an eine feste Stelle legen (Festkomma), etwa immer nach dem 16. Bit. Dann ist der darstellbare Bereich aber sehr schmal: Für sehr große und sehr kleine Zahlen zugleich reicht er nicht.

Deshalb benutzt man Gleitkomma nach dem Muster der wissenschaftlichen Schreibweise:

$$z = (-1)^{V} \cdot M \cdot 2^{E}$$

mit Vorzeichenbit $V$, Mantisse $M$ (die Ziffernfolge) und Exponent $E$ (die Größenordnung). Der verbreitete Standard IEEE 754 teilt 32 Bit so auf:

Das Komma „gleitet", weil der Exponent es verschiebt. Damit lassen sich sehr große und sehr kleine Zahlen mit demselben Format darstellen.

Und hier entsteht das Problem aus der Einleitung. Die Mantisse hat endlich viele Bits, also lassen sich nur endlich viele Zahlen exakt darstellen. Entscheidend ist, welche:

Im Dezimalsystem ist $\tfrac{1}{3} = 0{,}333\ldots$ nicht endlich darstellbar, weil 3 kein Teiler von 10 ist. Im Dualsystem ist $\tfrac{1}{10} = 0{,}1$ nicht endlich darstellbar, weil 5 kein Teiler von 2 ist. Es entsteht die periodische Dualzahl

$$0{,}1_{10} = 0{,}0001100110011\ldots_2$$

Der Rechner muss abschneiden, und damit steht bereits vor jeder Rechnung ein winziger Fehler im Speicher. Bei $0{,}1 + 0{,}2$ addieren sich zwei solche Fehler, und das Ergebnis liegt knapp neben $0{,}3$.

🔴 Die praktische Folge ist eine feste Regel: Vergleiche Gleitkommazahlen nie mit Gleichheit. Statt $\texttt{a = b}$ prüft man $|a - b| < \varepsilon$ mit einer kleinen Schranke $\varepsilon$. Und für Geldbeträge nimmt man keine Gleitkommazahlen, sondern rechnet in Cent mit ganzen Zahlen. Cent sind ganzzahlig, also entfällt das Problem vollständig.