Stellenwertsysteme und Umrechnung zwischen den wichtigsten Zahlensystemen: Dezimalsystem, Hexadezimalsystem, Dualsystem

In Stellenwertsystemen bildet man Zahlen, indem man Ziffern je nach ihrer Position mit einer Potenz der Basis gewichtet. Vorgestellt wird die allgemeine Definition eines Stellenwertsystems und die wichtigsten Vertreter: Dezimalsystem, Hexadezimalsystem, Dualsystem und Oktalsystem. Mir R-Skripten wird die Umrechnung zwischen Zahlensystemen durch eine Rekursion realisiert.

walter

29 Jan. 2019

Division mit Rest Dualsystem Stellenwertsystem Ziffer Hexadezimalsystem Rekursion Dezimalsystem Basis

Inhaltsverzeichnis

Einordnung des Artikels

Ausgewählte Kapitel der Mathematik (für Programmierer, Informatiker, Ingenieure und Naturwissenschaftler)
- Zahlentheorie
  - Teilbarkeit
    - Stellenwertsysteme und Umrechnung zwischen den wichtigsten Zahlensystemen: Dezimalsystem, Hexadezimalsystem, Dualsystem

Einführung

Wir sind so sehr mit unseren Zahlen im Dezimalsystem vertraut, dass es uns schwer fällt, scharf voneinander zu trennen:

Welche Rechenregeln sind allgemein – also in jedem Zahlensystem – gültig?
Welche Rechenregeln sind nur im Dezimalsystem gültig?

Um diese Fragen zu klären, soll im Folgenden kurz gezeigt werden:

Wie legt man ein spezielles Zahlensystem fest? Was versteht man unter der Basis eines Zahlensystems?
Welche Regeln gelten nur im speziellen Zahlensystem und welche sind allgemeingültig?
Was versteht man unter einem Stellenwertsystem?

Mit Hilfe dieser Begriffe fällt es dann leicht, andere Zahlensysteme zu untersuchen. Weil Computer intern mit Dualzahlen rechnen, werden das Hexadezimalsystem und das Dualsystem untersucht, speziell die Fragen:

Welche Konventionen verwendet man zum Rechnen im Hexadezimalsystem (Zahlensystem zur Basis 16)?
Wie rechnet man zwischen Zahlen im Dezimalsystem und Hexadezimalsystem um?
Wie rechnet man zwischen Zahlen im Hexadezimalsystem und im Dualsystem (Basis 2) um?

Das Zehnersystem und beliebige Zahlensysteme

Viele werden sich noch erinnern, wie mühsam es war etwa das 1×1 mit 7 zu lernen: Wie viel ist zum Beispiel 8 · 7 – wer kann die Antwort in weniger als einer Sekunde geben. Dagegen ist das 1×1 mit 10 kinderleicht – worin liegt eigentlich der Unterschied?!

Ein Blick auf den Zahlenstrahl soll die Problematik nochmal verdeutlichen: siehe Abbildung 1.

Abbildung 1: Der Zahlenstrahl.

Auf dem Zahlenstrahl folgt – ausgehend von der Null – eine Zahl nach der anderen. Es ist nicht einzusehen, warum eine Zahl wie die 10 eine besondere Stellung einnehmen soll.

Oder auch wenn man Rechenregeln wie

a + b = b + a oder a · (b + c) = a · b + a · c

betrachtet, die man durch Abzählen am Zahlenstrahl verifizieren kann. Diese Rechenregeln gelten für alle Zahlen und haben nichts mit der besonderen Rolle der Zahl 10 zu tun.

Wenn man sich dagegen vergegenwärtigt, wie wir die Zahlen benennen, so ist klar, dass wir eine Einteilung in Zehner-Schritten vornehmen – und für größere Zahlen in Hunderter-Schritten, in Tausender-Schritten und so weiter.

So kann man etwa eine Zahl wie 482 aufschlüsseln in:

482 = 4 · 100 + 8 · 10 + 2 · 1,

was sich etwas abstrakter schreiben lässt:

482 = 4 · 10² + 8 · 10¹ + 2 · 10⁰.

Spätestens jetzt erkennt man die spezielle Rolle der Zahl 10: Wir verwenden Ziffern, um Zahlen zu bilden; die Ziffern sind die einstelligen Zahlen 0, 1, 2, ..., 9. Je nachdem, an welcher Stelle eine Ziffer steht, hat sie eine andere Bedeutung. Im Beispiel der 482 oben steht die Ziffer 2 an letzter Stelle – der Einer; die Ziffer 8 steht an der Stelle der Zehner, die Ziffer 4 an der Stelle der Hunderter.

Allgemein bildet man Potenzen von 10, um einer Ziffer ihre Bedeutung zu geben: man zählt die Stellen von hinten ab (beginnend mit 0) und erhält so die Zahl, mit der die Basis 10 potenziert werden muss.

Damit sollte auch der Begriff Stellenwertsystem klar geworden sein: so ist zum Beispiel die Zahl 482 von der Zahl 842 zu unterscheiden, obwohl nur die Ziffern anders angeordnet wurden. Die Stelle, an der eine Ziffer steht, legt ihren Wert in der Zahl fest.

