Datentypen im Detail
T$

Um die von heutigen Prozessoren verwendeten Datentypen möglichst effizient nutzen zu können braucht man einige Hintergrundinformationen über ihre mathematische und technische Realisierung. Insbesondere bei der Assemblerprogrammierung, aber auch in C(++) oder Pascal ist dieses Wissen unerläßlich zur Erstellung leistungsfähiger Programme.

Mathematische Grundlagen

Potenzen zur Basis 2 werden als a = 2^b geschrieben. Die Zahl b wird Exponent genannt.

Die folgenden Formeln sollte man kennen:

• a = 2^b entspricht b = ld(a).
  Dabei ist ld(...) der Logarithmus zur Basis 2.
• 2⁰ = 1,
  die Darstellung der Zahl 1 als Zweierpotenz.
• 2^-b = 1/2^b und ld(1/a) = -ld(a).
  Bedeutung: Mit Potenzen lassen sich auch Zahlen zwischen 0 und 1 angeben.
• 2^a * 2^b = 2^a+b und ld(a*b) = ld(a) + ld(b).
  Bedeutung: Die Multiplikation von Potenzen entspricht der Addition der Exponenten.
• 2^a / 2^b = 2^a-b und ld(a/b) = ld(a) - ld(b).
  Bedeutung: Die Division von Potenzen entspricht der Subtraktion der Exponenten.

Desweiteren ist mit [a...b] eine Zahl zwischen a und b gemeint, a und b einschließlich.

Technische Grundlagen

Digitalrechner speichern Informationen als Bitfolge, in der jedes Bit entweder den Wert "0" oder den Wert "1" enthält. Gängige Datengrößen heutiger CPUs sind 8 Bit (Byte), 16 Bit (Word), 32 Bit (DWord) und 64 Bit (QWord). Mit n Bits lassen sich maximal 2ⁿ verschiedene Informationen speichern, die Bits werden Bit n-1, Bit n-2, ..., Bit 1, Bit 0 genannt. Dabei ist Bit n-1 das höchstwertigste Bit (MSB) und Bit 0 das am wenigsten bedeutendste Bit (LSB).

Welche Information damit dargestellt wird hängt allein von der aktuellen Verwendung ab, auf Hardwareebene gibt es keine weitere Unterscheidung außer der Datengröße. Im Allgemeinen kann man auf die größeren Datentypen auch byteweise zugreifen.

Ganzzahlen (Char, Integer)

Mit n Bits kann man eine Ganzzahl in der Form
Bit_n-1 * 2^n-1 + Bit_n-2 * 2^n-2 + ... + Bit₁ * 2¹ + Bit₀ * 2⁰
speichern. Die niedrigste darstellbare Zahl ist hier 0, die größte Zahl 2ⁿ - 1. Der Wertebereich ist also [0...2ⁿ-1].

Dabei werden für eine Stelle im Dezimalsystem ld(10) = ~3,322 Bits benötigt. Mit 16 Bit kann man also maximal 16 / 3,322 = 4,8 Dezimalstellen darstellen, für eine 10-stellige Dezimalzahl werden mindestens 3,322 * 10 = 33,22 Bits benötigt. In der Praxis rundet man die Werte entsprechend auf bzw. ab oder verzichtet auf einen Teil des Wertebereiches.

Beim Verrechnen zweier Zahlen mit maximal n bzw. m Bits ergeben sich somit folgende Konsequenzen:

• Bei der Addition zweier Zahlen wird maximal ein weiteres Bit im Ergebnis benötigt:
  [0...2ⁿ] + [0...2ⁿ] = [0...2 * 2ⁿ] = [0...2ⁿ⁺¹]
• Die Substraktion benötigt keine weiteren Bits für das Ergebnis:
  [0...2ⁿ] - [0...2ⁿ] = [0...2ⁿ]
• Die Multiplikation erfordert für das Ergebnis soviele Bits wie beide Zahlen zusammen:
  [0...2ⁿ] * [0...2^m] = [0...2ⁿ * 2^m] = [0...2^n+m]
• Für die Division werden keine weiteren Bits benötigt. Der Divisionsrest liegt bei [0...2^m-1]:
  [0...2ⁿ] / [1...2^m] = [0...2ⁿ]
• Eine Division mit einer mindestens m-bittigen Zahl reduziert die Anzahl benötigter Bits um m:
  [0...2ⁿ] / [2^m...2ⁿ] = [0...2^n-m]

