• Bisher kennengelernt:
  • Binärformat
    • Wertigkeit der Bits im Binärsystem
    • Verteilung der Bits auf mehrere Bytes für Zahlen >=255
    • Verschiedene Stellenwertsysteme (Dezimal, Hexadezimal, Binär, Oktal)
  • Boolesche Operatoren
    • AND, OR, NOT
• Jetzt:
  • Boolesche Logik (Interpretation/Bedeutung von Binärwerten)
  • Bitweise Operatoren/Operationen

• Computer speichert Informationen im Binärformat:

  1 oder 0 (= genannt Bit)

• Kombination von mehreren Ziffern bildet Binärzahl: 1001

• Zahlen \(> 255\) werden genauso dargestellt, bestehen aber aus mehreren Bytes
• Beispiel: 591 = 512 + 79

• 591 = 0000 0010 x 256 + 0100 1111

• Byte mit dem höchsten/niedrigsten Wert heißt Most/Least Significant Byte (MSB bzw. LSB)
• Reihenfolge der Bytes heißt Byte Order: Entweder von MSB zu LSB (Big Endian) oder von LSB zu MSB (Little Endian)
• Analog für Bits: Most/Least Significant Bit (MSBit bzw. LSBit)

• 🚨 Achtung: Zahlen können gleich aussehen, aber in unterschiedlichen Zahlensystemen stehen
• Beispiel: 110 (Binär) ≠ 110 (Dezimal)

• Ein Ausdruck, der zu true oder false evaluieren kann, heißt boolescher Ausdruck

Den Umgang mit boolescher Logik lernen wir jetzt kennen!

• OR: true, sobald mindestens einer der beiden Teilausdrücke wahr ist

A	B	\(A \vee B\)
0	0	0
1	0	1
0	1	1
1	1	1

\(\bf{A\vee B}\)

• AND: true, sobald beide Teilausdrücke wahr sind

A	B	\(A \wedge B\)
0	0	0
1	0	0
0	1	0
1	1	1

\(\bf{A\wedge B}\)

• NOT: Gegenteil des ursprünglichen Werts

A	\(\overline{A}\)
0	1
1	0

\(\bf{\overline{A}}\)

• Boolesche Ausdrücke können natürlich mehr als zwei Variablen beinhalten

  → Schrittweise Evaluierung von links nach rechts

• Setzt Klammern, um eindeutige Auswertungsreihenfolge zu erzwingen → Lesbarkeit

• Beispiel: (!A && B) || (A && !B)

  bool A = false; bool B = true;

• Erlauben Umformen von booleschen Ausdrücken
• Ermöglichen Vereinfachung von langen und komplexen booleschen Ausdrücken
• Gesetze sind (meist) einfach zu verstehen
• Ergeben sich intuitiv aus der Mengenlehre

• Anmerkung: Anschauliche, vertiefende Literatur mit vielen Übungsaufgaben ist
  • Thomas L. Floyd - Digital Fundamentals [1]
  • Gedacht für Elektrotechniker, auf Englisch

• Darüber hinaus gelten auch noch weitere Regeln:

Die Herleitung von Regel 11 schauen wir uns einmal als Beispiel an

Herleitung: \(A \vee \overline{A}B = A \vee B\)

• Ein zweites Beispiel: \((A \vee B)(A \vee C) = A \vee BC\)

• Abschließend gibt es noch zwei wichtige Regeln nach De-Morgan:

Die De-Morganschen Regeln gelten auch für mehr als zwei Variablen:

\(\overline{ABC} = \overline{A} \vee \overline{B} \vee \overline{C}\)

Das war jetzt genug Theorie. Zurück zu C!

• In C gibt es einen Mechanismus namens Short-Circuiting für AND und OR
• Boolesche Teilausdrücke werden von links nach rechts evaluiert
• Steht Gesamtergebnis schon nach ersten Teilausdrucks fest → keine weitere Auswertung

• Short-Circuiting bietet Geschwindigkeitsvorteile:

  Lohnenswert, unkomplizierte Ausdrücke als erstes zu evaluieren

• Beispiel:

bool a = true;
if (a || long_complicated_function()) {
    do_stuff();
} else {
    // ...
}

Und nun betrachten wir noch die bitweisen Operationen

• Exklusives Oder ist sehr nützliche und viel benutzte Operation
• Beispiel Kryptographie

  1. Passwort P in Bitmuster übersetzen und abschnittsweise auf Text T anwenden

     → Nicht lesbares Ergebnis \(T \oplus P\)

  2. Entschlüsselung: \((T\oplus P) \oplus P = T\)

• Hamming-Distanz: Bestimmung der Anzahl verschiedener Bits
• Hashing: Erzeugen einer eindeutigen Signatur (Zwischenschritt, z.B. SHA-3)