Die Zahl 10 hat ihre besondere Bedeutung nur dadurch erhalten, wie wir Zahlen aus Ziffern aufbauen und die Stellen mit Potenzen der 10 belegen. Deshalb ist auch das 1×1 mit 10 so einfach: Bei einer Multiplikation mit 10 wird eine 0 angehängt. Und dies ist keine allgemeingültige Rechenregel der Mathematik, sondern eine Regel, die lediglich im Zehnersystem richtig ist.

Abbildung 2 zeigt wie eine dreistellige Dezimalzahl durch ihre Ziffern dargestellt wird (Gleichung 1 und 2) und wie man eine Zahl mit beliebig vielen Stellen durch Ziffern darstellt (Gleichung 3 und 4).

Abbildung 2: Darstellung einer Dezimalzahl durch Ziffern.

Wer dies einmal durchschaut hat, kann auch sofort angeben, wie man ein beliebiges Zahlensystem definiert: Man legt sich eine Basis b fest sowie die erlaubten Ziffern, das sind jetzt alle Zahlen von 0 bis b-1. Und so wie oben die Zahl 482 mit Hilfe der Potenzen von 10 geschrieben wurde, schreibt man jetzt eine Zahl mit Hilfe der Potenzen von b.

Als Beispiel sei das Oktalsystem genannt: Die Basis ist 8, die Ziffern sind 0, 1, 2, 3, 4, 5, 6, 7.

Eine Zahl im Oktalsystem könnte dann etwa lauten: (472)₈.

Hier und im Folgenden wird die Konvention verwendet, dass Zahlen, die nicht dem Zehnersystem angehören mit ihrer Basis als Index geschrieben werden. Ohne Angabe einer Basis soll es sich um eine Zahl im Zehnersystem handeln.

Wie oben im Beispiel mit 482 kann man jetzt (472)₈ aufdröseln und die Zahl ins Zehnersystem umrechnen:

(472)₈ = 4 · 8² + 7 · 8¹ + 2 · 8⁰ = 4 · 64 + 7 · 8 + 2 = 256 + 56 + 2 = 314.

Wie eine Zahl aus einem beliebigen Zahlensystem (zur Basis b) durch Ziffern dargestellt wird, kann man leicht aus Abbildung 2 herleiten: Man muss

Die Menge der Ziffern anpassen: sie laufen jetzt von 0 bis b - 1 (in Gleichung 1 und 3).
Man muss bei der Berechnung der Zahl aus den Ziffern die Basis von 10 zu b ändern (Gleichung 2 und 4).

Aufgaben:

1. Abbildung 3 zeigt links eine einfache Addition – die Darstellung soll an das Verfahren erinnern, wie in der Grundschule addiert wird.

Formulieren Sie als Algorithmus, wie man bei diesem Verfahren vorgeht. Dabei sollen:

beliebig viele ganze Zahlen addiert werden (keine negativen Zahlen, keine Zahlen mit Nachkommastellen),
die Anzahl der Stellen jeder Zahl kann beliebig sein.

Abbildung 3: Beispiel einer Addition (links) und angedeutet einer Multiplikation (rechts).

2. Die Zahlen, die in Abbildung 3 links addiert werden, könnten auch aus dem Oktalsystem stammen.

Berechnen Sie das Ergebnis der Addition, wenn man die drei Summanden als Oktalzahlen interpretiert. (Lösung: (1443)₈)
Formulieren Sie den Algorithmus wie in der letzten Aufgabe für das Oktalsystem.

3. In Abbildung 3 ist rechts eine Multiplikation zu sehen. Formulieren Sie den Algorithmus, mit dem die sogenannte schriftliche Multiplikation durchgeführt wird.

Das Hexadezimalsystem

Nachdem jetzt geklärt ist, was man unter einem Stellenwertsystem versteht, kann man die wichtigsten Beispiele etwas genauer ansehen: Relevant sind insbesondere das Dualsystem und das Hexadezimalsystem.

Computer rechnen intern mit dem Dualsystem; da Menschen damit nur schwer zurecht kommen, werden Rechnungen aus dem Dualsystem oft im Hexadezimalsystem dargestellt. Dies wirkt auf den ersten Blick wie ein unnötiger Umweg; bald wird aber gezeigt, dass das Dualsystem und das Hexadezimalsystem eng miteinander verwandt sind, so dass die Umrechnung zwischen diesen beiden Stellenwertsystemen sehr einfach ist.

Ziffern im Hexadezimalsystem

Das Hexadezimalsystem besitzt die Basis 16, somit sind die Ziffern die Zahlen von 0 bis 15. Aber hier ergibt sich schon das erste Problem: Im Zehnersystem waren die Ziffern die einstelligen Zahlen; wenn jetzt 10 eine Ziffer sein soll, muss man festlegen, wann 10 wie eine Ziffer und wann wie eine zweistellige Zahl (zusammengesetzt aus den Ziffern 1 und 0) zu lesen ist. Um die Typographie nicht unnötig aufzublähen und da Buchstaben innerhalb von Zahlen nicht vorkommen können, hat man die Übereinkunft getroffen, dass die Ziffern 10 bis 15 durch die Buchstaben A bis F dargestellt werden (siehe Abbildung 4).

Abbildung 4: Die Ziffern im Hexadezimalsystem.

Man beachte, dass 16 die Basis des Hexadezimalsystems ist, aber keine Ziffer – im Zehnersystem ist auch 10 keine Ziffer, sondern die kleinste zweistellige Zahl.

Umrechnung vom Hexadezimalsystem ins Dezimalsystem

