INTEGER - Zahlensysteme

[ < ] [ globale Übersicht ] [ Kapitelübersicht ] [ Stichwortsuche ] [ > ]

3.4.1 INTEGER-Zahlensysteme:

Am besten stellt man Integerzahlen in Binärschreibweise der Form: d_N-1d_N-2...d₂d₁d₀ dar. Diese Zahlen können leicht vom Computer verarbeitet, und auch mit folgender Formel ins Dezimalsystem umgerechnet werden:

$\begin{equation} \label{eqn:01.1} d_{N-1} d_{N-2} \cdots d_{2} d_{1} d_{0} \quad\doteq\quad \sum_{j=0}^{N-1} d_{j}\cdot 2^{j}, \qquad d_j \in \{0,1\}. \end{equation}$
Beispiele:

0000...0000 $\doteq$ 0
0000...0001 $\doteq$ 1
$\cdots$
1111...1111 $\doteq$ 2^N - 1

Damit werden alle positiven Zahlen von 0 bis 2^N- 1 dargestellt. N ist Element der natürlichen Zahlen und gibt die Anzahl der Binärziffern an (d₀ bis d_N-1). Man kann auch sagen, es gibt die Anzahl der Bits an, die verwendet werden, um eine Zahl darzustellen.
Man nennt jene Speicherzelle, in der genau eine binäre Ziffer abgespeichert werden kann, ein Bit. Dieser Name leitet sich von "binary digit" ab.
Warum gerade 2^N - 1 wird sich vielleicht jemand fragen. Eine Stelle im Binärsystem entspricht ja einem Bit, mit dem man 2 Zahlen darstellen kann, und zwar 0 und 1. Mit 2 Bit kann man 4 (= 2²) Zahlen darstellen: 00₂ $\doteq$ 0₁₀, 01₂ $\doteq$ 1₁₀, 10₂ $\doteq$ 2₁₀ und 11₂ $\doteq$ 3₁₀. Mit N Bit kann man 2^N Zahlen darstellen. Nun kann man sich leicht ein einfaches Beispiel überlegen:
Angenommen N = 3. Dann ist die kleinste darstellbare Binärzahl gleich 000. Ins Dezimalsystem umgerechnet ergibt das die Zahl 0. Die größte darstellbare Binärzahl 111 ins Dezimalsystem umgerechent ergibt die Zahl 7, und 7 = 2 * 2 * 2 - 1 = 2³- 1 = 8 - 1. Das sind also 2³ = 8 Zahlen, die dargestellt werden können.
Bei 32-Bit-Zahlen können also maximal 2³² $\doteq$ 4294967296 (in Worten: über 4Mrd.) Zahlen dargestellt werden.
Es müssen auch negative Zahlen darstellbar sein. Das geschieht auf 3 Arten: Getrennte Codierung des Vorzeichens, Einerkomplement- und Zweierkomplementdarstellung. Folgende Variablen werden für die Zahlendarstellungen verwendet: d_j, v $\in$ {0,1}, j $\in$ N, v = Vorzeichen.

Getrennte Codierung des Vorzeichens:

Das Vorzeichen v wird dazu verwendet um zu zeigen, ob die angegebene Binärzahl d_N-2...d₀positiv ist, das ist der Fall bei v = 0 oder negativ, bei v = 1.

$vd_{N-2}d_{N-3} \cdots d_2 d_1 d_0 \quad\doteq\quad (-1)^v \sum\limits_{j=0}^{N-2}d_j\cdot2^j.$
Man erhält damit die ganzen Zahlen [-(2^N-1- 1), 2^N-1- 1] $\subset$ Z:

0000...0000 $\doteq$ 0 1000...0000 $\doteq$ -0

0000...0001 $\doteq$ 1 1000...0001 $\doteq$ -1

$\cdots$ $\cdots$

0111...1111 $\doteq$ 2^N-1 - 1 1111...1111 $\doteq$ -(2^N-1 - 1)

Wie man sieht, ist die Codierung der Zahl 0 nicht eindeutig (±0). Die größte darstellbare Zahl hat nur mehr den Wert 2^N-1- 1, und die kleinste den Wert -(2^N-1- 1). 2^N-1 kommt daher, da die 1.Stelle das Vorzeichen repräsentiert, und daher ein Bit weniger zur Darstellung der eigentlichen Zahl zur Verfügung steht.

Einerkomplement:

Formel zur Darstellung der positiven Zahlen:
Dazu wird die Formel (1.1) verwendet.

Formel zur Darstellung der negativen Zahlen:

$\overline{x}=\sum\limits_{j=0}^{N-1}(1-d_j)\cdot2^j$

Man erhält wieder die ganzen Zahlen [-(2^N-1- 1), 2^N-1- 1] $\subset$ Z:

0000...0000 $\doteq$ 0 1111...1111 $\doteq$ -0

0000...0001 $\doteq$ 1 1111...1110 $\doteq$ -1

$\cdots$ $\cdots$

0111...1111 $\doteq$ 2^N-1 - 1 1000...0000 $\doteq$ -(2^N-1 - 1)

Die Codierung der Zahl 0 ist auch hier nicht eindeutig (±0).
Die negativen Zahlen, dargestellt im rechten Teil des obigen Beispiels, unterscheidet sich von den positiven im linken Teil dadurch, daß Nullen und Einser vertauscht sind. Dieses Komplement erhält man durch (1 - d_j), da 1 - 0 = 1 und 1 - 1 = 0 ist. Positive und negative Zahlen können am führenden Bit (d_N-1) unterschieden werden.

