Zahlensysteme, Teil 1 - Grundlagen

sothis_

Zahlensysteme, Teil 1 - Grundlagen

Inhalt

1 Vorwort
2 Allgemeines
2.1 Dezimalsystem
2.2 Binärsystem
2.3 Hexadezimalsystem
2.4 Oktalsystem
2.5 Andere Systeme
2.6 Umwandlungsalgorithmen
3 Ausblick

1 Vorwort

Zahlen können sehr verwirrend sein, insbesondere wenn einen das Programmierfieber gepackt hat, und man sich auf einmal mit Buchstaben konfrontiert sieht, welche Zahlen darstellen sollen. Ich gebe zu, es ist nicht einfach, dahinterzusteigen, mit unterschiedlichen Zahlensystemen zu arbeiten und deren Sinn zu verstehen. Dennoch benötigt man kein Diplom in Mathematik, um sich Grundlagen anzueignen. Mathematiker neigen dazu, Sachverhalte sehr schnell abstrahieren zu wollen, auch mir passiert dies häufig.
Ist es denn in der Wahrheitsfindung recht hilfreich, umso komplizierter macht dies dem Programmierer, sich auf das Wesentliche zu konzentrieren. Aus diesem Grunde verzichte ich in diesem Artikel absichtlich auf Begriffe wie Restklassen, Zahlentheorie, Mengenlehre, Körper und Ringe. Die Grundlagen, die ich in diesem Artikel beschreiben und erklären werde, sollen, so meine leise Hoffnung, genug sein, um sich wacker im Programmieralltag behaupten zu können.

Ich werde im dritten Teil Beispielcode in Assembler und C anführen. Assembler eignet sich hervorragend, um den eigentlichen maschinennahen Ablauf zu verdeutlichen. Da Assembler zugegebenermaßen nicht die einfachste Sprache ist, werde ich Assemblercode gesondert beschreiben und erklären. Also keine Scheu, falls Vorkenntnisse nicht existieren sollten. Auf C++-Beispiele verzichte ich gänzlich, da eine Umsetzung von C auf C++ kein unmögliches Unterfangen darstellt. Des Weiteren soll es hier nicht um Abstraktion und Polymorphismus gehen, eher denn um maschinennahe Grundlagen und wie Daten im Speicher eigentlich repräsentiert werden.

2 Allgemeines

2.1 Dezimalsystem

Das Dezimalsystem ist im Alltag das am häufigsten benutzte Zahlensystem. Jeder angehende und erfahrene Programmierer sollte somit die wenigsten Probleme mit dem Umgang mit Zahlen und Rechnen in diesem System haben. Wenn doch, dann hören Sie an dieser Stelle auf zu lesen. Im Ernst, was kennzeichnet dieses System denn eigentlich? Im Dezimalsystem, wie sich aus dem Namen herleiten lässt, stellen wir Zahlen zur Basis 10 dar. Dies bedeutet, dass sich sämtliche Zahlenwerte aus der Verknüpfung von Zehnerpotenzen bilden lassen.

Am Beispiel der Zahl 3425, mit der wohl die meisten assoziieren, dass "etwas" eben 3425-mal vorhanden ist, bedeutet dies:

3·10[h]3[/h] + 4·10[h]2[/h] + 2·10[h]1[/h] + 5·10[h]0[/h]

also

3000 + 400 + 20 + 5 = 3425

Der fraktionale Teil einer Dezimalzahl lässt sich ebenfalls mit Hilfe dieser Darstellung erzeugen, indem die jeweiligen Negativpotenzen verknüpft werden. Für die erste Ziffer hinter dem Komma multiplizieren wir also mit 10^-1, für die zweite mit 10^-2 und so weiter.

Zum Darstellen von Zahlen innerhalb des Dezimalsystems bietet es uns exakt zehn Ziffern. Auch wenn dies keines weiteren Kommentars bedürfte, liste ich sie hier der Vollständigkeit halber noch einmal auf:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9