Eine typische Zahl im Hexadezimalsystem könnte somit lauten: (FA3)₁₆.

Wie man diese Zahl in das Zehnersystem umrechnet, wurde oben schon allgemein erklärt. Es gilt:

(FA3)₁₆ = 15 · 16² + 10 · 16¹ + 3 · 16⁰.

Dabei wurde verwendet:

Die Ziffern F und A wurden in 15 und 10 übersetzt,
gemäß dem Stellenwertsystem wurden die Potenzen von 16 als Faktoren den Ziffern hinzugefügt.

Man erhält:

(FA3)₁₆ = 15 · 256 + 160 + 3 = 4003.

Wer das Stellenwertsystem verstanden hat, kann ganz leicht aus einem beliebigen Zahlensystem in das Zehnersystem umrechnen. Schwieriger ist die umgekehrte Rechnung.

Umrechnung vom Dezimalsystem ins Hexadezimalsystem

Es soll jetzt ein Algorithmus entwickelt werden, mit dem man jede Zahl aus dem Zehnersystem in eine Hexadezimalzahl umrechnen kann. Als Beispiel wird zunächst die Zahl 4003 von oben genommen, anschließend wird der Algorithmus allgemein formuliert.

Wie erhält man die Zahl im Hexadezimalsystem, die der Zahl 4003 (aus dem Dezimalsystem) entspricht? Man muss nur die richtigen Fragen stellen, dann ergeben sich die Rechnungen fast von alleine!

1. Frage:

Wie viele Stellen hat die gesuchte Hexadezimalzahl?

Oder genauer: Wie kann ich aus der gegebenen Zahl 4003 und der Basis 16 ablesen, wie viele Stellen die gesuchte Zahl hat?

Man bildet dazu die Potenzen von 16:

1, 16, 256, 4096, 65536, 1048576, ...,

wobei es vielleicht hilfreicher ist, diese Liste in umgekehrter Reihenfolge anzugeben:

..., 1048576, 65536, 4096, 256, 16, 1.

Da die gegebene Zahl 4003 zwischen 4096 und 256 liegt, ist klar, dass die gesuchte Hexadezimalzahl 3 Stellen belegen muss. Würde man auch die vierte Stelle belegen, ergibt sich eine Zahl größer oder gleich 4096.

2. Frage:

Welche Ziffer steht an der ersten (vordersten) Stelle der gesuchten Zahl?

Oder genauer: Durch welche Rechnung kann man die erste Ziffer bestimmen?

Die erste der drei Ziffern steht für die 256er, also muss man berechnen, wie oft die 256 in die 4003 passt. Die gesuchte Berechnung ist daher die Division

4003 : 256.

Diese Division wird nicht mit dem Taschenrechner und einer Zahl mit Nachkommastellen als Ergebnis durchgeführt, sondern als die Division mit Rest:

4003 : 256 = 15 Rest 163.

Wer sich an das schriftliche Dividieren aus der Grundschule erinnern kann, sollte noch wissen, wie man hier vorgeht. Die Begründung für das Ergebnis ist die Tatsache, dass

15 · 256 = 3840 und 4003 - 3840 = 163 oder anders formuliert: 4003 = 15 · 256 + 163.

Die Zahl 256 passt somit 15 mal in die 4003, wobei ein Rest von 163 bleibt. Die Ziffer an der führenden Stelle der gesuchten Hexadezimalzahl ist F (entspricht 15).

3. Frage:

Wie erhält man die Ziffern an den weiteren Stellen der Hexadezimalzahl?

Der Rest, der oben bei der Division bleibt, muss für die Belegung der weiteren Stellen verantwortlich sein. Die nächste zu belegende Stelle sind die 16er.

Man teilt daher 163 durch 16 und erhält:

163 : 16 = 10 Rest 3.

Aber damit hat man schon das Endergebnis: 10 wird in A übersetzt, 3 steht für 3 Einer und es gilt:

4003 = (FA3)₁₆

Versucht man die Vorgehensweise, wie 4003 in eine Hexadezimalzahl verwandelt wurde, allgemein zu formulieren, erhält man folgenden Algorithmus:

Schreibe die Potenzen von 16 in umgekehrter Reihenfolge auf: . . . 16ⁿ, 16ⁿ⁻¹, . . . , 16¹, 16⁰
Entscheide durch Vergleich zwischen Z und den Zahlen der Liste, durch welche Potenz von 16 zuerst geteilt werden muss: Falls 16ⁿ < Z ≤ 16ⁿ⁻¹, dann durch 16ⁿ⁻¹.
Führe diese Division als Division mit Rest durch, sie liefert als Ergebnis eine Zahl zwischen 0 und 15 sowie einen Rest.
Widerhole den letzten Schritt (jeweils Division des Restes durch die nächste Potenz von 16 in der Liste) bis das Ende der Liste (16⁰ = 1) erreicht ist.
Sammle die Ergebnisse der Divisionen auf (in der Reihenfolge, in der die Divisionen durchgeführt wurden) und verwandle sie in Ziffern des Hexadezimalsystems. Dies ist die gesuchte Hexadezimalzahl.

Aufgabe:

Formulieren Sie den Algorithmus so um, dass man eine Dezimalzahl in eine Dualzahl umrechnen kann.

Umrechnung zwischen Dualsystem und Hexadezimalsystem

