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.
Noch keine Stimmen abgegeben
Noch keine Kommentare

Einordnung des Artikels

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.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 · 102 + 8 · 101 + 2 · 100.

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

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)8 aufdröseln und die Zahl ins Zehnersystem umrechnen:

(472)8 = 4 · 82 + 7 · 81 + 2 · 80 = 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).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)8)
  • 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.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)16.

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

(FA3)16 = 15 · 162 + 10 · 161 + 3 · 160.

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)16 = 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)16

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: . . . 16n, 16n−1, . . . , 161, 160
  • Entscheide durch Vergleich zwischen Z und den Zahlen der Liste, durch welche Potenz von 16 zuerst geteilt werden muss: Falls 16n < Z ≀ 16n−1, dann durch 16n−1.
  • 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 (160 = 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.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:

24 = 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)16 ist in Abbildung 6 unten zu sehen.

Abbildung 6: Zur Umrechnung einer Zahl aus dem Hexadezimalsystem in das Dualsystem.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:

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

  1. Berechnen Sie die HĂ€lfte sowie ein Viertel von (1000)16. Geben Sie die Ergebnisse als Hexadezimalzahl, als Dualzahl und als Dezimalzahl an.
  2. Die grĂ¶ĂŸte und die zweit-grĂ¶ĂŸte dreistellige Hexadezimalzahl sollen addiert werden. Wie lautet das Ergebnis als Hexadezimalzahl?
  3. Die zwei kleinsten vierstelligen Hexadezimalzahlen sollen miteinander multipliziert werden. Wie lautet das Ergebnis als Hexadezimalzahl?
  4. 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?
  5. 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 bn
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:

  1. 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?
  2. 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.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:

  1. An welchen Stellen geht in den Algorithmus ein, dass jetzt die Basis 16 ist (anstelle von 2)?
  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:

  1. 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.
  2. 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 x0 und x1, dem eingehenden Übertrag cin, dem Ergebnis y0 und dem entstehenden Übertrag cout (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.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 baseN-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)2 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:

  1. 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.
  2. 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:

  1. Passen Sie die Funktion print.number() so an, dass man sie auch im Hexadezimalsystem einsetzen kann.
  2. Schreiben Sie eine Funktion, die eine Zahl z, die gemĂ€ĂŸ obiger Konvention als Vektor kodiert ist, in eine Dezimalzahl umrechnet.
  3. 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.