• Verschlüsselung mit fester Passphrase

#include <stdio.h>

int main() {
    int msg = 0x07; // 0000 0111
    int passwd = 0xAA; // 1010 1010
    int enc = msg ^ passwd; // 1010 1101
    printf("%#X\n", enc);
    // Umkehren zu Klartext
    enc ^= passwd; // 0000 0111
    printf("%#X\n", enc);
    return 0;
}

• Was ist das Ergebnis (GCC-Compiler)?

#include <stdio.h>
int main() {
    int i = 0x1;                // 0001
    printf("%d, %x\n", i, i);
    printf("%d, %x\n", i << 31, i << 31);
    return 0;
}

• Häufiger Anwendungsfall: Gezielte Manipulation eines oder mehrerer Bits
• Beispiele:
  • Hardwareprogrammierung
    • Einzelne Bits eines Speicherregisters stehen für verschiedene Funktionen (Flags)
    • Aktivierung über Setzen des Bits(An-Aus-Schalter)
  • Kommunikation
    • Nachricht mit fester Byte-Länge
    • Informationen sind an fester Stelle hinterlegt
• Etablierte Muster: Setzen (Set), Löschen (Clear), Flippen (Toggle) und Prüfen (Check)

• Setzen eines Bits ist unkompliziert über die OR-Operation möglich
• In Kombination mit Links-Shift: Setzen eines beliebigen Bits

#include <stdio.h>
int main() {
    int bit_pattern = 0x07;                 // 0111
    bit_pattern = bit_pattern | (1 << 3);
    printf("%#01x\n", bit_pattern);
    return 0;
}

• Löschen eines Bits geschieht mithilfe von Links-Shift, AND und NOT
• Idee
  • Links-Shift einer 1 bestimmt das Bit
  • Negierung des Ergebnisses → nur ein Bit mit 0
  • Anwenden mit AND

Beispiel: Bit 2 soll gelöscht werden

1. Links-Shift um 2 mit (1 << 2)

   Bitmuster: ...0 0100

2. Negierung: ~(1 << 2)

   Bitmuster: ...1 1011

3. AND: bit_pattern & ~(1 << 2)

• Umkehren (Flip) eines Bits: Links-Shift in Kombination mit XOR

#include <stdio.h>
int main() {
    int bit_pattern = 0x07;                 // 0111
    bit_pattern = bit_pattern ^ (1 << 1);
    printf("%#01x\n", bit_pattern);
    return 0;
}

• Überprüfen eines Bits: Links-Shift in Kombination mit AND

#include <stdio.h>
int main() {
    int bit_pattern = 0x07;                             // 0111
    printf("Is set: %#01x\n", bit_pattern & (1 << 0));
    return 0;
}

• Überprüfung darf auch als Bedingung verwendet werden

#include <stdio.h>
int main() {
    int bit_pattern = 0x07;                             // 0111
    if (bit_pattern & (1 << 0)) {
        printf("Bit 1 is set\n");
    } else {
        printf("Bit 1 is not set\n");
    }
    return 0;
}

• Szenario
  • Senden von Nachricht mit fester Länge
  • Informationen sind fester Stelle der Nachricht zu hinterlegen
• Beispiel
  • 64 Bit lange Nachricht
  • Bits 16-23 kodieren gemessene Temperatur

• Beschreibt Reihenfolge, wie Bytes im Speicher abgelegt werden
• Ausgangssituation: Eine Zahl mit mehreren Bytes → z. B. int, 4 Bytes
• Big Endian

• Little Endian

• Warum existiert diese Unterscheidung?
  • Big Endian ist intuitiver (Abbildung wie „ klassische “ Zahlen)
  • Little Endian erlaubt eine einfachere Umwandlung in Datentypen anderer Größe

• Verschiedene Prozessorhersteller legten für Produkte eine Reihenfolge fest

• Alternative Bezeichung

  • Motorola-Reihenfolge (Big Endian)
  • Intel-Reihenfolge (Little Endian)

• Intel, AMD (CPUs für Desktop/Laptop) → Little Endian

• ARM (Mobile/Mikrocontroller) → Unterstützen beides

• Keine Sorge: Compiler übernimmt automatisch die Konvertierung

  → Wir müssen (erst mal) nichts tun! 😀

• Komplexe Zustände mit Boolesche Algebra ausdrücken
• Boolesche Operationen für die praktische Umsetzung beim Programmieren
• Short-Circuiting vereinfachen Evaluation von booleschen Ausdrücken
• Bitweise Operationen erlauben Zugriff auf einzlene Bits Binärzahl
• Bitoperationen für das Bearbeiten von einzelnen Bits als unerlässliches Werkzeug
• Byte-Reihenfolge: Wichtig für verschiedene Anwendungszwecke