C/C++-Algorithmen

Bitoperationen

Bitmasken speichern mehrere unabhängige boolesche Optionen kompakt in einer Ganzzahl.

Was ist Bitoperationen?

Bitmasken speichern mehrere unabhängige boolesche Optionen kompakt in einer Ganzzahl.

Setze, lösche, invertiere und prüfe Flags.

Wichtige Punkte

Teste leere, einzelne, doppelte und sortierte Eingaben.
Trenne Korrektheit von Optimierung.
Nutze in Produktivcode bevorzugt die 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);
}

Erwartete Ausgabe

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';
}

Erwartete Ausgabe

flags=1000 bit3=1

Vergleich zwischen C und C++

Unsigned-Typen machen Shifts vorhersehbar. C arbeitet mit Masken; C++ bitset bietet benannte Operationen und lesbare Binärausgabe.

Schleifen, Pointer, Längen und Puffer sind explizit.

C++

Iteratoren und Algorithmen trennen Operation und Speicherung.

Übungsaufgaben

Führe beide Versionen aus und untersuche die unterschiedlichen Garantien.

Verfolge jeden Vergleich manuell.
Teste Duplikate und Extremwerte.
Vergleiche die Laufzeit mit der Standardbibliothek.