Zum Inhalt springen
Topos Uranos
Deutsch

Bits und Mathematikbibliothek

Zusammenfassung

Für den Prozessor ist eine ganze Zahl eine Reihe von Bits, und C++ bietet Operatoren, die Spalte für Spalte auf diese Reihe wirken: &, |, ^ und ~ sowie die Verschiebungen << und >>. Diese Lektion zeigt, wie man sie von Hand berechnet, wie man mit ihnen nach der Technik der Masken mehrere Flags in einer einzigen ganzen Zahl speichert und wie man die Verschiebungen erkennt, die der Standard nicht definiert. Danach erklärt sie, warum 2 ^ 3 den Wert 1 hat und nicht 8, und warum die Bitoperatoren Klammern verlangen. Die zweite Hälfte stellt die Mathematikbibliothek vor: die Funktionen von <cmath>, die Konstanten von <numbers>, den größten gemeinsamen Teiler und das kleinste gemeinsame Vielfache aus <numeric> und die Bitfunktionen von <bit>, mit einem Grundsatz, der in jeder Sprache gilt: Was die Bibliothek korrekt und erprobt anbietet, schreibt man nicht neu.

Lernziele

  1. Das Ergebnis von &, |, ^, ~ und der Verschiebungen auf kleinen ganzen Zahlen von Hand berechnen.
  2. Die definierten Verschiebungen (seit C++20 auch die negativer Zahlen) von denen unterscheiden, die undefiniertes Verhalten sind, und das Ergebnis der ersteren vorhersagen.
  3. Masken verwenden, um ein Bit zu prüfen, zu setzen, zu löschen und umzuschalten.
  4. Erklären, warum 2 ^ 3 den Wert 1 hat und nicht 8, und je nach Fall zwischen std::pow und einer Verschiebung wählen.
  5. Funktionen von <cmath> (std::sqrt, std::pow, std::abs, std::hypot, die trigonometrischen) und die Konstanten von <numbers>, etwa std::numbers::pi, in Formeln verwenden.

Bitoperatoren

Die Lektion Ganze Zahlen und ihre Darstellung hat gezeigt, dass ein int eine Reihe von Bits ist, 32 auf den Systemen des Kurses, und dass sein Wert die Summe der Stellenwerte der Positionen ist, an denen eine 1 steht. Bisher hat das Programm die ganze Zahl jedoch nur als Zahl behandelt: Es hat sie addiert, multipliziert und dividiert. Nun lässt dieselbe Reihe eine andere Lesart zu, als Sammlung von 32 Antworten mit Ja oder Nein, und für diese Lesart hat C++ vier Operatoren, die Bit für Bit arbeiten, ohne Übertrag zwischen den Positionen.

Die Bits werden von rechts nummeriert, beginnend bei 0: Bit kk ist das mit dem Stellenwert 2k2^k. So sind in 1212, binär 1100, die Bits 2 und 3 gesetzt und die Bits 0 und 1 nicht gesetzt.

Die Operatoren sind diese. Das bitweise UND, a & b, hat eine 1 an jeder Position, an der a und b beide eine 1 haben. Das bitweise ODER, a | b, hat eine 1 dort, wo mindestens einer der beiden eine hat. Das exklusive ODER, a ^ b, hat eine 1 dort, wo genau einer der beiden eine hat, das heißt, wo sich die Bits unterscheiden. Die bitweise Negation, ~a, hat nur einen Operanden und kehrt jedes Bit um. Die Tabellen der ersten drei sind für ein Bitpaar pp und qq die der Konjunktion, der Disjunktion und der ausschließenden Disjunktion:

pqp&qp∣qp^q11110100110101100000\begin{array}{cc|ccc} p & q & p \mathbin{\&} q & p \mid q & p \mathbin{\hat{}} q \\ \hline 1 & 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{array}

Wer den Kurs Mathematische Logik I studiert hat, erkennt hier die aussagenlogischen Junktoren wieder, mit 1 für wahr und 0 für falsch: Ein Bitoperator ist nichts anderes als ein Junktor, der auf alle Spalten zugleich angewendet wird. Daraus ergibt sich die Methode, von Hand zu rechnen: Man schreibt die beiden Zahlen binär untereinander, rechtsbündig, und wendet die Tabelle in jeder Spalte an, ohne sich um die Nachbarspalten zu kümmern.

