bitset din STL

bitset<N> e o structură din STL care reprezintă un vector fix de N biți. Fiecare bit poate fi 0 sau 1, iar operațiile se fac cuvânt cu cuvânt (64 biți deodată), ceea ce îl face extrem de rapid.

E util când vrei să manipulezi secvențe lungi de biți fără să te chinui cu operații manuale pe unsigned long long.

Ce e un bitset?

• N biți (N fixat la compilare, de ex. bitset<1000>)
• Folosește doar N/8 bytes (8 biți per byte) - foarte compact
• Operațiile &, |, ^, ~, shift - se fac la nivel de cuvânt (64 biți deodată)
• Viteza e de ~64 ori mai rapidă decât un vector de bool

Inclusion și declarare

#include <bitset>
using namespace std;

bitset<32> b;              // 32 biți, toți 0
bitset<10> b2(42);         // biții lui 42 (binar: 101010)
bitset<8> b3("10110100");  // din string (MSB la stânga)

După declarare, b conține 32 de biți setați la 0.

Reprezentarea internă

Atenție: poziția 0 e cea mai puțin semnificativă (LSB - cea din dreapta când afișezi).

bitset<8> b("10110100");
// Poziții:  76543210
// Bit 0 = 0, bit 1 = 0, bit 2 = 1, bit 3 = 0, bit 4 = 1, bit 5 = 1, bit 6 = 0, bit 7 = 1

Operații de bază

Accesare și setare

bitset<10> b;

b[0] = 1;        // seteaza bitul de pe pozitia 0
b[5] = 1;        // seteaza bitul de pe pozitia 5

cout << b[5];    // 1
cout << b[3];    // 0

b.set(2);        // seteaza bitul 2 la 1
b.reset(0);      // seteaza bitul 0 la 0
b.flip(5);       // inverseaza bitul 5 (0→1 sau 1→0)

b.set();         // toti bitii devin 1
b.reset();       // toti bitii devin 0
b.flip();        // inverseaza toti bitii

Teste

b.test(3);       // true daca bitul 3 e setat
b.any();         // true daca exista cel putin un bit setat
b.none();        // true daca toti bitii sunt 0
b.all();         // true daca toti bitii sunt 1 (C++11)
b.count();       // numarul de biti setati la 1
b.size();        // dimensiunea (N)

Operații între bitset-uri

bitset<8> a("11001100");
bitset<8> b("10101010");

bitset<8> c = a & b;   // AND:  10001000
bitset<8> d = a | b;   // OR:   11101110
bitset<8> e = a ^ b;   // XOR:  01100110
bitset<8> f = ~a;      // NOT:  00110011

// Shift
bitset<8> g = a << 2;  // 00110000
bitset<8> h = a >> 3;  // 00011001

Ambii operanzi trebuie să fie aceeași dimensiune N.

Afișare

bitset<8> b("10110100");

cout << b;                  // 10110100 (MSB primul)
cout << b.to_string();      // la fel
cout << b.to_ulong();       // 180 (valoarea decimală)
cout << b.to_ullong();      // la fel, dar unsigned long long (C++11)

to_ulong aruncă excepție dacă N > 64.

Exemplu: ciurul lui Eratostene cu bitset

Ciurul clasic cu bool[] ocupă 10 MB pentru N = 10^7. Cu bitset, 1.25 MB - de 8 ori mai puțin.

#include <fstream>
#include <bitset>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

const int N = 10000001;
bitset<N> ciur;

int main()
{
    int n;
    fin >> n;

    ciur.set();          // toti 1 (candidate la prim)
    ciur[0] = ciur[1] = 0;

    for (int i = 2; (long long)i * i <= n; i++)
        if (ciur[i])
            for (int j = i * i; j <= n; j += i)
                ciur[j] = 0;

    // Afisam primele pana la n
    for (int i = 2; i <= n; i++)
        if (ciur[i])
            fout << i << " ";

    return 0;
}

date.in:

30

date.out:

2 3 5 7 11 13 17 19 23 29

Ciurul cu bitset e și mai rapid datorită accesului la biți cuvânt cu cuvânt.

Avantaje vs bool[] sau vector

bitset e cel mai rapid pentru operații pe secvențe mari de biți, dar dimensiunea trebuie știută la compilare.

Problema clasică: subset sum

Ai n numere și vrei să știi ce sume se pot forma alegând o submulțime.

Soluția naivă

Complexitate O(n * S), unde S = suma totală posibilă.

Soluția cu bitset

bitset<100001> dp;
dp[0] = 1; // putem face suma 0 (multimea vida)

for (int i = 0; i < n; i++)
    dp |= (dp << v[i]);

// dp[s] = 1 ⟺ exista submultime cu suma s