Zweierkomplementdarstellung:

Formel zur Darstellung der positiven Zahlen:
Dazu wird wieder die Formel (1.1) verwendet, wie auch beim Einerkomplement.

Formel zur Darstellung der negativen Zahlen:

$\overline{\overline{x}} = 1+\sum\limits_{j=0}^{N-1}(1-d_j)\cdot2^j$

Beispiele:

0000...0000 $\doteq$ 0

0000...0001 $\doteq$ 1 1111...1110 $\doteq$ -1

$\cdots$ $\cdots$

0111...1111 $\doteq$ 2^N-1 - 1 1000...0001 $\doteq$ -(2^N-1 - 1)

1000...0000 $\doteq$ -2^N-1

Die Codierung der Zahl 0 ist eindeutig, das wird durch das 1 plus der Summe erreicht, allerdings ist jetzt der Zahlenbereich [-2^N-1, 2^N-1- 1] unsymmetrisch.
Die Binärzahlen und deren Wert unterscheiden sich beim Einer- und Zweierkomplement um eine Binärziffer bzw. um den Wert 1. Daher kann man auch die einzelnen Bits mittels des Einerkomplements umwandeln und anschließend 1 addieren.
Eine andere Alternative zur Umrechnung in Zweierkomplement ist, die binären Ziffern von rechts nach links bis zur ersten 1 einschließlich zu kopieren und die restlichen Ziffern zu komplementieren. Positive und negative Zahlen können wieder am führenden Bit unterschieden werden.

Beispiel:

Intel:Die Intel-Mikroprozessoren haben Zweierkomplement-Codierungen der ganzen Zahlen mit Formatbreiten N = 16, 32 und 64 Bits, die als short integer, word integer und long integer bezeichnet werden. Der Bereich der Word-integer-Zahlen ist [-2³¹,2³¹ - 1] = [-2.147.483.648, 2.147.483.647] $\subset$ Z.

Datentyp INTEGER:

Integer-Zahlen sind Teilmengen der ganzen Zahlen. Operationen, die auf Integer-Zahlen angewendet werden können sind: +, -, *, div, mod und abs. i_min $\le$ 0 ist die kleinste Zahl und i_max > 0 ist die größte ganze Zahl. Zum Beispiel i_min = 0 entspricht die Menge der nichtnegativen ganzen Zahlen. Bei einer symmetrische Codierung entspricht i_min = -i_max, andernfalls spricht man von einer unsymmetrsichen Codierung. Im besonderen gilt i_min = -(i_max + 1) bei der Codierung negativer Zahlen durch das Zweierkomplement:
i_min = -2^N-1, i_max = 2^N-1 - 1:
i_min = -((2^N-1- 1) + 1) = -2^N-1

Beispiel:

C: Auf HP-Workstation-Implementierungen der Programmiersprache C gibt es folgende INTEGER-Zahlensysteme:

Datentyp	i_min	i_max
unsigned short int	0	65 535
short int	-32 768	32 767
unsigned int	0	4 294 967 295
int	-2 147 483 648	2 147 483 647
unsigned long int	0	4 294 967 295
long int	-2 147 483 648	2 147 483 647

Die Datentypen int und long int sind beide mit einer Formatbreite N = 32 Bit codiert. Der Datentyp long int hat somit keine größere Zahlenmenge als der Datentyp int.

Modulo-Arithmetik:

Wenn der Zahlenbereich [i_min , i_max ] nicht ausreicht (integer overflow), dann kommt entweder eine Fehlermeldung, oder die Zahl wird Modulo gerechnet.
x_wrap $\in$ [i_min , i_max ],
x_wrap $\equiv$ x mod m,
m := i_max - i_min + 1.
Da i_min kleiner gleich 0 ist, ist -i_min positiv. Der Wert von m ist die Anzahl der Zahlen im Wertebereich [i_min, i_max]. Die Summe der Absolutbeträge von i_min und i_max ergeben nur 2^N-1 Zahlen, da die Zahl Null nicht miteingerechnet wurde. Darum muß man am Schluß der Berechnung von m noch 1 dazuzählen.

Beispiele:

Zweierkomplement: i_min = -2^N-1, i_max = 2^N-1 - 1
m : = (2^N-1-1) - (-2^N-1) + 1 = 2*2^N-1(-1+1) = 2*2^N-1 = 2^N
C: In der im obigen Beispiel behandelten C-Implementierung ist die INTEGER-Arithmetik in allen Fällen eine Module-Arithmetik; eine Umstellung auf Overflow-Modus ist weder durch Maßnahmen in den C-Programmen noch auf der Ebene des Betriebssystems möglich.

[ < ] [ globale Übersicht ] [ Kapitelübersicht ] [ Stichwortsuche ] [ > ]

0000...0000 $\doteq$ 0	1000...0000 $\doteq$ -0
0000...0001 $\doteq$ 1	1000...0001 $\doteq$ -1
$\cdots$	$\cdots$
0111...1111 $\doteq$ 2^N-1 - 1	1111...1111 $\doteq$ -(2^N-1 - 1)

0000...0000 $\doteq$ 0	1111...1111 $\doteq$ -0
0000...0001 $\doteq$ 1	1111...1110 $\doteq$ -1
$\cdots$	$\cdots$
0111...1111 $\doteq$ 2^N-1 - 1	1000...0000 $\doteq$ -(2^N-1 - 1)