Festkommazahlen, skalierte Ganzzahlen

Indem man die Bits nicht als Bit_n-1...Bit₀ interpretiert, sondern als Bit_n-1+s...Bit_s mit s<0 kann man auch Kommazahlen abspeichern. Wählt man s>0, so kann man die Schrittweite zwischen 2 Zahlen vergrößern. Mathematisch verbirgt sich dahinter eine Multiplikation mit 2^s, technisch eine Verschiebung um s Bit. Die Zahl ist somit folgendermaßen kodiert:
Bit_n-1 * 2^n-1 * 2^s + Bit_n-2 * 2^n-2 * 2^s + ... + Bit₁ * 2¹ * 2^s + Bit₀ * 2⁰ * 2^s.

Dadurch ergeben sich folgende Rechenregeln bei der Verschiebung um s Bits:

• Addition und Substraktion wie bei Ganzzahlen:
  [0...2ⁿ*2^s] + [0...2ⁿ*2^s] = [0...2ⁿ⁺¹*2^s]
  [0...2ⁿ*2^s] - [0...2ⁿ*2^s] = [0...2ⁿ*2^s]
• Die Multiplikation erfordert für das Ergebnis soviele Bits wie beide Zahlen zusammen, zusätzlich ist das Ergebnis um s Bits verschoben, also um 2^s zu groß:
  [0...2ⁿ*2^s] * [0...2^m*2^s] = [0...2^n+m*2^2s]
• Für die Division werden keine weiteren Bits benötigt, das Ergebnis ist um s Bits verschoben, also um 2^s zu klein. Der Divisionsrest liegt bei [0...(2ⁿ-1)*2^s] und ist nicht verschoben:
  [0...2ⁿ*2^s] / [1...2^m*2^s] = [0...2ⁿ]

Festkommazahlen und skalierte Ganzzahlen werden häufig bei Zusatzhardware wie Grafik- und Soundkarten verwendet, auf den gängigen CPUs muß man sie jedoch durch Verschieben der Bits von Ganzzahlen realisieren.

Das Vorzeichen

Es gibt mehrere Arten, ein Vorzeichen zu realisieren:

• Für die Speicherung des Vorzeichens wird das oberste Bit verwendet.
  Vorteil: Einfache Multiplikation, Division, Negation, Betrag.
  Nachteil: Aufwendige Addition und Substraktion, die 0 tritt doppelt als +0 und -0 auf.
• Addition eines Offsets (Bias): [-2^n-1...2^n-1-1] + 2^n-1 = [0...2ⁿ-1]
  Außer bei Negation und Betrag ziemlich aufwendig.
• Einerkomplement: Negative Werte werden durch invertierte Bits realisiert, das oberste Bit speichert, ob der Wert negativ ist. Außer bei Negation und Betrag ziemlich aufwendig, heutzutage kaum mehr gebräuchlich. Zudem tritt auch hier die 0 als +0 und -0 auf.
• Zweierkomplement: [0...2ⁿ-1] wird unverändert gespeichert, [-2^n-1...-1] wird auf [2^n-1...2ⁿ-1] = 2ⁿ - [2^n-1...1] abgebildet.
  Da das Bit für 2ⁿ nicht existiert, kann man dies auch als 0 - [2^n-1...1] lesen: Die Zweierkomplementdarstellung stellt negative Zahlen so dar, als hätte man die Zahl Bit für Bit von der 0 abgezogen und den Überlauf ignoriert.
  Vorteil: Einfache Addition, Subtraktion, Negation, Betrag.
  Nachteil: Etwas aufwendigere Multiplikation und Division.

Alle Arten haben eine Eigenschaft gemeinsam: Das Vorzeichen läßt sich direkt im obersten Bit ablesen. Für Ganzzahlen hat sich heutzutage das Zweierkomplement durchgesetzt. Um den Wertebereich einer Zweierkomplementzahl zu vergrößern muß man nur die neu dazugekommenen Bits mit dem MSB füllen. Ist bekannt, daß die Zahl positiv ist genügt es also, die neuen Bits auf 0 zu setzen.