Oben wurde behauptet, dass das Dualsystem und das Hexadezimalsystem eng miteinander verwandt sind. Worin besteht die Verwandtschaft? Abbildung 5 gibt den entscheidenden Hinweis.

Abbildung 5: Potenzen von 2, von 16 und von 10.

Der Algorithmus oben hat gezeigt, dass man zum Umrechnen zwischen den Zahlensystemen die Potenzen der Basis benötigt. Abbildung 5 zeigt die Potenzen von 2, von 16 und von 10.

Es ist sofort auffällig:

Jede Zahl, die in der Liste der Potenzen von 16 vorkommt, ist auch in den Potenzen von 2 enthalten.
Betrachtet man die zugehörigen Abstände, so muss man in der Liste der Potenzen von 2 um 4 Schritte weitergehen, wenn man in der Liste der Potenzen von 16 um einen Schritt weitergeht.
Dagegen kommt keine Zahl aus den Potenzen von 10 in den anderen Listen vor (und umgekehrt).

Die letzte Beobachtung kann man leicht erklären: Durch Multiplikation mit 10 entstehen immer Zahlen, die als letzte Ziffer eine 0 haben. In den Listen zur Basis 2 und 16 kann keine Zahl mit der Ziffer 0 am Ende vorkommen (6 · 6 = 36, daher enden alle Potenzen von 16 auf 6; bei den Potenzen von 2 kommen als Endziffern alle geraden Zahlen außer der 0 vor).

Wie erklärt sich die Beziehung zwischen den Potenzen von 2 und von 16? Klar es gilt:

2⁴ = 16

Oder salopp ausgedrückt: 4 Multiplikationen mit 2 entsprechen einer Multiplikation mit 16.

Und diese Beziehung kann man verwenden, um die Regel zu formulieren, wie zwischen dem Dualsystem und dem Hexadezimalsystem umgerechnet wird. Man muss nur wieder die richtigen Fragen stellen:

Wie viele Stellen hat eine Dualzahl, die einer einstelligen Hexadezimalzahl entspricht?
Wie viele Stellen hat eine Dualzahl, die einer zweistelligen Hexadezimalzahl entspricht?
Wie viele Stellen hat eine Dualzahl, die einer dreistelligen Hexadezimalzahl entspricht?
Und so weiter.

Ein Blick auf die Potenzen von 2 und von 16 in Abbildung 5 oben gibt sofort die Antworten:

Eine einstellige Hexadezimalzahl ist kleiner als 16 und wird in eine Dualzahl mit maximal 4 Stellen umgewandelt.
Eine zweistellige Hexadezimalzahl ist kleiner als 256 und wird in eine Dualzahl mit maximal 8 Stellen umgewandelt.
Eine dreistellige Hexadezimalzahl ist kleiner als 4096 und wird in eine Dualzahl mit maximal 12 Stellen umgewandelt.
Und so weiter.

Aber das kann man auch so formulieren:

Jede Ziffer einer Hexadezimalzahl wird in eine vierstellige Dualzahl umgewandelt (wenn man führende Nullen mitrechnet).
Um eine Hexadezimalzahl umzuwandeln, werden Viererblöcke vorbereitet – für jede Ziffer ein Viererblock.
Wandelt man jetzt nacheinander die Hexadezimal-Ziffern in Dualzahlen um und schreibt sie in den entsprechenden Viererblock, hat man die gesuchte Dualzahl gefunden.

Damit hat man schon den Algorithmus formuliert, den man auf eine beliebige Hexadezimalzahl anwenden kann. Ein Beispiel – wieder mit der Zahl (FA3)₁₆ ist in Abbildung 6 unten zu sehen.

Abbildung 6: Zur Umrechnung einer Zahl aus dem Hexadezimalsystem in das Dualsystem.

Für die Umwandlung in umgekehrter Richtung muss man nur umgekehrt vorgehen: Man unterteilt eine Dualzahl (ausgehend von ihrem Ende) in Viererblöcke und verwandelt jeden Viererblock in eine Hexadezimal-Ziffer.

Aufgabe

Formulieren Sie den Algorithmus zur Umwandlung einer beliebigen Dualzahl in eine Hexadezimalzahl.

Mechanische Realisierung eines Zählers

Eine elektronische Realisierung eines Zählers mit Hilfe von Toggle-Flip-Flops wird in Schaltwerke in Die Komponenten des von Neumann Rechners: elektrotechnische Grundlagen diskutiert. Vergegenwärtigt man sich, wie das Zählen in einem Zahlensystem mit Basis b vonstatten geht, ist es nicht mehr schwer, sich eine mechanische Realisierung eines Zählers zu überlegen.

Zählen von 0 bis 15 im Dualsystem (die Zahl 16 kann nicht mehr als vierstellige Zahl dargestellt werden – und man beachte, dass die Zeilennummern bei 1 beginnen):

(0000)_2 
(0001)_2 
(0010)_2 
(0011)_2 
(0100)_2 
(0101)_2 
(0110)_2 
(0111)_2 
(1000)_2 
(1001)_2 
(1010)_2 
(1011)_2 
(1100)_2 
(1101)_2 
(1110)_2 
(1111)_2

Zählen von 0 bis 26 im Zahlensystem zur Basis 3 (die Zahl 27 kann nicht mehr als vierstellige Zahl dargestellt werden – und man beachte, dass die Zeilennummern bei 1 beginnen):

