Zahlbasiswechsel

Dem Artikel oder Abschnitt fehlen Belege. Hilf, indem du sie recherchierst und einfügst.

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

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 wie das Duodezimalsystem, 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

Ist die Grundzahl n des Zielsystems eine positive ganzzahlige Potenz der Grundzahl m des Quellsystems (also n = mⁱ 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=bⁱ und n=b^j, 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=2³) ins Hexadezimalsystem (n=16=2⁴) ü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 b^z 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

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. 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

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

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.

Dieser Wikipedia-Artikel wurde, gemäß GFDL, CC-by-sa mit der kompletten History importiert.