Fiecare |= (dp << v[i]) adaugă fiecare sumă posibilă + v[i] la mulțimea sumelor posibile. Totul în O(n * S / 64) - de 64 ori mai rapid!

Pas cu pas: subset sum

v = [1, 3, 4]. Ce sume se pot forma?

Inițial:  dp = 000000001 (doar suma 0)

Iterație 1 (v[0] = 1):
  dp << 1 = 000000010
  dp |= ... → dp = 000000011 (sume: 0, 1)

Iterație 2 (v[0] = 3):
  dp << 3 = 000011000
  dp |= ... → dp = 000011011 (sume: 0, 1, 3, 4)

Iterație 3 (v[0] = 4):
  dp << 4 = 110110000
  dp |= ... → dp = 110111011 (sume: 0, 1, 3, 4, 5, 7, 8)

Toate sumele posibile în O(n * S / 64).

Alte aplicații

1. Vectori de frecvență compacți

Pentru valori 0/1 pe multe poziții.

2. Căutare în reprezentări de seturi

Verificări O(1) pentru apartenență, reuniune, intersecție.

3. Probleme cu submulțimi (până la 64 sau 100k)

Cu bitset, poți itera peste submulțimi mari eficient.

4. DP cu stări booleene

Accelerează DP-uri prin reprezentarea stărilor cu bitset.

5. Algoritm gramatici / recunoaștere pattern

Pentru testarea intersecțiilor între mulțimi de stări.

Limite

1. Dimensiune la compilare

int n;
cin >> n;
bitset<n> b; // GRESIT - n nu e constanta

Alegi N la compilare, destul de mare pentru toate testele. Dacă ai nevoie de dimensiune dinamică, folosește vector<uint64_t> manual.

2. Acces iterativ

bitset nu are iteratori STL (nu poți for (auto x : b)). Trebuie să parcurgi cu for (int i = 0; i < b.size(); i++).

Există _Find_first() și _Find_next(i) (GCC extension) pentru a itera doar prin biții setați rapid:

for (int i = b._Find_first(); i < b.size(); i = b._Find_next(i)) {
    // b[i] == 1
}

Cod complet: numărul de biți setați

#include <fstream>
#include <bitset>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int main()
{
    bitset<64> b;
    long long x;
    fin >> x;
    b = x;

    fout << b << "\n";          // reprezentare binara
    fout << b.count() << "\n";  // cati biti de 1
    fout << b.any() << "\n";    // exista vreun 1?
    fout << b.flip() << "\n";   // inversam toti bitii

    return 0;
}

date.in:

42

date.out:

0000000000000000000000000000000000000000000000000000000000101010
3
1
1111111111111111111111111111111111111111111111111111111111010101

Greșeli frecvente

1. Dimensiunea nu e constantă

int n;
cin >> n;
bitset<n> b;        // GRESIT

const int N = 100000;
bitset<N> b;        // CORECT

Bitset-ul e template cu parametru int constant.

2. Confuzie MSB/LSB

bitset<4> b("1010");
cout << b[0] << b[1] << b[2] << b[3]; // 0 1 0 1

Stringul "1010" are MSB primul, deci b[0] = ultimul caracter (0), b[3] = primul (1).

3. Overflow la to_ulong()

bitset<128> b;
b.set();
cout << b.to_ulong(); // arunca exceptie - nu incape in unsigned long

Folosește to_ullong() pentru unsigned long long (64 biți), sau afișează direct.

4. Operații între dimensiuni diferite

bitset<8> a;
bitset<10> b;
auto c = a & b; // EROARE DE COMPILARE - dimensiuni diferite

Toate operațiile binare cer aceeași dimensiune.

5. Uitarea set() inițial

bitset<100> b;          // toti sunt 0
// b.set();             // uitat! ciurul nu merge daca pornim de la 0

La ciur vrei toți 1 la început. b.set() face asta.

Viteză vs cod echivalent

Pentru a calcula un AND bitwise între 2 mulțimi de 10^6 biți:

Bitset e de ~60 de ori mai rapid pentru operații pe tot vectorul.

Ce să reții

• bitset<N> = vector fix de N biți, N constant la compilare.
• Operațiile &, |, ^, ~, shift se fac cuvânt cu cuvânt - foarte rapid.
• Metode: set, reset, flip, count, any, all, none, test.
• Memorie: N/8 bytes (de 8x mai compact decât bool[]).
• Aplicații: ciur, subset sum, vectori de frecvență, DP cu stări booleene.
• Poziția 0 = LSB (bitul cel mai puțin semnificativ, afișat cel din dreapta).
• Nu are iteratori standard; folosește for cu indici sau _Find_first/_Find_next (GCC).