(000)_3 
(001)_3 
(002)_3 
(010)_3 
(011)_3 
(012)_3 
(020)_3 
(021)_3 
(022)_3 
(100)_3 
(101)_3 
(102)_3 
(110)_3 
(111)_3 
(112)_3 
(120)_3 
(121)_3 
(122)_3 
(200)_3 
(201)_3 
(202)_3 
(210)_3 
(211)_3 
(212)_3 
(220)_3 
(221)_3 
(222)_3

Für jede Stelle wird eine Walze vorbereitet, die mit den Ziffern 0, 1, 2, ..., b - 1 beschriftet ist (b ist die Basis des Zahlensystems). Hochzählen um 1 wird dann mechanisch übersetzt in ein Weiterdrehen der Walze, so dass die nächste Ziffer erscheint. Allerdings muss man hier zwei Fälle unterscheiden:

Die aktuelle Ziffer auf der letzten Walze (diejenige für die Einer) ist kleiner als b - 1: die Einer-Walze wird um 1 weitergedreht – die dargestellte Zahl hat sich um 1 vergrößert.
Die aktuelle Ziffer ist gleich b - 1: Jetzt wird die letzte Walze (Einer-Walze) um 1 weitergedreht, so dass die 0 erscheint. Und gleichzeitig wird die nächste Walze mitgezogen, also auch um 1 weitergedreht. Dieses Mitziehen wird so lange fortgesetzt, bis man bei einer Walze ankommt, deren aktueller Wert kleiner als b - 1 ist.

Aufgabe: Identifizieren Sie diese beiden Fälle in den Tabellen oben.

Wie man sich an den Tabellen oben leicht überlegt, entspricht das Mitziehen der nächsten Walze gerade dem Übertrag.

Früher waren tatsächlich Kilometerzähler im Auto derart mechanisch realisiert (siehe Abbildung 7). Und daher wusste man etwa bei der Anzeige 34 567 auf dem Kilometerzähler nicht, ob das Auto 34 567 Kilometer auf dem Buckel hatte oder 134 567 oder 234 567 oder ... Denn bei dieser Zählweise (im Zehnersystem) folgt auf die Zahl 99 999 die Zahl 00 000, falls 5 Stellen zur Verfügung stehen.

Abbildung 7: Kilometerzähler mit 5 Stellen, der gerade 99999 km anzeigt. Jede Stelle ist durch eine Walze realisiert, die mit den Ziffern von 0 bis 9 beschriftet ist.

Nebenbei: Eine Uhr (mit der Bewegung des Stunden-Zeigers) ist eine Walze für das 12er-System; sie wird nur immer falsch beschriftet, nämlich von 1 bis 12 und nicht von 0 bis 11.

Aufgaben

Für die folgenden Aufgaben gibt es jeweils mehrere Lösungswege. Bevor Sie einen Weg einschlagen: Versuchen Sie die möglichen Wege zu skizzieren und entscheiden Sie sich für den einfachsten Weg.

Berechnen Sie die Hälfte sowie ein Viertel von (1000)₁₆. Geben Sie die Ergebnisse als Hexadezimalzahl, als Dualzahl und als Dezimalzahl an.
Die größte und die zweit-größte dreistellige Hexadezimalzahl sollen addiert werden. Wie lautet das Ergebnis als Hexadezimalzahl?
Die zwei kleinsten vierstelligen Hexadezimalzahlen sollen miteinander multipliziert werden. Wie lautet das Ergebnis als Hexadezimalzahl?
Farben werden im RGB-Modus (Rot-, Grün- und Blau-Anteil) als sechsstellige Hexadezimalzahlen kodiert; jeweils zwei Stellen stehen für eine der drei Grundfarben.
- Wie viele Farben können gebildet werden?
- Kommen in allen drei Farben jeweils zwei identische Ziffern vor, so reicht es, die Ziffer einmal anzugeben: EEAA33 kann durch EA3 abgekürzt werden. Wie viele Farben mit abgekürzter Schreibweise gibt es?
Weiter unten wird ein Algorithmus angegeben, der eine Dezimalzahl in eine Hexadezimalzahl umrechnet. Der Algorithmus verwendet eine Rekursion und arbeitet völlig anders als der Algorithmus, der oben vorgestellt wurde. Formulieren Sie diese Algorithmus in einer Form, so dass er auch von Menschen zur Umrechnung von Dezimalzahlen zu Hexadezimalzahlen verwendet werden kann.

Zusammenfassung

Die folgende Tabelle zeigt die wichtigsten Eigenschaften der hier besprochenen Zahlensysteme:

Zahlensystem	Basis b	Ziffern	"runde" Zahlen bⁿ
Dezimalsystem	10	0, 1, 2, 3, 4, 5, 6, 7, 8, 9	1, 10, 100, 1000, ...
Hexadezimalsystem	16	0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F	1, 16, 256, 4096, 65536, ...
Oktalsystem	8	0, 1, 2, 3, 4, 5, 6, 7	1, 8, 64, 512, 4096, ...
Dualsystem	2	0, 1	1, 2, 4, 8, 16, 32, 64, ...

R-Skripte

Umwandlung einer Dezimalzahl in eine Dualzahl

Berechnung mit Hilfe einer Rekursion

