Wikipedia · einfach zusammengefasst · Stand
Integer (Datentyp)
Als grundlegender arithmetischer Datentyp werden Ganzzahlen von der Hardware fast aller Rechenanlagen nativ unterstützt und sind in nahezu jeder …
Inhalt5 Abschnitte
Grundidee und Bedeutung
Ein Integer ist in der Informatik ein Datentyp, der ganzzahlige Werte speichert. Ganzzahlen gehören zu den grundlegenden arithmetischen Datentypen. Die Hardware fast aller Rechenanlagen unterstützt sie nativ, und sie sind in nahezu jeder Programmiersprache verfügbar. Festkomma- und Gleitkommazahlen müssen dagegen gegebenenfalls softwareseitig emuliert werden.
Meist gibt es mehrere ganzzahlige Datentypen. Sie unterscheiden sich in ihrer Darstellung, ihrer Länge beziehungsweise Wortbreite und darin, ob sie ein Vorzeichen besitzen. Dadurch decken sie unterschiedliche Wertebereiche ab. Der Internationale Standard ISO/IEC 10967 „Language Independent Arithmetic“, veröffentlicht 2001, beschreibt grundlegende Eigenschaften und Rechenoperationen für ganze Zahlen und Gleitkommazahlen unabhängig von Programmiersprache und Computer.
Darstellungen von Ganzzahlen
Ganzzahlen werden normalerweise in einem binären Stellenwertsystem gespeichert. Jede Stelle besitzt einen bestimmten Stellenwert; der Zahlenwert entsteht durch die Summe der Stellenwerte aller gesetzten Bits. Im Binärsystem gibt es nur die Ziffern 0 und 1. Die Stellenwerte entsprechen Zweierpotenzen.
Bei einer 8-Bit-vorzeichenlosen Zahl reichen die Werte von 0 bis 255. Die Zahl 100 wird als 01100100 dargestellt: Die Bits 6, 5 und 2 sind gesetzt, also ergibt sich 64 + 32 + 4 = 100. Durch die Zweierpotenzen besitzt jede Zahl genau eine Darstellungsmöglichkeit.
Für negative Zahlen ist das Zweierkomplement die verbreitetste Darstellung. Dabei erhält das höchstwertige Bit einen negativen Stellenwert. Bei 8 Bit ist dieser Stellenwert −128 statt 128; der Wertebereich reicht daher von −128 bis 127. So wird beispielsweise −7 als 11111001 dargestellt. Addition und Subtraktion funktionieren dabei wie bei vorzeichenlosen Zahlen. Vergleiche, Multiplikation und Division müssen dagegen angepasst werden. Die kleinste negative Zahl besitzt kein entsprechendes positives Gegenstück; deshalb kann die Multiplikation mit −1 dazu führen, dass sich das Vorzeichen nicht ändert.
Beim Einerkomplement wird ebenfalls der Stellenwert der höchstwertigen Stelle umgekehrt, zusätzlich wird 1 abgezogen. Bei 8 Bit reicht der Wertebereich von −127 bis 127. Es gibt zwei Darstellungen der Null: +0 (00000000) und −0 (11111111). Rechenschaltungen für das Einerkomplement sind aufwendiger, weshalb diese Darstellung nicht weit verbreitet ist.
Bei der Vorzeichen-und-Betrag-Darstellung (signed-magnitude representation) werden Vorzeichen und Betrag getrennt gespeichert. Ein Bit bestimmt das Vorzeichen, die übrigen Bits den Betrag. Sie ist für Multiplikation und Division praktisch, weil das Vorzeichen separat behandelt werden kann. Vergleiche, Additionen und Subtraktionen sind im Zweierkomplement jedoch einfacher umzusetzen. Auch hier existieren +0 und −0.
Eine weitere Möglichkeit ist die Speicherung als vorzeichenlose Zahl mit Bias. Ein Bias ist ein fester Wert, der bei der Interpretation der Bitfolge berücksichtigt wird. Für eine n-Bit-Zahl wird meist der Bias 2^{n−1} verwendet; darstellbar sind dann Werte von −2^{n−1} bis 2^{n−1}−1. Diese Darstellung ist unter anderem bei vielen A/D- und D/A-Wandlern üblich und wird auch für Exponenten in IEEE-Gleitkommadarstellungen verwendet. Zwischen Zweierkomplement und einer vorzeichenlosen Darstellung mit Bias lässt sich durch Invertierung des höchstwertigen Bits umschalten. Andere Bias-Werte eignen sich für asymmetrische Signale. Beispiele sind 12-Bit-Kamera-Rohdaten mit Bias −256 und dem Wertebereich −256…3839 sowie 14-Bit-Kamera-Rohdaten mit Bias −1024 und dem Wertebereich −1024…15359.
Bei BCD-Darstellungen (Binary Coded Decimal) wird jede Dezimalziffer binär codiert. Etliche CPUs der 1970er/80er Jahre und auch die meisten Taschenrechner arbeiteten intern mit BCD. Negative Zahlen können dabei als Betrag und Vorzeichen oder als Zehnerkomplement gespeichert werden, etwa −6 = FFFA_{(16)}. Gegenüber Binärarithmetik wurde BCD-Arithmetik durch die Einführung von Multiplikation und Division in Befehlssätzen deutlich langsamer; sie war 3 bis 4 Größenordnungen langsamer. Im 64-Bit-8086-Befehlssatz wurde die entsprechende Unterstützung entfernt. Weiterhin unterstützt werden unter anderem die Umwandlung von 18-stelligen BCD-Zahlen in Gleitkommazahlen doppelter Genauigkeit (double) mit FBLD sowie die umgekehrte Umwandlung mit FBSTP.
Carry-Save-Darstellungen werden für Zwischenberechnungen in CPUs und FPGAs eingesetzt, etwa bei Hardware-Multiplikationen oder komplexen Adressberechnungen wie 8*RBX + RCX + 78h. Ein Zwischenergebnis wird durch zwei Ganzzahl-Vektoren dargestellt: die Überläufe der letzten Addition und die Summen der letzten Addition. Dadurch ist keine Übertrags-Propagation nötig; für die Umwandlung in eine normale Ganzzahl ist aber eine finale Addition erforderlich. Weitere, vor allem historisch beschriebene Darstellungen verwenden beispielsweise die Basen 3, 4, 5, 20 oder 60, negative ganzzahlige Basen, komplexwertige Basen wie 2i, √2i oder i−1, unterschiedliche Basen oder irrationale Basen.
Wortbreiten und Speicherformen
Ganzzahlformate treten in unterschiedlichen Bitbreiten auf. Nativ unterstützte Bitbreiten liegen zwischen 4 und 64 Bit. Historisch wurden auch 12- und 48-Bit-Formate verwendet. Typische Einsatzbereiche sind:
- A/D- und D/A-Wandler: 8 bis 24 Bit
- FPGAs: 18, 25 oder 27 Bit als DSP-Slice-Hardwaremakros oder beliebige Breiten
- ASICs: beliebige Breiten
- Zähler: bis zu 60 Bit
- Signalprozessoren: 24 bis 56 Bit
- Grafikprozessoren: 4 bis 32 Bit
- normale CPUs: 8 bis 64 Bit
Namen mit fester Breite bestehen meist aus einem Vorzeichenindikator und der Bitbreite. Int32 bezeichnet beispielsweise einen vorzeichenbehafteten 32-Bit-Datentyp, UInt128 einen vorzeichenlosen (unsigned) 128-Bit-Datentyp. Die konkreten Namen unterscheiden sich je nach Programmiersprache.
Historisch gewachsene Bezeichnungen folgen keinem einheitlichen Schema. Byte oder char stehen je nach Sprache für 8 Bit mit oder ohne Vorzeichen. Word bezeichnet je nach Rechnerarchitektur 16, 18, 32 oder 36 Bit; daraus sind DWord für „double word“ und QWord für „quad word“ abgeleitet. Weitere Namen sind Int, Integer, SmallInt, short int, LongInt und long long int. Rune bezeichnet die Darstellung von Zeichen.
Bei der Ablage im Speicher muss außerdem die Bytereihenfolge festgelegt sein, also die Reihenfolge, in der die Bits einer Zahl auf einzelne Bytes verteilt werden.
Für Zweierkomplement-Zahlen gelten unter anderem folgende Wertebereiche:
- 8 Bit: signed −128 bis 127, unsigned 0 bis 255
- 16 Bit: signed −32.768 bis 32.767, unsigned 0 bis 65.535
- 32 Bit: signed −2.147.483.648 bis 2.147.483.647, unsigned 0 bis 4.294.967.295
- 64 Bit: signed −9.223.372.036.854.775.808 bis 9.223.372.036.854.775.807, unsigned 0 bis 18.446.744.073.709.551.615
- 128 Bit: signed ungefähr −1,70141·10^{38} bis 1,70141·10^{38}, unsigned 0 bis ungefähr 3,40282·10^{38}
Allgemein reicht der signed-Bereich bei n Bit von −2^{n−1} bis 2^{n−1} − 1, der unsigned-Bereich von 0 bis 2^{n} − 1.
Rechenoperationen und Vergleiche
Die folgenden Verfahren beziehen sich auf das Zweierkomplement. Andere Darstellungen sind meist aufwendiger, weil sie zwei unterschiedliche Darstellungen der 0 besitzen.
Für den Vergleich zweier vorzeichenloser Ganzzahlen A und B wird A − B berechnet. Zusätzlich wird der Übertrag der höchstwertigen Stelle untersucht: Ist der Übertrag 1, ist B größer als A; ist er 0, ist B kleiner oder gleich A. Ergibt die Subtraktion 0, sind A und B gleich. Bei vorzeichenbehafteten Zahlen wird zunächst das höchstwertige Bit gekippt und anschließend wie bei vorzeichenlosen Zahlen verglichen. Ein Gleichheitsvergleich ist besonders einfach; außer bei Einerkomplement und Vorzeichen-und-Betrag reicht ein bitweiser Vergleich.
Bei der Addition werden die Bits paarweise wie bei der schriftlichen Addition verarbeitet. Ein Volladdierer addiert ein Bit aus jeder Zahl und den Übertrag der vorherigen Stelle. Entsteht an der höchstwertigen Stelle ein Übertrag, ist das Ergebnis für den Datentyp zu groß. Bei vorzeichenlosen Zahlen wird dieser Überlauf üblicherweise ignoriert. Bei vorzeichenbehafteten Zahlen hängt das Verhalten von Programmiersprache, Compiler und Umgebung ab: In C ist es undefiniert, in Java wird der Übertrag verworfen.
Für die Subtraktion werden alle Bits von B gekippt und anschließend A, das gekippte B und 1 addiert. Statt B zu subtrahieren, wird also seine Gegenzahl addiert. Entsteht dabei ein Übertrag, war die Subtraktion erfolgreich. Ohne Übertrag liegt das mathematische Ergebnis außerhalb des darstellbaren Bereichs; es gelten die gleichen Folgen wie bei der Addition.
Seit Anfang der 1990er Jahre werden für Multiplikationen optimierte Verfahren wie der Dadda-Tree-Algorithmus eingesetzt. Typische Latenzen liegen bei 3…4 Takten bei 3…6 GHz, also bei 500 bis 1300 ps. Das Ergebnis besitzt meist genauso viele Stellen wie die beiden Operanden einzeln. Der Befehl imul rcx, rbx bedeutet beispielsweise rcx = rcx * rbx bei 64 Bit = 64 Bit * 64 Bit. Für den Low-Teil spielt es keine Rolle, ob die Operanden signed oder unsigned sind, weil sich die Darstellungen im Wert um 2^{64} unterscheiden. Für Langzahlarithmetik gibt es unter anderem imul rbx für ein signed-Ergebnis und mul rbx für ein unsigned-Ergebnis; gemischte signed-unsigned-Multiplikationen gibt es im Allgemeinen nicht.
Bei der Division werden seit Anfang der 1990er Jahre optimierte Algorithmen verwendet, die bis zu 6 Bit in einem Takt bestimmen.
Überlauf, Verwendung und verwandte Typen
Ein arithmetischer Überlauf entsteht, wenn ein berechneter Wert außerhalb des Wertebereichs eines Integer-Datentyps liegt. Bei einer vorzeichenlosen 8-Bit-Variablen wird aus 255 + 1 der Wert 0. Bei einer vorzeichenbehafteten 8-Bit-Zahl im Zweierkomplement wird aus 127 + 1 entweder −128 oder es tritt undefiniertes Verhalten auf. Das hängt von CPU, Programmiersprache, Compiler, Compiler-Optionen und Laufzeitumgebung ab.
Ganzzahlen werden vielseitig verwendet:
- als Werte, mit denen gerechnet wird;
- als Nummern oder Kennungen, etwa für Fehlernummern, Fehlercodes und Datenbank-IDs;
- als Bitmenge, also zur Darstellung einer Teilmenge aus einer kleinen Anzahl von Objekten, beispielsweise möglicher Zustände in nichtdeterministischen Automaten.
Verwandte Datentypen sind Aufzählungstypen, die eine Menge unterscheidbarer Objekte definieren und üblicherweise als Ganzzahl gespeichert werden. Festkommazahlen funktionieren in vieler Hinsicht analog zu Ganzzahlen: Das Komma beeinflusst Vergleich, Addition und Subtraktion nicht. Bei Multiplikation und Division muss das Komma verschoben und das Ergebnis gerundet werden.
Gleitkommazahlen können bei gleichem Speicherbedarf einen größeren Zahlenbereich abdecken. Dafür können sie nicht alle ganzen Zahlen innerhalb dieses Bereichs darstellen. Wegen notwendiger Rundungen gelten bei Gleitkommarechnungen viele Rechenregeln, darunter Assoziativgesetz und Distributivgesetz, nicht allgemein.