Die Algebra und Arithmetik innerhalb dieses Systems sind für uns leicht greifbar und intuitiv nachzuvollziehen.

int main(int argc, char* argv[])
{
	int a = 2;
	int b = 3;
	int c = 0;

	c = a + b;

	return 0;
}

Die Variable c wird nun, nach dem Aufruf c = a + b; , wie gewohnt 5 beinhalten. Was passiert nun aber wirklich? Was macht der Prozessor, damit c auch wirklich 5 ist? Um dies nachvollziehen zu können, müssen wir uns zuvor mit anderen Zahlensystemen beschäftigen.

2.2 Binärsystem

Heutige Mikrocontroller und Prozessoren basieren auf dem Prinzip, dass sie durch vorgegebene Schaltlogik und einem definierten Ausgangszustand einen bestimmten Endzustand einnehmen. Der Ursprung dieser Technologie ist zwar nicht in der Erfindung des Transistors zu suchen, sie gewann damit aber an Effizienz und Leistung. In der Schaltlogik nutzt man die Eigenschaft des Transistors zwei Schaltzustände einnehmen zu können. Da es besonders effizient und einfach ist, einen Schaltzustand darin zu überprüfen, ob eine Spannung anliegt oder nicht, liegt es nahe, Daten in eben dieser Repräsentation zu speichern. Demnach ist es nur vernünftig, dieses elektronische Konstrukt mit einem Zahlensystem zu beschreiben, welches auch nur zwei Ziffern bietet, um Zahlenwerte darstellen zu können.

Das binäre System erfüllt diese Eigenschaft und stellt uns folgende Ziffern zur Verfügung:

0, 1

Der Wert einer binären Zahl lässt sich genauso konstruieren wie schon beim Dezimalsystem gezeigt. Eine Umrechnung in das Dezimalsystem erfolgt also mit dem Verknüpfen der Zweierpotenzen.

Am Beispiel der Zahl 11010110 bedeutet dies:

1·2[h]7[/h] + 1·2[h]6[/h] + 0·2[h]5[/h] + 1·2[h]4[/h] + 0·2[h]3[/h] + 1·2[h]2[/h] + 1·2[h]1[/h] + 0·2[h]0[/h]

also:

128 + 64 + 0 + 16 + 0 + 4 + 2 + 0 = 214

Die Umwandlung von einer Dezimalzahl in eine Binärzahl gestaltet sich etwas komplizierter (siehe Abschnitt 2.6). Des Weiteren sind Binärzahlen sehr unhandlich. Sie neigen dazu, selbst bei geringen Dezimalwerten, sehr lang zu werden, da eben nur zwei Ziffern zur Verfügung stehen. Um das Programmieren einfacher zu gestalten und die Vorteile der Dezimalzahlen und der Binärzahlen zu verbinden, hat man sich auf ein Zahlensystem geeinigt, welches bei selbst sehr großen Ganzzahlwerten eine kompakte Darstellung bietet, in dem sich aber zugleich Werte einfach in Dualzahlen umwandeln lassen.

2.3 Hexadezimalsystem

Wie schon erwähnt, war es notwendig, ein Zahlensystem zu konstruieren, welches sich einfach in die Dualzahldarstellung umwandeln lässt und einfach zu lesen ist. Die Einfachheit der Umwandlung von einem System in ein anderes basiert darauf, welche Basis dem Zahlensystem zugrunde liegt. Um ein einfaches Umwandeln in und vom Binärsystem zu gewährleisten, wählt man eine Basis, die selbst eine Zweierpotenz ist. Im Hexadezimalsystem ist dies die Basis 16 also 2[h]4[/h] . Demnach benötigt man 16 verschiedene Ziffern um eine Zahl darzustellen. Man hat sich darauf geeinigt, die ersten 6 Buchstaben des lateinischen Alphabets als Erweiterung der schon bekannten zehn arabischen Ziffern einzusetzen.

