---

Aufgabe Operationen auf der Binärdarstellung

Letzte Änderung: 13. November 2020, 16:49 Uhr
20 Punkte — im Detail
Ansicht:   |  

Die einfachste Repräsentation einer (nichtnegativen) Ganzzahl ist die Binärdarstellung, mit der Sie alle bereits vertraut sein sollten. Das ist auch die Darstellung, die in modernen Prozessoren verwendet wird. Für manche Anwendungen ist es nötig, direkt mit der Binärdarstellung einer Zahl zu arbeiten. In anderen Fällen kann ein Arbeiten mit der Binärdarstellung Ihren Code signifikant beschleunigen. Zum Arbeiten mit der Binärdarstellung bietet C++ die Operatoren ~, &, |, <<, >>, ^, die Sie in der Vorlesung oder im Tutorium kennenlernen werden.

Aufgabenteil A:

1. Erklären Sie, warum bei einer vorzeichenlosen Binärzahl ein Linksshift gerade einer Multiplikation mit 2 entspricht. Was passiert, wenn das höchste Bit (most significant bit) des Datentyps vor dem Shift auf 1 gesetzt war?
2. Auch Dezimalzahlen lassen sich stellenweise nach links oder rechts verschieben. Was bewirkt ein Linksshift einer Zahl im Dezimalsystem?
3. Recherchieren und erklären Sie den Unterschied zwischen einem arithmetischen und einem logischen Rechtsshift. Finden Sie heraus, welche der beiden Versionen von Ihrem Compiler implementiert wird, und beschreiben Sie kurz, wie Sie das herausgefunden haben.

Aufgabenteil B:
Im Folgenden wollen wir Operationen auf einzelnen Bits eines uint64_t implementieren. Wir nummerieren die Bits so, dass das niederwertigste (least significant bit / „rechteste“) Bit den Index 0 bekommt und das höchstwertigste (most significant bit / „linkeste“) den Index 63.

1. Schreiben Sie eine Funktion extract, die eine Zahl \(z\) vom Typ uint64_t und eine Zahl \(n\) vom Typ int32_t nimmt und genau dann true zurückgibt, wenn das n-te Bit in \(z\) gesetzt ist.
2. Schreiben Sie eine Funktion set, die eine Zahl \(z\) vom Typ uint64_t und eine Zahl \(n\) vom Typ int32_t nimmt und das n-te Bit in \(z\) auf 1 setzt.
3. Schreiben Sie eine Funktion clear, die eine Zahl \(z\) vom Typ uint64_t und eine Zahl \(n\) vom Typ int32_t nimmt und das n-te Bit in \(z\) auf 0 setzt.
4. BONUS: Die Funktionen sind natürlich nur für 0 <= n < 64 sinnvoll. Modifizieren Sie die Funktionen so, dass sie die Stellen rückwärts durchlaufen, wenn -64 <= n < 0 ist (analog zur Listenindizierung in Python).
5. Schreiben Sie eine Funktion print, die eine Zahl \(z\) vom Typ uint64_t nimmt und die Binärdarstellung auf der Konsole ausgibt.
6. Schreiben Sie eine Funktion upper, die eine Zahl \(z\) vom Typ uint64_t nimmt und die Zahl zurückgibt, die durch die oberen ("höherwertigen") 32 Bit von z dargestellt wird.
7. Schreiben Sie eine Funktion lower, die eine Zahl \(z\) vom Typ uint64_t nimmt und die Zahl zurückgibt, die durch die unteren ("niederwertigen") 32 Bit von z dargestellt wird.

Aufgabenteil C:
Eine andere Repräsentation einer Ganzzahl ist „Binary Coded Decimal“ (BCD). Hierbei werden vier aufeinanderfolgende Binärstellen einer Zahl als Dezimalstelle interpretiert, die nur die Werte 0 bis 9 annehmen darf. Ein uint64_t kann auf diese Weise 16 Dezimalstellen darstellen.

1. Wieviele Dezimalstellen kann ein uint64_t darstellen, wenn die Zahl binär kodiert wird?
2. Kodieren Sie die Zahlen 0, 1337, 65536, 5318008 und 3141592653589793 in BCD. Schreiben Sie die Zahlen mithilfe von Hexadezimalzahlliteralen als C++-Ausdruck.
3. Wie könnte man negative Zahlen in BCD kodieren?
4. Schreiben Sie eine Funktion, die eine Binärzahl in eine BCD-Zahl umwandelt, indem Sie die Dezimalstellen aus der Binärzahl einzeln extrahieren und an die richtige Stelle in der BCD-Zahl setzen.
5. Schreiben Sie eine Funktion, die eine BCD-Zahl in Dezimaldarstellung auf der Konsole ausgibt.
6. Schreiben Sie eine Funktion, die zwei uint64_t mit Zahlen in BCD-Darstellung nimmt und die Summe ebenfalls als BCD-Zahl zurückgibt. Der Übertrag der letzten Stelle darf ignoriert werden (das ist konsistent mit dem Verhalten in C++).