Institut für Informatik

Michael Wand
Christian Ali Mehmeti-Göpel

Wintersemester 2020/21 • DIGITAL

• Zum einen schauen wir uns an, wie Operationen direkt auf Bit-Ebene in C++ bewerkstelligt werden können. Als konkrete Anwendung schauen wir uns an, wie beliebig große Zahlen im Dezimalsystem als Binärcode so codiert werden können, dass eine Ausgabe schnell möglich ist.
• Reelle Zahlen können auf dem Rechner durch Fließkommazahlen approximiert werden. Das Problem dabei ist, dass die Art der Darstellung im Rechner zu einigen Eigenheiten beim Rechnen führt. Welche genau das sind, und wieso sie etwa einige dieser Bugs verhindern könnten, lernen wir in der zweiten Aufgabe.

Aufgabe Operationen auf der Binärdarstellung

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

Aufgabe Konsequenzen beschränkter Präzision

Aufgabenteil A:
Aus Python kennen Sie noch den Datentyp int für Ganzzahlen. ints in Python können beliebig viele Stellen haben, was das Rechnen in Python sehr intuitiv macht. Maschinennahe Sprachen wie C++ verwenden stattdessen eine beschränkte Repräsentation für numerische Datentypen. Das bewirkt, dass man den Speicheraufwand von numerischen Daten sehr genau vorhersagen kann, hat aber auch zur Folge, dass sich die meisten Zahlen nicht unmittelbar darstellen lassen.

• Mit dem Befehl sizeof(T) kann man herausfinden, wie viele Bytes ein Wert vom Datentyp T belegt.
  • Wieviele Bytes im Speicher werden durch 128 Zahlen vom Typ uint64_t belegt?
  • Wieviele Bits benötigt man (theoretisch), um einen Wert vom Typ bool zu speichern? Wieviele Bits sind es laut sizeof(bool)?
• In C++ kann man static_cast<T>(x) verwenden, um den Wert x explizit in einen Wert vom Typ T umzuwandeln. Das funktioniert natürlich nicht immer verlustfrei. Finden Sie für die folgenden Konversionen jeweils eine Zahl, die im Eingabedatentyp problemlos repräsentiert werden kann, aber nicht im Zieldatentyp. Testen Sie mithilfe Ihres Compilers für Ihre gewählte Zahl, welches Ergebnis der Cast liefert. Falls keine solche Zahl existiert, begründen sie kurz, warum alle Zahlen verlustfrei übernommen werden können. Geben Sie außerdem Ihre Compilerversion an.
  • Konversion von uint32_t zu uint64_t
  • Konversion von int32_t zu uint64_t
  • Konversion von int32_t zu uint32_t
  • Konversion von int64_t zu uint32_t
  • Konversion von uint32_t zu int32_t
  • Konversion von int32_t zu double
  • Konversion von double zu int32_t
  • Konversion von float zu int32_t

Aufgabenteil B:
Betrachten Sie die folgende Schleife, die einen einfachen Countdown implementiert:

for (uint32_t i = 10; i >= 0; --i) {
    std::cout << i << std::endl;
}

Kompilieren Sie den Code. Verifizieren Sie, dass die Schleife endlos läuft. Erklären Sie, wieso das passiert. Schreiben Sie den Code so um, dass er korrekt funktioniert. Versuchen Sie, eine möglichst nachvollziehbare Lösung zu finden.

Aufgabenteil C:
Auch Fließkommazahlen sind durch beschränkten Speicherplatz eingeschränkt, aber auf eine andere Weise. Die folgende Aufgabe basiert auf der Annahme, dass ihr Compiler Fließkommazahlen nach dem Standard IEEE-754 implementiert, aber alle größeren Compiler tun das eigentlich. Wir wollen jetzt zeigen, dass Fließkommazahlen, die nah an der 0 liegen, mehr Abstufungen zulassen als solche, die weiter von der 0 entfernt sind. Wir können dazu alle verschiedenen Binärdarstellungen von floats aufzählen und die Differenz zur jeweils nächsten Fließkommazahl betrachen:

int main() {
    // ignore this line
    static_assert(sizeof(uint32_t) == sizeof(float), "");
    
    uint32_t lower = 0x00000000u;
    uint32_t upper = 0xFFFFFFFFu;
    // enumerate all 2**32-1 possible states
    for(uint32_t i = lower; i < upper; ++i) {
        // reinterpret storage location as float
        float i_as_float = *reinterpret_cast<float*>(&i);
        uint32_t i_plus_one = i + 1;
        float i_plus_one_as_float = *reinterpret_cast<float*>(&i_plus_one);
        double difference = i_plus_one_as_float - i_as_float;
        std::cout << std::setprecision(20) << "Decimal: " << i << " | Float: " << i_as_float << " | Difference to next float: " << difference << std::endl;
    }
}

1. Kompilieren Sie den Code.
2. Recherchieren Sie oder finden Sie experimentell heraus, welche Bit-Darstellung die 0 kodiert. Ist die Darstellung eindeutig, d.h. kann der Wert 0 auch durch eine andere Bit-Darstellung kodiert werden?
3. Finden Sie jeweils zwei Werte für lower und upper, bei denen man das oben beschriebene Problem gut sehen kann, d.h. für ein Paar sollen die Abstände zwischen mehreren aufeinanderfolgenden Zahlen möglichst groß und für ein anderes möglichst klein sein. Erklären Sie kurz, wie sie die Werte gefunden haben.
4. Fließkommazahlen können außerdem die Werte \(\pm\) inf (Unendlich) und NaN (keine darstellbare Zahl) kodieren. Geben Sie für jeden der drei Werte jeweils eine mögliche Bit-Darstellung und eine Rechnung, die diesen Wert als Ergebnis liefert, an.
5. BONUS: Nach IEEE-754 kodiert ein Teil der 32 Bits in einem float den Exponenten der Fließkommazahl. Finden Sie ein uint32_t x, sodass die floats, die durch x und (x + 1) kodiert werden, unterschiedliche Exponenten haben.