bitset — tablou compact de biți

Ce este un bitset și de ce îl folosești

Un bitset este un tablou de biți (valori 0 sau 1) cu dimensiune fixată la compilare: scrii bitset<N>, iar N nu se mai poate schimba la rulare. Pare o limitare, dar tocmai asta îl face rapid.

Sunt două motive pentru care îl alegi:

• Compactare. Un bool ocupă de obicei 1 octet (8 biți) ca să țină o singură valoare 0/1. Un bitset împachetează 64 de biți într-un singur cuvânt de memorie, deci e de aproximativ 8x mai compact decât un șir de bool și mult mai compact decât folosirea de întregi.
• Operații în masă. Când faci a & b, procesorul prelucrează 64 de biți dintr-o singură instrucțiune. Pentru N biți, costul devine de ordinul O(N/64) în loc de O(N) — de aici accelerarea de ~64x folosită la ciur sau la DP pe seturi de biți.

Exemplu pas cu pas

Pornim cu un bitset<8> plin de zerouri și îl modificăm:

• b.set(2) aprinde bitul 2 → 00000100
• b.set(5) aprinde bitul 5 → 00100100
• b.set(0) aprinde bitul 0 → 00100101
• b.count() numără biții pe 1 → 3
• b.reset(5) stinge bitul 5 → 00000101
• b.flip() inversează toți biții → 11111010

Atenție la ordine: bitul 0 este cel mai din dreapta (cel mai puțin semnificativ). Când scriem un bitset, primul bit (index 0) apare ultimul.

Implementare C++

#include <iostream>
#include <bitset>
using namespace std;

int main() {
    bitset<8> b;                 // 00000000 (toti biti pe 0)

    b.set(2);                    // 00000100
    b.set(5);                    // 00100100
    b[0] = 1;                    // 00100101 (indexare cu [])

    cout << b << "\n";           // afiseaza 00100101
    cout << b.count() << "\n";   // 3 (biti pe 1)
    cout << b.size() << "\n";    // 8 (dimensiunea N)
    cout << b.test(2) << "\n";   // 1 (bitul 2 e setat)
    cout << b.any() << "\n";     // 1 (exista cel putin un bit pe 1)
    cout << b.none() << "\n";    // 0 (nu sunt toti pe 0)

    b.reset(5);                  // 00000101 (stinge bitul 5)
    b.flip();                    // 11111010 (inverseaza toti bitii)
    cout << b << "\n";           // 11111010

    // operatii pe doua bitset-uri de aceeasi dimensiune
    bitset<8> x(string("11001010"));   // construit dintr-un sir
    bitset<8> y(string("10101100"));
    cout << (x & y) << "\n";     // 10001000 (SI pe biti)
    cout << (x | y) << "\n";     // 11101110 (SAU pe biti)
    cout << (x ^ y) << "\n";     // 01100110 (XOR pe biti)
    cout << (~x)    << "\n";     // 00110101 (negare)
    cout << (x << 2) << "\n";    // 00101000 (deplasare stanga cu 2)
    cout << (x >> 1) << "\n";    // 01100101 (deplasare dreapta cu 1)
    return 0;
}

Complexitate

Fie N numărul de biți. Operațiile în masă tratează câte 64 de biți deodată.

Dacă vizualizezi un bitset, citește-l de la dreapta la stânga — indicele 0 e în capătul din dreapta:

Recapitulare

• bitset<N> are dimensiune fixă la compilare; e de ~8x mai compact ca bool[].
• Operațiile în masă (&, |, ^, ~, <<, >>) lucrează pe 64 de biți deodată, deci O(N/64) — folosite la ciur și DP pe seturi de biți.
• Controlul individual: set/reset/flip/test/count/any/none și indexarea cu [], unde bitul 0 e cel mai puțin semnificativ.