Dies wären im folgenden:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F

Die Wertigkeiten von A, B, C, D, E und F entsprechen dezimal 10, 11, 12, 13, 14 und 15. Beim Aufzählen folgt also nach 9 nicht 10 , sondern A . Auf F folgt 10 . Die Umrechnung in das Dezimalsystem gestaltet sich ähnlich wie schon beim Binärsystem gezeigt.

Am Beispiel F6C2 erhalten wir:

15·16[h]3[/h] + 6·16[h]2[/h] + 12·16[h]1[/h] + 2·16[h]0[/h]

also

61440 + 1536 + 192 + 2 = 63170

Warum das Umwandeln einer hexadezimalen Zahl in das Binärsystem verhältnismäßig einfach von statten geht, wird in Abschnitt 2.6 gezeigt.

2.4 Oktalsystem

Das Oktalsystem stellt Zahlen zur Basis 8 dar. Da 8 ebenfalls eine Zweierpotenz ist, gestaltet sich die Umwandlung vom Oktalsystem in das Binärsystem und umgekehrt sehr einfach (näheres dazu ebenfalls im Abschnitt 2.6). Wie der aufmerksame Leser bereits vermuten wird, stehen uns in diesem System acht Ziffern zur Verfügung.

Dies wären im folgenden:

0, 1, 2, 3, 4, 5, 6, 7

Die Umrechnung in das Dezimalsystem erfolgt nach dem gleichen Prinzip wie bei den anderen schon vorgestellten Systemen.

Die Zahl 3651 lässt sich demzufolge so darstellen:

3·8[h]3[/h] + 6·8[h]2[/h] + 5·8[h]1[/h] + 1·8[h]0[/h]

also

1536 + 384 + 40 + 1 = 1961

Anwendung findet dieses System nur noch selten, da es aufgrund der niedrigen Anzahl von zur Verfügung stehenden Ziffern ebenfalls eine relativ lange Darstellung bei großen Dezimalwerten erzeugt. Die einfache Umrechnung in das Binärsystem jedoch macht dieses System immer noch, abhängig vom Anwendungsfall besonders bei einem kleinen dezimalen Wertebereich, attraktiv. So werden bei POSIX-kompatiblen Betriebssystemen, wie Unix, Linux oder BSD-Derivaten, Dateirechte mit einem Zahlenwert im Oktalformat verwaltet und repräsentiert (z.B. 0664).

2.5 Andere Systeme

Kreative Leser mögen nun entdeckt haben, dass man sich doch eigentlich mit Hilfe der Potenzdarstellung jedes nur erdenkliche Zahlensystem konstruieren kann. Dies ist natürlich korrekt. Man muss die Basis definieren, welche dem System zugrunde liegen soll, den Ziffernsatz eindeutig bestimmen und deren Wertigkeit festlegen.

Ein weiteres System, welches wir täglich nutzen, ist zum Beispiel das Hexagesimalsystem. So assoziieren wir doch, dass eine Stunde aus 60 Minuten besteht, und nicht aus 100 . Nicht nur bei der Zeitmessung, sondern auch in der Astronomie hat das Hexagesimalsystem immer noch einen großen Stellenwert. So werden Koordinaten vorzugsweise mit Grad, Bogenminuten und Bogensekunden angegeben, welches natürlich unmittelbar mit der uns vertrauten Einteilung des Kreises in 360 gleiche Teile zusammenhängt. Der größte Unterschied des Hexagesimalsystems zu den hier näher vorgestellten besteht darin, dass die Algebra und Arithmetik in diesem System nicht denen des Dezimalsystems ähnelt, da wir für gewöhnlich die Folge der 60 als Basis nicht konsequent beibehalten. So ist, in Stunden gerechnet, 21 + 5 eben 2 . Dies ist ein Restklassenproblem - ok, jetzt habe ich dieses Wort doch verwendet, und werde nicht näher darauf eingehen, versprochen.