Oben war als Aufgabe formuliert, eine Dezimalzahl in eine Dualzahl zu verwandeln, wobei der Algorithmus angepasst werden sollte, der für Hexadezimalzahlen ausführlich besprochen wurde. Das Vorgehen in diesem Algorithmus entspricht sehr dem menschlichen Denken (wie durch die Formulierung der Fragen gezeigt werden sollte). Diesen Algorithmus in ein Programm umzusetzen, ist sehr kompliziert – es gibt einen viel einfacheren Algorithmus, der mit wenigen Zeilen Quelltext auskommt. Dazu wird eine Funktion definiert, die rekursiv aufgerufen wird. Die Rekursion sorgt dafür, dass der Algorithmus sehr schlank wird, hat aber den Nachteil, dass er für den Menschen schwerer verständlich ist (als der oben besprochene Algorithmus)

Das folgende Skript zeigt eine R-Implementierung; das Ergebnis (die Dualzahl) wird dabei nicht abgespeichert, sondern sofort auf der Konsole ausgegeben. Der Algorithmus beruht auf der Ganzzahl-Division %/% und der Berechnung des Restes %% :

decToBin <- function(n){
  if(n < 2){
    cat(n)
    return()
  }
  k <- n %/% 2
  r <- n %% 2
  decToBin(n = k)
  cat(r)
}

Aufgabe:

Führen Sie für diesen Algorithmus den Trockentest mit den Werten n = 0, 1, 2, 13, 16 durch. Warum sind Zahlen wie 9 oder 15 für einen Trockentest wenig geeignet?
Schreiben Sie eine Version von decToBin(n) , die die Dualzahl nicht auf der Konsole ausgibt sondern zurückgibt. Welcher geeignete Datentyp bietet sich für den Rückgabewert an?

Erklärung der rekursiven Umrechnung

Entscheidend für den Algorithmus oben ist, in welcher Reihenfolge

die Funktion decToBin() rekursiv aufgerufen wird und
wann die Konsolenausgaben mit cat() stattfinden.

Für den Eingabewert n = 13 soll dies durchgespielt werden. Die wichtigsten Schritte, insbesondere die aktuellen Werte von k und r aus der Gleichung n = k · 2 + r, sind in Abbildung 8 zu sehen; ob der if-Zweig betreten wird, ist nicht dargestellt.

1. Aufruf von decToBin() , mit n = 13:

Der if-Zweig wird nicht betreten.
Da 13 = 6 · 2 + 1, ist k = 6 und r = 1.
Die Funktion decToBin() wird mit n = 6 aufgerufen.
Da zuerst decToBin() und dann erst die Konsolenausgabe erfolgt, gibt es jetzt noch keine Ausgabe; diese erfolgt erst, wenn die Ausführung von decToBin(n = 6) beendet ist.

2. Aufruf von decToBin() , mit n = 6:

Der if-Zweig wird wieder nicht betreten.
Da 6 = 3 · 2 + 0, ist k = 3 und r = 0.
Die Funktion decToBin() wird mit n = 3 aufgerufen.
Der Aufruf von cat() geschieht wieder erst nach der Ausführung von decToBin(n = 3) .

3. Aufruf von decToBin() , mit n = 3:

Der if-Zweig wird wieder nicht betreten.
Da 3 = 1 · 2 + 1, ist k = 1 und r = 1.
Die Funktion decToBin() wird mit n = 1 aufgerufen.
Es erfolgt wieder kein Aufruf von cat() .

4. Aufruf von decToBin() , mit n = 1:

Jetzt wird der if-Zweig betreten.
Es erfolgt die Ausgabe cat(n) mit n = 1. Erste Ausgabe: 1.
Im if-Zweig befindet sich das return-statement, somit ist der Aufruf decToBin(n = 1) beendet.
Da decToBin(n = 1) von der Funktion decToBin(n = 3) aufgerufen wurde, kehrt man zu dieser Funktion zurück und deren Abarbeitung wird fortgesetzt.

Rückkehr in den 3. Aufruf von decToBin() , mit n = 3:

In decToBin(n = 3) wird nach dem Aufruf von decToBin(n = 1) nur noch der cat()-Befehl ausgeführt.
Dabei wird der aktuelle Wert von r, nämlich 1, ausgegeben. Zweite Ausgabe: 1.
Damit ist die Abarbeitung von decToBin(n = 3) beendet.
Man kehrt dorthin zurück, wo diese Funktion aufgerufen wurde.

Rückkehr in den 2. Aufruf von decToBin() , mit n = 6:

Wieder ist noch der cat()-Befehl abzuarbeiten, jetzt mit r = 0. Dritte Ausgabe: 0.
Die Abarbeitung ist beendet, Rückkehr zu ihrem Aufruf.

Rückkehr in den 1. Aufruf von decToBin() , mit n = 13:

Hier fehlt wiederum nur der cat()-Befehl, nämlich mit r = 1. Vierte Ausgabe: 1.

Gesamtergebnis:

Auf der Konsole wird 1101 ausgegeben. Zur Kontrolle: 8 + 4 + 0 + 1 = 13.

Abbildung 8: Darstellung der Befehlsabarbeitung beim Aufruf von decToBin(n = 13); die Rekursion sorgt für drei weitere Aufrufe der Funktion decToBin(). Gezeigt sind nur die jeweils relevanten Werte von k und r, die Aufrufe von decToBin() und die Ausgaben mit cat(). Nur beim vierten Aufruf von decToBin() wird der if-Zweig betreten und dort die Ausgabe ausgelöst; bei den anderen drei Aufrufen wird der if-Zweig übersprungen und die Ausgabe erfolgt erst nachdem der rekursive Aufruf von decToBin() abgearbeitet wurde.

