Zahlbasiswechsel

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Die Transformation der Darstellung einer Zahl in einem Stellenwertsystem in ein anderes, beispielsweise aus dem in der Digitaltechnik verwendeten Binär- oder Dualsystem in das alltagsgebräuchliche Dezimalsystem, wird als Zahlbasiswechsel bezeichnet. Für diesen Prozess werden geeignete Algorithmen benötigt. Der Wechsel vollzieht sich von einem Quellsystem hin zum Zielsystem.

Motivation[Bearbeiten]

Unter den Zahlensystemen werden heute neben unserem gebräuchlichen Dezimalsystem auch noch Stellenwertsysteme mit anderen Grundzahlen verwendet.

So werden Zahlen in der Informationstechnik normalerweise im Dualsystem dargestellt, da dieses sich zur Verarbeitung durch elektronische Schaltungen gut eignet. Bei der Eingabe und Ausgabe dagegen stellt man die Zahlen lieber in einem System dar, das für Menschen besser lesbar ist. Außer dem Dezimalsystem werden hierfür häufig auch das Oktalsystem und das Hexadezimalsystem verwendet, da beide besonders einfach in das Dualsystem transformierbar sind.

In anderen Kulturen und in früheren Zeiten kamen aus den verschiedensten Gründen auch andere Stellenwertsysteme zum Einsatz, was bis heute, insbesondere bei der Einteilung bestimmter Einheiten von physikalischen Größen, erkennbar ist.

Daraus ergibt sich häufig die Notwendigkeit, die Darstellung einer Zahl von einem Stellenwertsystem in ein anderes zu transformieren. Im Folgenden wird das Stellenwertsystem, von dem transformiert werden soll, als Quellsystem und das Stellenwertsystem, in das transformiert soll, als Zielsystem bezeichnet.

Umrechnung für einfache Spezialfälle[Bearbeiten]

Ist die Grundzahl n des Zielsystems eine positive ganzzahlige Potenz der Grundzahl m des Quellsystems (also n = mi für eine beliebige positive ganze Zahl i), so gestaltet sich der Umrechnungsvorgang besonders einfach. In diesem Fall lassen sich nämlich Gruppen aus jeweils i Ziffern einer Zahl im Quellsystem direkt in eine Ziffer des Zielsystems umrechnen. Umgekehrt ist es natürlich genauso möglich, eine Ziffer einer Zahl des Quellsystems in mehrere Ziffern des Zielsystems zu transformieren, wenn die Grundzahl des Quellsystems eine positive ganzzahlige Potenz der Grundzahl des Zielsystems ist. Da sich die Größe der Zifferngruppen in diesen Fällen üblicherweise in einem überschaubaren Bereich bewegt, lassen sich solche Umrechnungen leicht mit Hilfe von Tabellen durchführen. Die Transformation zwischen Dual- und Oktalsystem ist beispielsweise mit folgender Tabelle möglich:

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

So ergibt die Umrechnung der Dualzahl 10011101 ins Oktalsystem (i=3):

10011101 = 010 011 101 = 2 3 5

Die Transformation zwischen Dual- und Hexadezimalsystem kann über folgende Tabelle erreicht werden:

Dual 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
Hex 0 1 2 3 4 5 6 7 8 9 A B C D E F

Dieses Verfahren funktioniert auch für weitere Fälle. Es genügt, dass die Grundzahlen m und n Potenzen einer gemeinsamen Basis b sind, das heißt es gilt m=bi und n=bj, wobei i und j natürliche Zahlen sind. Im naiven Fall wird zuerst mit dem gerade gezeigten Verfahren in die Grundzahl b umgerechnet, um anschließend in die Darstellung zur Grundzahl n zu wechseln. Beispielsweise ist so die Umrechnung vom Oktalsystem (m=8=23) ins Hexadezimalsystem (n=16=24) über den Umweg des Dualsystems (b=2) möglich.

Es ist immer günstig, die Grundzahl b in der Weise zu normieren, dass die Eins der größte gemeinsame Teiler von i und j ist. Ist dies nicht der Fall, so kann statt b die Grundzahl bz und statt i bzw. j die Zahlen i/z bzw. j/z gewählt werden, mit z=ggt(i, j).