2.6 Umwandlungsalgorithmen

Bei der grundlegenden Beschreibung habe ich jeweils schon gezeigt, wie einfach es ist, Zahlen eines beliebigen Zahlensystems in wertgleiche Repräsentanten des Dezimalsystems umzuwandeln. Der umgekehrte Weg, also eine Dezimalzahl zum Beispiel in eine Dualzahl umzuwandeln ist, wenn auch nicht ungemein, schwieriger.

Schauen wir uns das Beispiel aus 2.2 noch einmal genauer an:

Die Dualzahl 11010110 ist wertgleich mit 214 im Dezimalsystem:

1·2[h]7[/h] + 1·2[h]6[/h] + 0·2[h]5[/h] + 1·2[h]4[/h] + 0·2[h]3[/h] + 1·2[h]2[/h] + 1·2[h]1[/h] + 0·2[h]0[/h]

also:

128 + 64 + 0 + 16 + 0 + 4 + 2 + 0 = 214

Wie wandeln wir 214 in eine Dualzahl um? Der geübte Mathematiker erkennt sofort, dass wir die Koeffizienten vor den Zweierpotenzen berechnen müssen, um so Schritt für Schritt unsere Dualzahl konstruieren zu können. Am einfachsten gestaltet sich dies in der Reihenfolge von links nach rechts. Wir beginnen also mit der höchsten Zweierpotenz, welche in unserer Dezimalzahl enthalten ist.

Wir wählen geeigneter Weise eine angemessen hohe Zweierpotenz:

2[h]8[/h] = 256	// 256 ist größer als 214, demnach wählen wir die nächstkleinere Zweierpotenz.
			// Man kann diesen Umstand mit führenden Nullen in der Dualzahl repräsentieren
2[h]7[/h] = 128	// 128 ist die größte Zweierpotenz kleiner als 214,
			// demnach wählen wir eine 1 als erste Ziffer für unsere

Jetzt bilden wir die Differenz aus unserer umzuwandelnden Dezimalzahl 214 und der eben ermittelten höchsten Zweierpotenz, die kleiner ist als 214 , also 128 .

214 - 128 = 86

Mit diesem Rest bestimmen wir den Wert der nächsten Stelle unserer Dualzahl. Wir fahren mit der nächstkleineren Zweierpotenz fort, also 2[h]6[/h] . Ist 2[h]6[/h] kleiner oder gleich als 86 fügen wir wieder eine 1 an die Dualzahl an, da 2[h]6[/h] dann als in 86 "enthalten" angesehen werden kann. Dann bestimmen wir den neuen Rest und fahren damit wie gewohnt fort. Bei einem Rest von 0 ist eine 1 zu setzen. Danach haben alle nachfolgenden Zweierpotenzen einen Koeffizienten von 0 . In diesem Fall füllen wir unsere Dualzahl einfach mit Nullen nach rechts bis 2[h]0[/h] auf. Ist eine Zweierpotenz größer als der bleibende Rest, so fügen wir eine 0 an die Dualzahl, und benutzen den alten Rest um ihn mit der nächstkleineren Zweierpotenz zu vergleichen.

Hier der vollständige Algorithmus für die Zahl 214 :

2[h]8[/h] = 256   // 256 > 214 [e]rarr[/e] 0
2[h]7[/h] = 128   // 128 < 214 [e]rarr[/e] 1 (214 - 128 = 86)
2[h]6[/h] = 64    //  64 <  86 [e]rarr[/e] 1 ( 86 -  64 = 22)
2[h]5[/h] = 32    //  32 >  22 [e]rarr[/e] 0
2[h]4[/h] = 16    //  16 <  22 [e]rarr[/e] 1 ( 22 -  16 = 6)
2[h]3[/h] = 8     //   8 >   6 [e]rarr[/e] 0
2[h]2[/h] = 4     //   4 <   6 [e]rarr[/e] 1 (  6 -   4 = 2)
2[h]1[/h] = 2     //   2 =   2 [e]rarr[/e] 1 (  2 -   2 = 0)
2[h]0[/h] = 1     //   1 >   0 [e]rarr[/e] 0