Zweierkomplementzahlen lassen ebenso wie vorzeichenlose Zahlen als Festkommazahlen bzw. skalierte Ganzzahlen verwenden. Zu beachten ist aber bei der Multiplikation, daß im Ergebnis die beiden obersten Bits meist identisch sind, so daß hier ein Bit verloren geht. Abhilfe: Als kleinste Zahl maximal -2^n-1 + 1 verwenden und mit 2*Ergebnis weiterrechnen.

Gleitkommazahlen (Float, Double)

Eine Gleitkommazahl wird als Vorzeichen * 2^Exponent * Mantisse dargestellt. Der Exponent ist eine Ganzzahl, die Mantisse eine Festkommazahl zwischen 0 und 2

Nach dem IEEE-Standard werden Gleitkommazahlen einfacher Genauigkeit (Floats) als 1 Bit Vorzeichen, 8 Bit Exponent und 23 Bit Mantisse gespeichert. Bei der doppelten Genauigkeit (Double) ist der Exponent 11 Bits groß und die Mantisse 52 Bits lang.

Die Mantisse wird normalisiert gennant, wenn sie zwischen 1 und 2 liegt, das oberste Bit also 1 ist. Dieses Bit wird nicht mitgespeichert, so daß intern die Mantisse 24 bzw. 53 Bit groß ist. Der Exponent wird mit einem Offset gespeichert (biased exponent).

Einige Werte haben besondere Bedeutung:

• Exponent = 0 und Mantisse = 0 stellt die Zahl +/-0 dar.
• Exponent = 0 und Mantisse != 0 markiert Zahlen, die so klein sind daß sie nicht normalisiert werden können.
• Exponent = FF/7FF und Mantisse = 0 kennzeichnet +/- unendlich.
• Exponent = FF/7FF und Mantisse != 0 wird als NaN (Not a Number) bezeichnet: Das Ergebnis ist undefiniert.

Ein häufiger Irrtum besteht darin, daß Gleitkommazahlen für genauer gehalten werden als Ganzzahlen und Festkommazahlen. Der Vorteil von Gleitkommazahlen liegt jedoch woanders: Eine exakte Rechnung mit Ganz- oder Festkommazahlen benötigt schnell große Mengen an verfügbaren Bits, so daß das Ergebnis nicht mehr in die von der CPU unterstützten Datentypen paßt und der Algorithmus extrem aufwendig werden kann oder das Ergebnis gerundet werden muß.

Hier bieten Gleitkommazahlen eine Alternative: Die Genauigkeit ist bei derselben Bitmenge geringer, aber dafür konstant (jedenfalls solange die Zahlen normalisierbar sind).

Dadurch ergeben sich folgende Konsequenzen:

• Bei der Addition und Subtraktion werden beide Operanden zuerst auf den gleichen Exponenten gebracht, danach wird wie gewohnt addiert bzw. subtrahiert. Anschließend wird das Ergebnis normalisiert. Dieses Verfahren hat eine auffällige Eigenschaft: Je weiter die Exponenten auseinanderliegen, desto ungenauer ist das Ergebnis. Ist die Differenz der Exponenten größer als die Zahl der Bits in der Mantisse, besteht das Ergebnis allein aus dem betragsmäßig größeren Operand!
• Bei der Multiplikation und Division werden im wesentlichen die beiden Exponenten addiert bzw. subtrahiert und die Mantissen mulipliziert bzw. dividiert. Nach der Normalisierung ist die Genauigkeit des Ergebnisses identisch mit der Genauigkeit der Operanden.

Gleitkommazahlen sind somit ideal, wenn oft skaliert (= SHL/SHR), multipliziert oder dividiert werden muß. Für Additionen und Subtraktionen sind sie Ganzzahlen und Festkommazahlen mit gleicher Bitzahl unterlegen.

Symbolische Zahlen

Viele Zahlen wie Pi, e, viele Wurzeln, ... lassen sich nicht mit endlich vielen Stellen darstellen und sind somit nicht als exakter Wert in binärer Form darstellbar. Aber auch Brüche gehören dazu, selbst Brüche die im Dezimalsystem nur wenige Stellen brauchen wie 0,2 lassen sich nicht mit endlich vielen Bits darstellen.

Jedoch kann jede binärcodierte Zahl als endliche Dezimalzahl dargestellt werden, indem man sie als Bruch a/2^b schreibt. Die Dezimalzahl erhält man, indem man mit 5^b erweitert: a*5^b / 10^b. Folgerung: Jede Zahl, die sich nicht als Bruch mit einer Zweierpotenz im Nenner darstellen, läßt kann nicht als endliche Binärzahl dargestellt werden.