Umwandlung einer Dezimalzahl in eine Hexadezimalzahl

Da jetzt der Algorithmus bekannt ist, wie man eine Dezimalzahl in eine Dualzahl umrechnen kann, ist es nicht mehr schwer, eine Dezimalzahl in eine Hexadezimalzahl umzuwandeln. Die entsprechende Funktion wird dann decToHex() genannt.

Ausgehend von obigem Skript muss man nur zwei Fragen klären:

An welchen Stellen geht in den Algorithmus ein, dass jetzt die Basis 16 ist (anstelle von 2)?
Wie sorgt man dafür, dass die Ziffern A, B, ..., F gebildet werden.

Zur ersten Frage:

Im Skript kommt an drei Stellen die Zahl 2 vor. Bedenkt man, welche Berechnungen dabei ausgeführt werden, erkennt man schnell, dass die 2 hier immer die Rolle der Basis des Zahlensystems hat. Man kann sattdessen 16 einsetzen.

Zur zweiten Frage:

Die Funktion decToBin() gibt nacheinander Ziffern (im Dualsystem) auf der Konsole aus; dies geschieht an zwei unterschiedlichen Stellen:

Innerhalb des if-Zweiges, wenn decToBin() mit einer Zahl n < 2 aufgerufen wird – also mit einer Ziffer. Hier muss man dafür sorgen, dass die richtige Hexadezimal-Ziffer ausgegeben wird.
Nach dem if-Zweig wird der Rest r ausgegeben, der ja auch eine Ziffer sein muss.

Nachdem man diese beiden Stellen identifiziert hat, muss man dafür sorgen, dass eine Zahl 0, 1, 2, ..., 14, 15 in eine Hexadezimal-Ziffer 0, 1, ..., E, F umgerechnet wird. Dies geschieht am einfachsten mit Hilfe einer Funktion getHexDigit(n) ; das folgende Skript zeigt eine mögliche Implementierung:

# Erzegt zu einer Zahl n < 16 die zugehörige Hexadezimal-Ziffer
getHexDigit <- function(n){
  stopifnot(n < 16)
  if(n < 10) return(n)
  else{         # n = 10, 11, ..., 15
    x <- switch(EXPR = (n - 9), 'A', 'B', 'C', 'D', 'E', 'F')
    return(x)
  }
}

Man beachte, dass der Rückgabewert entweder eine Zahl oder ein Zeichen ist; da mit ihm aber nicht weitergerechnet wird, spielt dies keine Rolle (die Ziffer wird lediglich auf der Konsole ausgegeben).

Für die Rekursion decToHex() wird dann decToBin() als Vorlage genommen und die Hexadezimal-Ziffer wird mit getHexDigit() berechnet:

#    Umwandlung einer Dezimalzahl n in eine Hexadezimalzahl
#    kein Rückgabewert; das Ergebnis wird sofort auf der Konsole ausgegeben
decToHex <- function(n){
  if(n < 16){
    h <- getHexDigit(n)
    cat(h)
    return()
  }
  k <- n %/% 16             # Ganzzahldivision
  r <- getHexDigit(n = (n %% 16))       # Rest
  decToHex(n = k)
  cat(r)
}

Realisierung eines Zählers in einem beliebigen Zahlensystem

Oben wurde erklärt, wie ein mechanischer Zähler arbeitet, ebenso wurde auf den elektronischen Zähler verwiesen, der auf Toggle-Flip-Flops beruht.

In der Elektronik muss man scharf zwischen dem Ein-Bit-Halb-Addierer und dem Ein-Bit-Voll-Addierer unterscheiden.

Der Ein-Bit-Halb-Addierer addiert zwei Bits und erzeugt keinen Übertrag, das Ergebnis der Addition ist somit nur die letzte Stelle des eigentlichen Ergebnisses. Bei 0 + 0, 1 + 0, 0 + 1 erzeugt der Ein-Bit-Halb-Addierer somit das richtige Ergebnis, nicht aber bei 1 + 1: jetzt ist das Ergebnis gleich 0.

Dagegen berücksichtigt der Ein-Bit-Voll-Addierer sowohl den eingehenden Übertrag als auch den eventuell neu erzeugten Übertrag. Die folgende Abbildung 9 zeigt die logische Tabelle des Ein-Bit-Voll-Addierers mit den zu addierenden Zahlen x₀ und x₁, dem eingehenden Übertrag c_in, dem Ergebnis y₀ und dem entstehenden Übertrag c_out (c wie carry-bit).

Abbildung 9: Links: Logische Tabelle des Ein-Bit-Voll-Addierers. Falls Cin = 0, stimmt die logische Tabelle natürlich mit der des Halb-Addierers überein (obere Hälfte der Tabelle). Für Cin = 1 ergeben sich neue Werte. Rechts: Schaltzeichen des Ein-Bit-Voll-Addierers.

Vergleicht man dies mit dem mechanischen Zähler, so entspricht dem Weiterdrehen einer Walze einer Halbaddition und die Verbindungen zwischen den Walzen entsprechen dem Übertrag.

