Informations- und Zahlendarstellung

In einem früheren Artikel haben wir uns mit Bits und Bitfolgen beschäftigt und dabei gesehen, dass man damit verschiedenste Informationen codieren kann. Während wir bei einem eigenen Schachprogramm das Verfahren noch frei wählen können, sind zur Verarbeitung grundlegender Informationen Standards entwickelt worden, die in diesem Kapitel erläutert werden.

Eine absolute Grundlage zur Darstellung von Informationen ist ASCII, der American Standard Code for Information Interchange. Dieser fasst 33 Steuerzeichen und 95 druckbare Zeichen in einem 7-Bit-Code zusammen, also insgesamt 128 Zeichen [1]. Normalerweise erfolgt die Darstellung mit 8 Bit, wobei das erste nur der Fehlerkontrolle dient (Paritätsbit).

Natürlich lassen sich damit nicht alle Zeichen dieser Welt darstellen. Schon früh gab es verschiedene Erweiterungen, die z.B. deutsche Umlaute eingeschlossen haben. Doch mit einem Blick auf den arabischen oder asiatischen Sprachraum erkennt man schnell, dass ein viel komplexerer Code notwendig ist. Dazu wurde Unicode (oder auch UCS für Universal Character Set) mit einer Mindestlänge von 16 Bits entwickelt. Solch ein Codierungsverfahren kann wirklich alle Zeichen dieser Welt erfassen, doch leider ist es nicht Abwärtskompatibel zu ASCII.

Abhilfe schafft hier UTF-8 (8-bit Unicode Transformation Format), eine spezielle Darstellungform des Unicode mit variabler Länger zwischen 8 und 32 Bit (1-4 Byte), die somit voll kompatibel zu ASCII ist [2].

Viel spannender wird das Ganze natürlich, wenn wir Zahlen darstellen wollen. Denn für jede Zahl ein mit 8-Bit codiertes Zeichen zu verwenden ist reine Verschwendung (denn damit können wir ja schon die Zahlen von 0-255 darstellen), mal davon abgesehen, dass dies zum Rechnen unsinnig ist.

Grundsätzlich können wir die Zahlsysteme als endliche Alphabete betrachten:

b={0, 1, 2, …, b-1}, mit b wird die Basis benannt. Hier ein paar Beispiele verschiedener Zahlensysteme:

Dezimalsystem 10={0, 1, 2, 3, 4, 5, 6, 7, 8 9}
Binärsystem (Dualsystem) 2={0, 1}
Oktalsystem 8={0, 1, 2, 3, 4, 5, 6, 7}
Hexadezimalsystem 16={0, 1, 2, 3, 4, 5, 6, 7, 8, 9 , A, B, C, D, E, F}

Im Hexadezimalsystem werden die Ziffern > 9 also mit den Buchstaben von A bis F dargestellt.

Sprechen wir nun von Ziffernfolgen aus ∑b, so nennen wir sie b-adische Zahlen. Diese lassen sich folgendermaßen darstellen: z = (zn-1zn-2 … z0)b – wobei b die Basis, z die gesamte Zahl, zx die Ziffer an Stelle x und n die Anzahl der Ziffern benennt. Ein Beispiel hierzu:

(4946)10 = (1001101010010)2 – also 4946 im Dezimalsystem entspricht 1001101010010 im Binärsystem.

Nun möchten wir jedoch nicht nur natürliche, sondern auch ganze Zahlen darstellen – ganz besonders auch die negativen. Die einfachste Lösung wäre natürlich die Einführung eines Vorzeichen-Bits. Steht dieses auf 0 so handelt es sich um eine positive, steht es auf 1 um eine negative Zahl. So wäre 0010 die Dezimalzahl 2, während 1010 die Dezimalzahl -2 darstellt. Doch diese Darstellung bringt zwei Probleme mit sich: Zum Einen erhält die Zahl 0 zwei Darstellungen (z.B. 0000 und 1000 für +0 und -0), zum Anderen brauchen wir im späteren Rechneraufbau nicht nur ein Addier- sondern auch ein Subtrahierwerk. An dieser Stelle hilft uns die Komplementdarstellung weiter:

Wir betrachten eine n-stellige Dualzahl: z=(zn-1…z0)2. Das Komplement der 1 (kurz !1) ist 0, das Komplement der 0 (kurz !0) ist 1. Zunächst bilden wir das sogenannte Einerkomplement von z:

K1(z) = !zn-1…!z0, Beispiel: K1(010101001) = 101010110

Für !zn-1 = 0 ist K1(z) positiv, für !zn-1 = 1 ist K1(z) negativ, d.h. K1(010101001) ist die negative Darstellung von 010101001. Nun lassen sich Subtraktionen durch reine Additionen darstellen: s1-s2 = s1 + K1(s2). Folgendes Beispiel soll dies verdeutlichen:

Entsteht bei der Addition ein Übertrag, so wird dieser Rest auf das Ergebnis addiert:

Doch ein Problem bleibt, denn die Null verfügt nach wie vor über zwei Darstellungen: 0000 (0) und 1111 (-0). Hier schafft das Zweierkomplement Abhilfe. Es wird genau wie das Einerkomplement gebildet, jedoch wird noch 1 hinzuaddiert:

K2(z) = !zn-1…!z0+1, bzw. K2(z) = K1(z)+1. Beispiele:

Entsteht bei der Addition ein Übertrag, so wird dieser einfach abgeschnitten:

Folgende kleine Tabelle soll einen Überblick über die Darstellung ganzer Zahlen mit den genannten Methoden bieten (3-stellige Dualzahlen):

Bitfolge Dezimaldarstellung
VB K1 K2
000 0 0 0
001 1 1 1
010 2 2 2
011 3 3 3
100 0 -3 -4
101 -1 -2 -3
110 -2 -1 -2
111 -3 0 -1

Abschließend widmen wir uns in diesem Kapitel der Königsdisziplin der Zahlendarstellung: die Gleitkomma-Darstellung. Eine Gleitkommazahl z wird durch (+/-)M*b(+/-)e dargestellt, wobei M die Mantisse, b die Basis und e den Exponenten benennt. Die Basis bleibt für alle rechnerinternen Darstellungen 2, weshalb man z als (+/-M, +/-e) schreiben kann. Eine solche Darstellung ist eindeutig und außerdem muss die 1 vor dem Komma nicht dargestellt werden. Deshalb wird diese 1 auch als hidden bit bezeichnet.

Die Norm IEEE 754 definiert ein Grunddatenformat für die Darstellung von 32 und 64 bit Gleitkommazahlen. Betrachten wir einmal die Darstellung einer 32 bit Gleitkommazahl (Typ single):

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
  • Bit 0: Vorzeichen v
  • Bit 1-8: Exponent + 127 = e (Darstellung im Zweierkomplement, Verschiebung von 127 ermöglicht einen leichteren Vergleich der Exponenten)
  • Bit 9-31: Mantisse M
  • Zahl: -1v*(1,M)*2e-127
  • Sonderfall 1: Ungültiger Wert NaN (not a number) e=255 und M ist nicht 0.
  • Sonderfall 2: Die Zahl 0: e=0 und M=0

Bei der Darstellung einer 64 bit Gleitkommazahl (double) werden 11 Bit für den Exponenten (mit der Verschiebung 1023) und 52 Bit für die Mantisse verwendet.

Hier nun noch ein paar Rechenregeln für Gleitkommazahlen. Dazu betrachten wir x=Mx*2ex und y=My*2ey:

  • Für ex <= ey: – ansonsten natürlich umgekehrt.
  • Für ex <= ey: – ansonsten natürlich umgekehrt.

Literatur

[1] – Wikipedia: ASCII-Tabelle
[2]Unicode Character Name Index