Ein möglicher Ausweg besteht darin, die Dezimalzahl direkt zu verwenden, indem man jeweils 4 Bit für eine Dezimalstelle verwendet. Entstehende Rundungsfehler sind mit denen im Dezimalsystem identisch, so daß diese Darstellung bei Finanzsoftware sehr verbreitet ist.

Bruchzahlen können als Paar zweier Ganzzahlen realisiert werden, wenn man die Rechenregeln für Brüche auf diese Paare anwendet. Desweiteren kann man auch mit symbolischen Werten (Pi, e, beliebige Variablen oder Konstanten) rechnen, wobei man die symbolischen Werte während der gesamten Rechnung mitschleift. Dies ist aber nur sinnvoll, wenn der symbolische Wert am Ende auch mitausgegeben wird.

Little und BigEndian

Im Speicher werden die Typen Word, DWord und QWord als eine Folge von 2,4 und 8 Bytes abgelegt. Je nach Prozessor aber in unterschiedlicher Reihenfolge:

• Little Endian:
  Das erste Byte speichert die Bits 2^n-1..2^n-8, das folgende die Bits 2^n-9..2^n-16, das letzte die Bits 2⁷..2⁰.
  Vorteil: Einfachere Konvertierung nach Hex oder Binär, da die Reihenfolge im Speicher der Textdarstellung entspricht.
• BigEndian:
  Das erste Byte speichert die Bits 2⁰..2⁷, das zweite die Bits 2⁸..2¹⁵, das letzte die Bits 2^n-8..2^n-1
  Vorteil: Die direkte Adresse des Bytes mit dem n-ten Bit berechnet sich immer als Basisaddresse + n/8.

Da man aber meist direkt Words, DWords oder QWords einliest, ist der Unterschied in der Praxis meist ohne Bedeutung. Wichtig wird er nur, wenn man direkt einzelne Bytes eines Wertes im Speicher manipulieren will oder wenn Daten größer als Bytes zwischen zwei verschiedenen Systemen ausgetauscht werden: x86-CPUs verwenden das BigEndian-Format, 68xxx-CPUs LittleEndian.

Gepackte Formate (Vektoren, PackedPixel, ...)

Words, DWords und QWords können auch verwendet werden, um mehrere unabhängige Bytes, Words oder DWords gleichzeitig zu verarbeiten. Idealerweise steht dafür ein geeigneter Befehlssatz wie MMX bereit, aber auch die normalen Ganzzahloperationen eignen sich dafür. Logische Operationen wie NOT, AND, OR, XOR funktionieren ohne weiteres, bei der Addition, Subtraktion, Multiplikation und Division muß man jedoch Vorkehrungen gegen über- bzw. unterlaufende Bits treffen.

Arrays und Zeiger(Pointer)

Ein Zeiger (Pointer, p_XXX, ...) ist nichts weiter als eine Variable, die eine Speicheradresse (also eine Ganzzahl) enthält. Bei einem Zugriff mittels einem Zeiger benutzt die CPU diese Zahl, um die Variable an dieser Adresse auszulesen.

Viele Programmiersprachen unterstützen typisierte Zeiger, die dem Compiler mitteilen, auf welchen Datentyp zugegriffen wird. Desweiteren wird bei der Erhöhung um 1 der Zeiger nicht 1, sondern die Größe des Datentyps erhöht.

Auf Assemblerebene sind hier Addressierungsmodi wie mov eax,[4*ebx] oder add [2*edi],eax vergleichbar.

Einfache, eindimensionale Arrays können direkt ab einer beliebigen Speicheradresse abgelegt werden. An dieser Adresse liegt üblicherweise das Element mit Index 0. Die folgenden Elemente findet sich an der Adresse von Element[0] + (Größe_der_Elemente_in_Bytes * Elementnummer). Mit einem typisierten Zeiger auf den Arrayanfang kann man somit auf die Elemente zugreifen, indem man einfach den Elementindex zum Zeiger hinzuaddiert und das Ergebnis zum Zugriff verwendet.

Mehrdimensionale Arrays können direkt auf eindimensionale Arrays abgebildet werden, für Arrays mit nichtnumerischen Indexen oder variabler Größe sind aufwendigere Techniken nötig.

T$
http://www.deinmeister.de