Natürliche Zahlen, das sind die Zahlen 1, 2, 3, 4, … – je nach Autor ist auch die 0 eine natürliche Zahl. Die Menge der natürlichen Zahlen wird in der Mathematik mit \(\mathbb{N}\) bezeichnet. Um die 0 explizit als natürliche Zahl in Betracht zu ziehen, schreiben viele Autoren \(\mathbb{N}_0\). Ganze Zahlen erweitern die Menge der natürlichen Zahlen um deren jeweils negatives Gegenstück. Die Rolle der 0 ist hierbei unzweifelhaft. Niemand bestreitet, dass es sich dabei um eine ganze Zahl handelt. Die Menge der ganzen Zahlen bezeichnen wir mit \(\mathbb{Z}\).
In fast allen Programmiersprachen scheinen die ganzen Zahlen so zu funktionieren, wir wir das aus dem Alltag kennen. Nur gelegentlich werden wir enttäuscht. Ursache ist dann regelmäßig einer sogenannter Overflow Error. – Ich habe dazu einen interessanten Beitrag geschrieben, der Dir die modulare Arithmetik erläutert. Anhand dessen kannst Du die Ergebnisse im Falle eines Überlauffehlers verstehen.
Betrachten wir die folgende Zeichenfolge: 123. So, wie wir in der Regel konditioniert sind, interpretieren wir diese Zeichenfolge sofort als die Zahl „einhundertdreiundzwanzig“. Wie kommen wir aber dazu? — Blitzschnell, ohne uns dessen bewusst zu werden, führen wir die folgende Rechnung aus, dekodieren die Zeichenfolge und ermitteln deren Wert:
\[ 3 \cdot 10^{0}+2 \cdot 10^{1}+1 \cdot 10^{2} = 3 \cdot 1+2 \cdot 10+1 \cdot 100 = 123 \]Das heißt, wir wissen um den Stellenwert, der mit jeder Position der einzelnen Ziffern in der Zeichenfolge verbunden ist, die wir als Zahl interpretieren. Das 10er-System (Dezimalsystem, Basis 10) ist das System, in dem wir üblicherweise Zahlen notieren und welches wir im Sprachgebrauch verwenden.
Natürliche Zahlen
Der digitale Computer benutzt – das sollte Dir nicht fremd sein – ein duales System (Basis 2) zur Kodierung von Zahlen. Wir notieren diese mit Nullen und Einsen. Betrachten wir: 110. Das könnte der Polizeinotruf sein. Als Dualzahl im Computer repräsentiert dies aber die dezimale Zahl 6.
Wie kommen wir auf 6? — Nun, wir machen genau das, was wir vorher bereits mit unserer 123 getan haben. Allerdings führen wir die Berechnung nun mit der Basis 2 aus.
\[ 0 \cdot 2^{0} + 1 \cdot 2^{1} + 1 \cdot 2^{2} = 0 \cdot 1 + 1 \cdot 2 + 1 \cdot 4 = 6 \]Sei \(w\) der dezimale Wert einer dualen Zeichenfolge, die als positive Ganzzahl ausgewertet werden soll. \(d_i\) seien die einzelnen Digits, also die Nullen und Einsen, aus denen die Folge besteht. Dann können wir die Wertermittlung wie folgt formulieren: \[ w = \sum_{i=0}^{n-1}{d_{i} \cdot 2^{i}} \]
Niemand gibt jedoch 110 ein, wenn er eine 6 meint. Im Gegenteil geben wir tatsächlich 6 (auch wenn Python andere Notationen, auch die binäre, unterstützt) ein. Die Umwandlung in das interne Format übernimmt der Computer. Würden wir 110 eingeben, würde dieser das als die dezimale Zahl 110 interpretieren, so wir ihm keine anderslautende Anweisung geben. Schauen wir uns also an, wie wir aus einer Dezimalzahl die duale Codierung ermitteln.
Wir wissen, dass wir unsere Dezimalzahl irgendwie in eine Summe von 2er-Potenzen zerlegen müssen. Kommt eine bestimmte 2er-Potenz vor, notieren wir eine 1, ansonsten eine 0. Herumprobieren kann ziemlich nervenaufreibend sein. Versuchen wir es also systematischer!
Teilen wir eine uns gegebene Dezimalzahl ganzzahlig durch 2, dann ist sie entweder ohne Rest teilbar oder es verbleibt ein Rest von 1. Ist der Rest 1, so schreiben wir für die Binärdarstellung eine 1, sonst eine 0. Mit dem ganzzahligen Teiler, den wir bei der Restwertdivision erhalten haben, führen wir das Spielchen fort, bis wir ihn auf 0 transformiert haben. Auf diese Weise ermitteln wir die einzelnen Digits von rechts nach links, errechnen also erst die Wertigkeit \(2^0\), dann \(2^1\) und so weiter.
Während die dezimale Wertermittlung einer Dualzahl noch halbwegs im Kopf zu bewerkstelligen ist, ist die umgekehrte Richtung, die binäre Kodierung zu ermitteln, schon weniger bequem. Zwar können wir in Python den Binärcode einer dezimalen Ganzzahl ganz einfach mittels einer entsprechenden Ausgabeformatierung darstellen, ich möchte den vorgestellten Algorithmus aber gerne auch als Programm demonstrieren. Das verarbeitet nicht-negative Ganzzahlen und ermittelt deren binäre Kodierung.
def dez2bin(x: int) -> str:
binstr = ""
while x > 0:
if x % 2 == 1:
binstr = "1" + binstr
else:
binstr = "0" + binstr
x = x // 2
return binstr
Ganze Zahlen
Viele Programmiersprachen bieten unterschiedliche Datentypen für ganze Zahlen mit und ohne Vorzeichen. In Python sind alle Datentypen für Zahlen mit einem Vorzeichen behaftet, also auch die ganzen Zahlen (int). Außerdem unterscheidet Python nicht bezüglich unterschiedlicher Wertebereiche, wie beispielsweise Java oder C++.
Wir erweitern also unseren Zahlenhorizont von \(\mathbb{N}_0\) auf \(\mathbb{Z}\). Unsere erste Überlegung gilt dem Vorzeichen. Wo und wie wird es gespeichert? – Das Vorzeichen findet seinen Platz in dem jeweils ganz links stehenden Bit einer Dualzahl. Bei einem Datentyp, der nur ein Byte Speicherplatz beansprucht, ist dies das Bit Nummer 7, wenn wir von rechts nach links, mit 0 beginnend, zählen. Ist das Bit gesetzt, ist es also 1, so signalisiert dies ein negatives Vorzeichen. Ist das Bit dagegen 0, haben wir es mit einer positiven Ganzzahl zu tun. Da dieses höchstwertige Bit zur Kodierung des Vorzeichens verwendet wird, steht es uns nicht mehr zur Kodierung der Ziffern einer Zahl zur Verfügung – logisch. Damit ergeben sich, ein wenig voraus gegriffen, folgende Wertebereiche für die, zum Beispiel in Java standardmäßig definierten Ganzzahlen, die ein Vorzeichen besitzen, und in folgender Tabelle dargestellt sind.
| Datentyp | Wertebereich | Bit |
|---|---|---|
byte | -128 .. 127 | 8 |
short | -32768 .. 32767 | 16 |
int | -2147483648 .. 2147483647 | 32 |
long | -9223372036854775808 .. 9223372036854775807 | 64 |
Python unterscheidet ganze Zahlen nicht nach Größen, die von der Anzahl verfügbarer Bits abhängen. In Python können ganze Zahlen nahezu beliebig groß bzw. klein werden. In der Tat kann in Python eine ganze Zahl aus bis zu 4300 Ziffern bestehen. Eine Grenze gibt es also schon. Python beherrscht Langzahlarithmetik. Ich komme später darauf zurück.
Um uns jetzt nicht die Finger wund zu schreiben, betrachten wir einen imaginären Datentyp, der uns vier Bit zur Darstellung vorzeichenbehafteter Ganzzahlen spendieren soll. Das höchste Bit signalisiert das Vorzeichen. Bei positiven Zahlen soll es 0 sein.
Die folgende Tabelle zeigt die positiven ganzen Zahlen, die sich unter Einhaltung der genannten Prämisse kodieren lassen.
| VZ | \(2^2\) | \(2^1\) | \(2^0\) | dezimal |
|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 7 |
| 0 | 1 | 1 | 0 | 6 |
| 0 | 1 | 0 | 1 | 5 |
| 0 | 1 | 0 | 0 | 4 |
| 0 | 0 | 1 | 1 | 3 |
| 0 | 0 | 1 | 0 | 2 |
| 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 0 | 0 | 0 |
So weit, so schön. Wie kodieren wir jetzt -1? – Eine Idee könnte sein, vorne eine 1 zu schreiben und die restlichen Ziffern genauso zu kodieren, wie beim positiven Pendant. -1 ergäbe dann 1001. Offensichtlich liegt dann zwischen 1001 und 0000, was die Null darstellt, noch 1000. Unserer Logik folgend, hatten wir eine zweite Null kreiert, was eine redundante Darstellung derselben bedeutet. Das ist alles andere als optimal. Ein paar schlaue Köpfe haben sich daher ausgedacht, den ganzen Kram, der sich über der Null befindet, einfach darunter zu kopieren. Das sieht dann so aus:
| VZ | \(2^2\) | \(2^1\) | \(2^0\) | dezimal |
|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 7 |
| 0 | 1 | 1 | 0 | 6 |
| 0 | 1 | 0 | 1 | 5 |
| 0 | 1 | 0 | 0 | 4 |
| 0 | 0 | 1 | 1 | 3 |
| 0 | 0 | 1 | 0 | 2 |
| 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | -1 |
| 1 | 1 | 1 | 0 | -2 |
| 1 | 1 | 0 | 1 | -3 |
| 1 | 1 | 0 | 0 | -4 |
| 1 | 0 | 1 | 1 | -5 |
| 1 | 0 | 1 | 0 | -6 |
| 1 | 0 | 0 | 1 | -7 |
| 1 | 0 | 0 | 0 | -8 |
Diese Darstellung nennt sich Zweierkomplement (2er-Komplement). Um es zu ermitteln, müssen wir uns natürlich nicht irgendwelche Tabellen malen und via Copy & Paste ganze
Zahlenblöcke kopieren und irgendwo ankleben. Das Zweierkomplement lässt sich einfach errechnen. Das Bitmuster einer negativen Ganzzahl, -x, errechnen wir, indem wir zuerst das Bit-Muster von x bilden, dieses Muster invertieren und dann 1 addieren.
Beispiel:
VZ/Stellenwert VZ 4 2 1 dez. Ausgangszahl 0 1 0 1 5 invertiert 1 0 1 0 -6 1 addieren 0 0 0 1 1 Ergebnis 1 0 1 1 -5
Das Zweierkomplement besitzt einige herausragende Eigenschaften, die diese Darstellung unserer ersten Überlegung, die ja nicht optimal war, deutlich überlegen machen. Zum Einen vermeiden wir das Problem mit der Null, sie ist jetzt eindeutig. Zum Anderen können wir zwei Zahlen konsistent miteinander verknüpfen also problemlos auch so etwas wie \(2-5\) rechnen. Das ist nichts anderes als \(2+(-5)\), wie wir aus dem Mathematikunterricht wissen. Überhaupt, so wissen wir, „gibt es die Subtraktion gar nicht“, sie ist lediglich die Addition mit negativen Zahlen. Da sich an den Regeln zur schriftlichen Addition gegenüber denen für Dezimalzahlen nichts ändert, wenn wir mit Dualzahlen rechnen, probieren wir es aus:
VZ/Stellenwert VZ 4 2 1 dez.
0 0 1 0 2
1 0 1 1 -5
Ergebnis 1 1 0 1 -3
Cool – Was passiert jedoch, wenn wir 3 und 5 addieren wollen? — Nach allgemeiner Lehrmeinung ist das kein Problem und unser Taschenrechner für maximal 10 Euro liefert auch brav das erwartete Ergebnis: 8.
VZ/Stellenwert VZ 4 2 1 dez.
0 0 1 1 3
0 1 0 1 5
Ergebnis 1 0 0 0 -8
Unser gedachter Prozessor versagt kläglich. -8 ist ganz offensichtlich nicht das, was uns jahrelange Erfahrung und viele Stunden Mathematikunterricht gelehrt haben. In unserem beschränkten System können wir nur positive Zahlen bis maximal 7 darstellen. Für die 8, die nach Adam Riese, der eigentlich Ries hieß, haben wir zu wenige Bits zur Verfügung. Das nennt man einen Arithmetic Overflow. Dennoch ist das Ergebnis nicht ganz aus der Welt gegriffen. Wie Du in meinem Beitrag zur modularen Arithmetik nachlesen kannst.
Das Problem gilt für größere Datentypen, die mehr Bits besitzen, analog. Dumm, wenn man nun mühsam rechnet und nicht weiß, ob das Ergebnis der Bemühungen auch valide ist. Mit einem kleinen Trick können wir uns jedoch helfen, um herauszubekommen, ob wir dem Ergebnis unserer intellektuellen Schufterei vertrauen können. Hierzu verdoppeln wir temporär das Vorzeichenbit. Sind nach Abschluss unserer Verknüpfung die beiden Vorzeichenbits, die wir (gedacht und temporär) haben, identisch, ist die Welt in Ordnung und wir können dem Ergebnis unserer Berechnung trauen, andernfalls nicht.
VZ/Stellenwert VZ2 VZ1 4 2 1 dez.
0 0 1 1 3
0 1 0 1 5
Ergebnis 0 1 0 0 0 -8
VZ1 und VZ2 unterscheiden sich. Das angezeigte Ergebnis ist daher falsch.
Das bis hierher Gesagt gilt für die meisten Programmiersprachen. Python unterscheidet sich jedoch ganz erheblich. Natürlich gelten in Python die genannten Regeln ebenso. Allerdings, und das wird Dir aufgefallen sein, rechnet Python auch mit betragsmäßig großen Ganzzahlen korrekt, auch wenn diese nicht in unsere 64-Bit-Prozessoren passen, wie ich es oben immer vorausgesetzt habe. – Der Grund ist einfach: Python implementiert die sogenannte Langzahlarithmetik. Sie ist langsamer, befreit uns aber davon, die Größe ganzer Zahlen im Auge behalten zu müssen. Bei anderen Programmiersprachen benötigen wir Zusatzbibliotheken für die Langzahlarithmetik. Bei Python ist sie Standard.
Langzahlarithmetik
Du wirst Dir, spätestens nach den obigen Ausführungen, die Frage stellen, wie Dein Computer mithilfe von Python mit Zahlen rechnen kann, die größer als 64 Bits sind, der Bit-Anzahl heutiger Computer.
Ersparen wir uns die Details, so können wir die Frage vergleichsweise einfach beantworten. Zur Vereinfachung spendieren wir uns wieder einen „Versuchsprozessor“. Dieser habe jetzt aber 8 Bit, sodass er ganze Zahlen von -256 bis 255 speichern kann.
Um Zahlen speichern zu können, die größer als 255 (\(2^8-1)\) sind, speichern wir sie in aufeinanderfolgenden Speicherzellen die „Ziffern“ einer solchen Zahl in einem Stellenwertsystem zur Basis 256. Das Verfahren kennst Du bereits. Nur verwenden wir hierbei nicht 2 oder 10, wir nehmen 256 als Basis.
Block (Stellenwert) (256^2) (256^1) (256^0)
65536 256 1
-------------------------------------------------
15 42 192
\[10752
15 \cdot 65536 + 42 \cdot 256 + 192 \cdot 1 = 983040 + 10752 + 192 = 993984
\]
Eine Zahl zu speichern ist eine Sache. Wie aber rechnet unser Prozessor, der ja (angenommen) nur 8 Bits hat, damit. Dazu erinnere Dich an das schriftliche Addieren und Multiplizieren, wie Du es in der Schule gelernt hast. Beim Addieren zweier Zahlen konnte dabei niemals eine Teilsumme größer als 19 herauskommen (zwei Neunen und „einer im Sinn“ ergibt maximal 19). Du rechnest im Grunde mit sehr kleinen Zahlen. Analoges gilt für die schriftliche Multiplikationen. Große Zahlen werden bei diesen Verfahren in kleine und handliche Pakete aufgeteilt – dem Stellenwertsystem sei es gedankt.
Das gleiche Prinzip wird auch bei der Langzahlarithmetik verwendet. Ein Prozessor arbeitet nur mit einzelnen Bits. Die Arithmetisch-Logische-Einheit (engl. ALU), die die eigentliche Rechenarbeit im Prozessor übernimmt, ist aber so konstruiert, das sie auch 8 Bits in einem Stück addieren und multiplizieren kann. Unterteilen wir betragsmäßig große Zahlen in solche 8-Bit-Einheiten, wie oben dargestellt, sodass die ALU sie gerade noch verarbeiten kann, können wir auch solche Zahlen verarbeiten. Wir müssen lediglich Obacht haben, ob Zwischendurch Überträge auftreten. Wenn also ein Overflow auftritt, muss sie nicht nur die 8 verbleibenden Bits kennen, die wie Du weißt, wenn Du meinen Beitrag gelesen hast, das Ergebnis in modularer Arithmetik darstellen, sie muss auch wissen, was sie vorne abgeschnitten hat. Das können jedoch alle handelsüblichen Prozessoren. Die in unseren PCs und Laptops beherrschen das jedenfalls alle. Die meisten Programmiersprachen nutzen dieses Feature nur nicht. Python tut es und kann daher mit beliebigen Ganzzahlen rechnen.Die Langzahlarithmetik hat natürlich auch Nachteile – Du ahnst es. Sie ist langsamer als die rein auf der hardwarenahen Abbildung beruhende modulare Arithmetik, weshalb viele Programmiersprachen im Standard auf modularer Arithmetik basieren und Langzahlarithmetik nur mithilfe von Zusatzbibliotheken realisieren.
Wichtige Erkenntnisse
Ganze Zahlen lassen sich präzise im Computer kodieren – das sollte anhand deren vorgestellter Kodierung (auch in Bezug auf Langzahlarithmetik) klar sein. Ebenso korrekt ist die ganzzahlige Arithmetik. Alle mit ganzen Zahlen durchgeführten Berechnungen sind präzise. Achtung: Die Gleitkommadivision, auch wenn die Operanden ganze Zahlen sind, ist keine Operation der Ganzzahlarithmetik. Die Operanden werden vor der Division in Gleitkommazahlen konvertiert. Die ganzzahlige Division und die Restwertdivision (Modulo) werden dagegen mit ganzzahliger Arithmetik durchgeführt. Mit Python sind wir, dank Langzahlarithmetik, nicht durch die Bits unserer Prozessoren beschränkt.