BeispielZwölf und zehn, Spalte für Spalte

Die Zahlen 12=12 = 1100 und 10=10 = 1010 haben die Eigenschaft, dass ihre vier Spalten die vier Kombinationen zweier Bits durchlaufen; deshalb eignen sie sich, um die drei Tabellen zugleich zu sehen.

Beweis

  1. Die Daten: 1100 ist 12 und 1010 ist 10. Die Spalten enthalten von links nach rechts die Paare (1,1)(1, 1), (1,0)(1, 0), (0,1)(0, 1) und (0,0)(0, 0).

  2. Erste Spalte von 12 & 10: Beide Bits sind 1, und das UND ergibt 1.

  3. Zweite Spalte: 1 und 0. Eine einzige 0 genügt, damit das UND 0 ergibt.

  4. Dritte Spalte: 0 und 1; das UND ergibt wieder 0.

  5. Vierte Spalte: 0 und 0 ergeben 0. Die Ergebniszeile, 1000, ist 8: 12 & 10 hat den Wert 8.

  6. Das ODER setzt jede Spalte, die mindestens eine 1 enthält: 1110, das heißt, 12 | 10 hat den Wert 14.

  7. Das exklusive ODER setzt nur die Spalten, deren Bits sich unterscheiden: 0110, und 12 ^ 10 hat den Wert 6.

Das folgende Programm überprüft die Abbildung. Die Formatangabe {:04b}, die in der Lektion über die ganzen Zahlen vorgestellt wurde, schreibt einen Wert binär mit vier Ziffern, mit Nullen aufgefüllt.

C++-Programm
#include <print>​int main(){    const int a{0b1100};    const int b{0b1010};    std::println("a     = {:04b} = {}", a, a);    std::println("b     = {:04b} = {}", b, b);    std::println("a & b = {:04b} = {}", a & b, a & b);    std::println("a | b = {:04b} = {}", a | b, a | b);    std::println("a ^ b = {:04b} = {}", a ^ b, a ^ b);    std::println("~a    = {}", ~a);}
Ausgabe
a     = 1100 = 12b     = 1010 = 10a & b = 1000 = 8a | b = 1110 = 14a ^ b = 0110 = 6~a    = -13

Die letzte Zeile verdient eine Erklärung. Die Negation kehrt die 32 Bits von a um, nicht nur die vier, die geschrieben werden: Die 28 Nullen links werden zu Einsen, und ein int, das mit 1 beginnt, ist im Zweierkomplement negativ. Nun erhält man im Zweierkomplement das Negative einer Zahl, indem man ihre Bits umkehrt und 1 addiert, das heißt −x=∼x+1-x = {\sim}x + 1; folglich gilt ∼x=−x−1{\sim}x = -x - 1, und ~12 ist −13-13. Die bitweise Negation einer vorzeichenbehafteten ganzen Zahl ergibt also eine Zahl, die als Zahl selten interessiert: Sie interessiert als Muster, und deshalb bearbeitet man Bits vorzugsweise in vorzeichenlosen Typen, wie sich bei den Masken zeigen wird.

Eine Warnung zu den kleinen Typen. Vor dem Rechnen wandelt C++ jeden Operanden eines schmaleren ganzzahligen Typs, etwa std::uint8_t, in int um; das ist die Promotion, die die Lektion Arithmetik für die arithmetischen Operationen beschrieben hat, und sie gilt auch hier. Daraus folgt, dass ~flags mit flags vom Typ std::uint8_t und dem Wert 5 nicht das Byte 11111010 ist, sondern das int −6-6, dessen 32 Bits links 24 hinzugefügte Einsen enthalten; erst wenn man es wieder in einem std::uint8_t speichert, wird es auf acht Bits gekürzt und das erwartete Byte, 250, zurückgewonnen.

Die Bitoperatoren dürfen nicht mit den logischen Operatoren aus der Lektion Relationen und Logik verwechselt werden. 6 && 3 ist true: Beide Operanden sind von null verschieden, und das Ergebnis ist ein bool. 6 & 3 dagegen ist eine ganze Zahl, nämlich die, die von den Spalten gebildet wird, in denen beide eine 1 haben. Außerdem wird && mit Kurzschlussauswertung ausgewertet, und & wertet immer beide Operanden aus.