Da führende Nullen die Wertigkeit der Zahl nicht beeinflussen, erhalten wir so die Dualzahldarstellung der Dezimalzahl 214 :

11010110

Wie sieht dann aber die Umwandlung von einer Dezimalzahl in eine Hexadezimalzahl aus? Dieser Algorithmus wäre sogar noch komplexer. Grundsätzlich benötigen wir die Koeffizienten der Sechzehnerpotenzen. Da wir aber nun nicht mehr nur zwischen zwei Ziffern zu unterscheiden haben, sondern zwischen sechzehn, reicht ein einfaches Vergleichen der Sechzehnerpotenz mit dem Rest nicht mehr. Vielmehr müssten wir nun alle 16 möglichen Koeffizienten mit der zugehörigen Potenz multiplizieren. Das Ergebnis, welches uns am nächsten an den Rest "heranbringt" würde uns dann den zu wählenden Koeffizienten liefern.

Da jener Algorithmus insbesondere bei sehr hohen Basen zu rechenaufwendig ist, erscheint dieses Verfahren zunehmend ineffizient. Eine andere Möglichkeit, eine Zahl in ihre Form zu einer beliebigen Basis zu bringen ist die Modulomethode, auch Divisionsmethode genannt. Hier betrachtet man den Rest, der bei der Division der Zahl durch die gewünschte Basis entsteht. Bei diesem Algorithmus erhält man allerdings zuerst den Koeffizienten der kleinsten Potenz. Wir erzeugen die Zahl nun also von rechts nach links. Das besondere an dieser Rechenvorschrift ist, dass der Rest unmittelbar die Wertigkeit der Ziffer im Zielsystem repräsentiert. Demnach ist dies ein sehr effizienter Algorithmus, da keine weiteren Rechenoperationen notwendig sind. Im dritten Teil dieses Artikels werde ich verschiedene Beispielimplementierungen anführen, und sie anhand deren Geschwindigkeiten vergleichen.

Betrachten wir die Modulomethode anhand des Beispiels der Dezimalzahl 63170 :

Eine Umwandlung in das Hexadezimalsystem bedeutet, dass wir durch 16 dividieren müssen, also

63170 : 16 = 3948, Rest  2 -> 2
 3948 : 16 =  246, Rest 12 -> C
  246 : 16 =   15, Rest  6 -> 6
   15 : 16 =    0, Rest 15 -> F

Da wir die Zahl von rechts nach links erzeugen, erhalten wir

63170[t](10)[/t] = F6C2[t](16)[/t]

Eine weitere Variante ist, die Dezimalzahl zuerst in ihre Dualdarstellung zu konvertieren, um diese dann anschließend in ihre Hexadezimalform zu bringen. Ich erwähnte bereits, dass dies sehr schnell und einfach möglich ist. Der Grund hierfür liegt darin, dass 16 selbst eine Zweierpotenz ist, eben 2[h]4[/h] .

Sehen wir uns zuerst die ersten 16 Dezimalwerte in ihrer Dualdarstellung und in ihrer Hexadezimaldarstellung an:

0      0000b    0x0
 1      0001b    0x1
 2      0010b    0x2
 3      0011b    0x3
 4      0100b    0x4
 5      0101b    0x5
 6      0110b    0x6
 7      0111b    0x7
 8      1000b    0x8
 9      1001b    0x9
10      1010b    0xA
11      1011b    0xB
12      1100b    0xC
13      1101b    0xD
14      1110b    0xE
15      1111b    0xF