Anstelle des naiven Verfahrens über den Umweg der Grundzahl b kann aber auch direkt zwischen derartigen Stellenwertsystemen umgerechnet werden. Dabei werden dann j/z Ziffern der Zahl in der Darstellung zur Grundzahl m in i/z Ziffern der Zahl in der Darstellung zur Grundzahl n umgesetzt, wobei wieder z=ggT(i, j) gilt. Eine derartige Tabelle lässt sich leicht mit dem naiven Verfahren erstellen. Die Umrechnung zwischen dem Stellenwertsystem zur Basis 4 und dem Oktalsystem ist zum Beispiel mit folgender Tabelle möglich:

Grundzahl 4 000 001 002 003 010 011 012 013 020 021 022 023 030 031 032 033
Oktal 00 01 02 03 04 05 06 07 10 11 12 13 14 15 16 17
Grundzahl 4 100 101 102 103 110 111 112 113 120 121 122 123 130 131 132 133
Oktal 20 21 22 23 24 25 26 27 30 31 32 33 34 35 36 37
Grundzahl 4 200 201 202 203 210 211 212 213 220 221 222 223 230 231 232 233
Oktal 40 41 42 43 44 45 46 47 50 51 52 53 54 55 56 57
Grundzahl 4 300 301 302 303 310 311 312 313 320 321 322 323 330 331 332 333
Oktal 60 61 62 63 64 65 66 67 70 71 72 73 74 75 76 77

Umrechnung im allgemeinen Fall[Bearbeiten]

Im Wesentlichen gibt es zwei Möglichkeiten, eine Darstellung von Zahlen in einem Stellenwertsystem in die Darstellung von Zahlen in einem anderen Stellenwertsystem zu überführen. Welche Variante verwendet wird, hängt von den gegebenen Voraussetzungen ab.

Zunächst ist festzustellen, dass eine Zeichenfolge in eine andere transformiert werden soll. In Programmiersprachen werden Zeichenfolgen meist durch Variablen vom Typ String repräsentiert. Auf solchen Typen können typische String-Operationen durchgeführt werden. Es werden im Wesentlichen nur die Operationen:

  • isEmpty(s), die prüft ob die Zeichenfolge s leer ist, also die Länge Null besitzt,
  • catFirst(c, s), die das Zeichen c an den Anfang der Zeichenfolge s stellt und
  • cutFirst(s), die das erste Zeichen der Zeichenfolge s abschneidet und zurückliefert,

benötigt.

Die Algorithmen zum Basiswechsel vereinfachen sich, wenn vereinbart wird, dass ein leerer String mit der 0 zu identifizieren ist. In realen Anwendungen würde dafür die Zeichenfolge „0“ verwendet werden. Dieser Sonderfall lässt sich aber leicht zusätzlich abfangen.

Wenigstens in einem System müssen auf den Zeichenfolgen bestimmte Grundrechenarten ausgeführt werden können. Je nachdem, auf welchem System die benötigten Grundrechenarten zur Verfügung stehen, wird eine der beiden Varianten ausgewählt. Die Algorithmen für diese Grundrechenarten sind nicht trivial. Beispielsweise können die aus der Schule bekannten Algorithmen für das Dezimalsystem auch für andere Stellenwertsysteme adaptiert werden (siehe Arithmetik in Stellenwertsystemen). Effizientere Algorithmen für die Multiplikation wären hingegen zum Beispiel der Karatsuba-Algorithmus, der Toom-Cook-Algorithmus oder der Schönhage-Strassen-Algorithmus.

Variante 1: Grundrechenarten im Quellsystem[Bearbeiten]

Steht die Division (Operator /) mit Rest („Modulo“, Operator %) im Quellsystem zur Verfügung, so kann die Darstellung einer (ganzen) Zahl im Quellsystem in die Darstellung derselben Zahl im Zielsystem wie folgt transformiert werden:

Zunächst wird die Darstellung (also die Zeichenfolge) im Zielsystem auf Null (also die leere Zeichenfolge) gesetzt. Solange die Zeichenfolge im Quellsystem verschieden von Null (also nicht die leere Zeichenfolge) ist, wird eine Folge von Anweisungen wiederholt, die zunächst den Rest der Zeichenfolge im Quellsystem beim Teilen durch die (ganze) Grundzahl (Basis) des Zielsystems bildet. Dieser Rest wird dann direkt über eine Tabelle in die zugehörige Ziffer des Zielsystems übersetzt und diese als höchstwertige Ziffer der Darstellung im Zielsystem vorangestellt. Anschließend wird die Zeichenfolge im Quellsystem durch die Basis des Zielsystems geteilt. Der folgende Pseudocode soll dies verdeutlichen.

function Zielsystem convert(Quellsystem quelle) {
    Zielsystem ziel = "";
    while (!quelle.isEmpty) {
       ziel = catFirst(convertSimple(quelle % zbasis), ziel)
       quelle = quelle / zbasis;
    }
    return ziel;
}

Die Variable quelle ist vom Typ Quellsystem und die Variable ziel vom Typ Zielsystem. Mit zbasis ist eine Variable vom Typ Quellsystem bezeichnet, die die Basis des Zielsystems enthält.

Die Operation convertSimple(s) ordnet einem Wert vom Typ Quellsystem, wie er von der Modulo-Operation beispielsweise im Bereich von 0 bis b-1 geliefert wird, direkt die entsprechende Ziffer des Zielsystems zu. Hierbei ist b die Basis (bzw. der Absolutbetrag der Basis) des Zielsystems. Dies ist leicht über eine Tabelle möglich.

Dieses Verfahren beginnt bei der niedrigstwertigen, der Einerstelle, und läuft zu den höherwertigen Stellen. Es ist ein Little-Endian-Verfahren.

Variante 2: Grundrechenarten im Zielsystem[Bearbeiten]

Stehen die Grundrechenarten Multiplikation (Operator *) und Addition (Operator +) im Zielsystem zur Verfügung, so kann die (endliche) Darstellung einer Zahl im Quellsystem in die Darstellung derselben Zahl im Zielsystem wie folgt transformiert werden.

Zunächst wird auch hier die Darstellung (also die Zeichenfolge) im Zielsystem auf Null (also die leere Zeichenfolge) gesetzt. Solange die Zeichenfolge im Quellsystem verschieden von Null (also nicht die leere Zeichenfolge) ist wird eine Folge von Anweisungen durchgeführt, die zunächst das erste Zeichen (also die höchstwertige Ziffer) der Darstellung im Quellsystem abtrennt und deren Wert direkt mittels einer Tabelle in eine Zahl des Zielsystems übersetzt. Anschließend wird diese Zahl zur Ziffernfolge im Zielsystem addiert, nachdem diese mit der Grundzahl des Quellsystems multipliziert wurde. Der folgende Pseudocode soll dies verdeutlichen.

Stehen die Grundrechenarten im Zielsystem zur Verfügung, so führt der folgende Algorithmus zum Ziel:

function Zielsystem convert(Quellsystem quelle) {
    Zielsystem ziel = "";
    while (!quelle.isEmpty())
       ziel = ziel * qbasis + convertSimple(cutFirst(quelle));
    return ziel;
}

Die Variable quelle ist wieder vom Typ Quellsystem und die Variable ziel vom Typ Zielsystem. Mit qbasis ist eine Variable vom Typ Zielsystem bezeichnet, die die Grundzahl des Quellsystems enthält.

Die Operation convertSimple(s) ordnet einer Ziffer vom Quellsystem eine Zahl im Zielsystem zu. Dies ist leicht über eine Tabelle möglich.

Dieses Verfahren ist eine Form des Horner-Schemas, es beginnt bei der höchstwertigen Stelle und läuft zu den Stellen mit kleinerem Wert (Big-Endian).

Geeignet erweitert lässt es sich über das Stellenwerttrennzeichen hinaus fortsetzen, so dass auch (endliche oder unendliche) Brüche mit beliebiger Genauigkeit umgewandelt werden können. Dabei können im Zielsystem Tabelleneinträge erforderlich sein, die mehr als eine Stelle umfassen. Die Behandlung der dabei entstehenden Überträge kann durch den Einschub einer gegenläufigen Rechnung nach Art der Variante 1 erfolgen.

Siehe auch[Bearbeiten]