Um einen Zähler in einem beliebigen Zahlensystem zu realisieren – wofür es wieder unzählige Möglichkeiten gibt –, kann man zum Beispiel auf den Ein-Bit-Halb-Addierer zurückgreifen, der im folgenden Skript implementiert wird:

add.1 <- function(z, base){
  stopifnot(base > 1)
  stopifnot(z < base)
  if(identical(z, base - 1)) return(0)
  else return(z + 1)
}

Die Funktion add.1(z, base) addiert 1 zu einer Zahl z, erzeugt dabei aber keinen Übertrag. Falls z == (base - 1) , erhält man 0. Dies entspricht somit einer einzigen Walze, die mit 0, 1, ..., (base - 1) beschriftet ist und die mit add.1(z, base) um eine Position weitergedreht wird.

Um einen Zähler für Zahlen mit beliebig vielen Stellen zu realisieren, wird folgende Konvention getroffen, die vielleicht etwas verwirrend ist: Eine N-stellige Zahl z in einem Zahlensystem mit Basis base wird durch einen Vektor der Länge N dargestellt, wobei die Einer an erster Stelle stehen. An der letzten Stelle steht somit die Ziffer für die höchste Potenz base^N-1.

Diese Konvention mag verwirrend sein, hat aber den Vorteil, dass man führende Nullen in der Vektor-Repräsentation einfach hinten anhängen kann. Möchte man zum Beispiel die Zahl (0000 1010)₂ als Vektor darstellten, so lautet er (0, 1, 0, 1, 0, 0, 0, 0). Und möchte man zu einer 12-stelligen Darstellung übergehen, werden 4 weitere Nullen hinten angehängt. Ebenso erleichtert diese Konvention die Umrechnung ins Zehnersystem.

Das folgende Skript zeigt nun zwei Funktionen:

Eine Funktion print.number(z, base, N) , die eine Zahl z (im Zahlensystem mit Basis base) N-stellig ausgibt, eventuell mit führenden Nullen. Sie erzeugt zudem Klammern mit Index, um sofort die Basis abzulesen. Die Funktion in der gegebenen Form kann nur für Basen kleiner oder gleich 10 verwendet werden, da in der Ausgabe nicht zwischen ein- und mehrstelligen Ziffern unterschieden werden kann.
Eine Funktion next.number(z, base, N) , die zu einer Zahl z (die nach obiger Konvention als Vektor gegeben ist) 1 addiert. Rückgabewert ist die Zahl z + 1, natürlich gemäß der Konvention als Vektor kodiert. Reichen zur Darstellung des Ergebnisses N Stellen nicht mehr aus, wird NA zurückgegeben.

print.number <- function(z, base, N){
  stopifnot(length(z) <= N)
  stopifnot(base < 11 && base > 1)
  stopifnot(N > 0)
  
  number <- paste0(rev(z), collapse = "")
  zeroes <- N - length(z)    # Anzahl der führenden Nullen
  cat(paste("(", paste0(rep(x = 0, times = zeroes), collapse = ""), number, ")_", base, sep = ""), "\n")
}

next.number <- function(z, base, N){
  stopifnot(length(z) <= N)
  stopifnot(base > 1)
  stopifnot(N > 0)
  
  n <- 1; c <- 1    # n: Index des Vektors; c: carry-Bit
  
  while(identical(c, 1)){
    # Carry-Bit ist gesetzt und alle Stellen maximal: return(NA)
    if(identical(z, rep(x = base - 1, times = N))){
      return(rep(x = NA, times = N))
    }
    # Carry-Bit zurücksetzen
    if(z[n] < base - 1) c <- 0
    z[n] <- add.1(z = z[n], base)    # Halbaddition
    n <- n + 1
  }
  return(z)
}

Zählt man jetzt ausgehend von 0 bis 16 im Dualsystem, erhält man:

# Zählen von 0 bis 16 im 2-System

z <- rep(x = 0, times = 4)

for(i in (1:17)){
  print.number(z = z, base = 2, N = 4)
  z <- next.number(z = z, base = 2, N = 4)
}
# (0000)_2 
# (0001)_2 
# (0010)_2 
# (0011)_2 
# (0100)_2 
# (0101)_2 
# (0110)_2 
# (0111)_2 
# (1000)_2 
# (1001)_2 
# (1010)_2 
# (1011)_2 
# (1100)_2 
# (1101)_2 
# (1110)_2 
# (1111)_2 
# (NANANANA)_2

In Zeile 19 bis 21 in print.number() wird dafür gesorgt, dass ein Überlauf den Vektor mit Komponenten NA erzeugt; lässt man diese Anweisung weg, beginnt man wieder bei einem Vektor, in dem alle Komponenten gleich 0 sind (wie beim Kilometerzähler).

Aufgaben:

Passen Sie die Funktion print.number() so an, dass man sie auch im Hexadezimalsystem einsetzen kann.
Schreiben Sie eine Funktion, die eine Zahl z, die gemäß obiger Konvention als Vektor kodiert ist, in eine Dezimalzahl umrechnet.
Die Funktion next.number() arbeitet mit einer Stellen-Anzahl, die man beim Aufruf der Funktion zwar setzen kann, die Funktion ist aber nicht in der Lage die Stellen-Anzahl anzupassen, wenn N nicht mehr ausreicht. Schreiben Sie eine verbesserte Version, die die Stellen-Anzahl dynamisch anpasst, aber immer nur so groß wie nötig macht.