Was macht denn nun eine Hexadezimalzahl für Computersystem so besonders? Dadurch das 16 durch 2[h]4[/h] dargestellt werden kann, können wir Gruppen von Dualzahlen der Länge 4 umwandeln, indem wir sie einfach durch ihren Hexadezimalwert austauschen, also substituieren. Umgekehrt funktioniert das natürlich genau so einfach. Sollte eine Dualzahl zum Beispiel 6 Ziffern lang sein, füllen wir sie solange mit führenden Nullen auf, bis die Länge durch vier teilbar ist. In diesem Beispiel also mit zwei Nullen. Diesen Vorgang bezeichnet man im Englischen als "padden". Ziel dabei ist es, Datenstrukturen passend für einen Algorithmus vorzubereiten, ohne dabei die Wertigkeit der Datenstruktur selbst zu verändern. Ein Vorgang, der zum Beispiel auch bei der Berechnung von Hash-Summen Anwendung findet.

Die Dualzahl 11010110 lässt sich also wie folgt darstellen:

1101 0110

Wir ersetzen die Vierergruppen gemäß oben angeführter Tabelle mit ihren hexadezimalen Entsprechungen:

D 6

Um hexadezimale Zahlen besser von dezimalen unterscheiden zu können, fügt man häufig das Präfix " 0x " an. Auch Suffixe wie "h" sind üblich. Diese beiden Notationen werden von den meisten Compilern und Assemblern verstanden. Da wir die Dualzahl benutzt haben, die wir bei der Konvertierung von 214 erhielten, können wir sofort darauf schließen, dass:

214 = 11010110b = 0xD6

Die Umwandlung einer hexadezimalen Zahl in eine binäre Zahl erfolgt nach ähnlichem Prinzip:

0xF6C2 = F 6 C 2 = 1111 0110 1100 0010 = 1111011011000010b

Diese wiederum kann durch die in 2.2 vorgestellte Rechenvorschrift leicht in ihre Dezimalform gebracht werden. Wir erhalten:

1111011011000010b = 63170

Das vorgestellte Oktalsystem verhält sich ähnlich wie das Hexadezimalsystem, ist doch die zugrunde liegende Basis 8 und somit auch eine Zweierpotenz. Statt binären Vierergruppierungen, müssen wir jetzt Werte in Dreiergruppen substituieren:

0      000b    0o
 1      001b    1o
 2      010b    2o
 3      011b    3o
 4      100b    4o
 5      101b    5o
 6      110b    6o
 7      111b    7o

Vorsicht, C-Compiler interpretieren eine konstante Zahl im Quellcode als Oktalzahl, wenn ihr eine führende Null vorangestellt wird:

int a = 12;  // 12 dezimal
int b = 012; // 12 oktal

Die Variable b beinhaltet jetzt den Dezimalwert 10 , nicht 12 . Wie in der Tabelle gezeigt, kann eine Oktalzahl auch mit nachfolgendem kleinem " o " gekennzeichnet werden. Diese Notation mag zwar intuitiver erscheinen, so wird sie doch bei Programmiersprachen recht selten als Indikator benutzt.

3 Ausblick

Im nächsten Teil des Artikels werde ich nach diesem mehr oder wenig trockenen Thema einen Einblick darauf geben, wie Daten denn nun tatsächlich im Arbeitsspeicher und Prozessor verwaltet werden, wie es kommt, dass wir Zeichen als Zahlen repräsentieren müssen und welche Spielereien sich mit Zahlen anstellen lassen.

Bis dahin,

Janos

guter artikel. das ^^ muss jeder wissen, der sich programmierer schimpft.
und das hier: http://de.wikipedia.org/wiki/Stellenwertsystem sollte man auch mal lesen.

rüdiger

Gibt ja auch noch komplexe Basen

void main(void)

*hust*

Undefined_cl

Sehr gute Erklärung dennoch hat sich ein kleiner unerheblicher Fehler eingeschmuggelt

oben heißt es beim Darstellen von 214 im Binärsystem:

2^7 = 128 // 128 < 214 → 1 (256 - 128 = 86) << an der Stelle müsste es 214-128 heißen

sothis_

danke für den hinweis