C/C++-Algorithmen

Bitmanipulation in C und C++

In dieser Lektion setzt, löschst, kippst und prüfst du einzelne Bits einer ganzen Zahl, um mehrere Ein/Aus-Zustände zu speichern.

Einführung

Jedes Bit einer ganzen Zahl kann einen Wahr- oder Falsch-Wert speichern. So kann eine einzige vorzeichenlose Zahl mehrere unabhängige Ein/Aus-Optionen enthalten, sogenannte Flags. Diese Technik mit Bitmasken (bit mask) ist in der Systemprogrammierung und bei eingebetteten Systemen sehr verbreitet.

Wichtige Punkte

Teste mit leeren Eingaben, einem einzigen Element, doppelten Werten und bereits sortierten Daten.
Zuerst richtig machen, dann optimieren.
Bevorzuge in echtem Code die fertigen Funktionen der Standardbibliothek.

Codebeispiele in C und C++

Code ausführen →

main.c

#include <stdio.h>

int main(void) {
    unsigned flags = 0;
    flags |= 1u << 1;
    flags |= 1u << 3;
    flags ^= 1u << 1;
    printf("flags=%u bit3=%u\n", flags, (flags >> 3) & 1u);
}

Ergebnis der Ausführung

flags=8 bit3=1

C++

Code ausführen →

main.cpp

#include <bitset>
#include <iostream>

int main() {
    std::bitset<4> flags;
    flags.set(1);
    flags.set(3);
    flags.flip(1);
    std::cout << "flags=" << flags
              << " bit3=" << flags.test(3) << '\n';
}

Ergebnis der Ausführung

flags=1000 bit3=1

C und C++ im Vergleich

Der Ausdruck 1u << n erzeugt eine Zahl, in der nur Bit n gleich 1 ist. Der Operator |= setzt ein Bit, ^= kippt es, und (flags >> 3) & 1u prüft Bit 3. Nachdem Bit 1 und Bit 3 gesetzt und Bit 1 wieder gekippt wurde, ist nur noch Bit 3 gesetzt, deshalb ist flags gleich 8. Verwende vorzeichenlose Typen (unsigned), damit Bitverschiebungen vorhersehbare Ergebnisse liefern. In C++ bietet std::bitset verständliche Methoden wie set() und flip() und gibt den Wert binär aus.

Schleifen, Zeiger, Längen und Zwischenpuffer werden ausdrücklich ausgeschrieben.

C++

Iteratoren und Standardalgorithmen trennen die Verarbeitung von der Art, wie die Daten gespeichert sind.

Übungen zur Vertiefung

Führe beide Versionen aus und ändere dann den Code, um zu beobachten, welche Sicherheit jede Sprache bietet.

Spiele jeden Vergleich auf Papier durch.
Teste mit doppelten Werten und mit sehr großen und sehr kleinen Werten.
Miss die Laufzeit deines Codes und vergleiche sie mit der Standardbibliothek.

Mit einer Challenge üben

Nutze den Inhalt dieser Lektion, um ein echtes Problem zu lösen. Jede Challenge läuft im Browser, mit sofortigen Tests und einem KI-Review.

Alle Challenges