Lecție-punte: măști de biți pentru începători

De ce contează?

Imaginează-ți un breloc cu 5 chei numerotate. În loc să spui „am cheile 0, 2 și 3", poți aprinde 5 beculețe: 01101. Un singur șir de becuri descrie complet ce chei ai. Masca de biți face exact asta — descrie o întreagă mulțime cu un singur număr.

De ce măști de biți

Ai învățat operațiile pe biți. Acum le folosim la ceva concret: să reprezentăm o mulțime de elemente într-un singur întreg. Bitul k aprins (1) înseamnă „elementul k e în mulțime". Avantajul: o mulțime întreagă încape într-un int, iar operațiile cu mulțimi devin operații pe biți, O(1).

Observația-cheie

Cu un int (32 de biți) reprezinți orice submulțime a unei mulțimi cu până la 32 de elemente. Cu long long, până la 64. De aici și legătura cu numărul de submulțimi: 2ⁿ.

Cele trei operații fundamentale

Pentru un element k, cheia e 1 << k — un număr cu doar bitul k aprins:

Operație	Cod	Ce face
Testează bitul k	`m & (1 << k)`	nenul ⟺ k e prezent
Setează (adaugă) k	`m \| (1 << k)`	aprinde bitul k
Șterge (scoate) k	`m & ~(1 << k)`	stinge bitul k
Comută k	`m ^ (1 << k)`	inversează bitul k

Pe un exemplu: mulțimea

Masca pentru are biții 0, 2, 3 aprinși → 1101 = 13.

#include <iostream>
using namespace std;

int main() {
    int m = 0;                  // multime goala
    m = m | (1 << 0);           // adauga 0  -> 0001
    m = m | (1 << 2);           // adauga 2  -> 0101
    m = m | (1 << 3);           // adauga 3  -> 1101 = 13

    int k = 2;
    if (m & (1 << k)) {         // e 2 in multime?
        cout << "2 este prezent\n";
    }

    m = m & ~(1 << 2);          // scoate 2  -> 1001 = 9
    cout << m << "\n";          // 9
    return 0;
}

Observația-cheie

1 << k e „cheia" elementului k. OR-ul aprinde un bit fără să-i atingă pe ceilalți, AND-ul cu masca izolează un bit, iar AND-ul cu ~(1 << k) stinge exact un bit. Memorează aceste trei tipare — le vei refolosi la backtracking și la programarea dinamică pe stări.

Când alegi măști de biți

Pentru: mulțimi mici (≤ 32–64 elemente), unde testarea/adăugarea trebuie să fie O(1) sau unde parcurgi toate submulțimile (de la 0 la 2ⁿ−1).
Împotrivă: mulțimi mari (mii de elemente) — un int/long long nu ajunge. Acolo folosești un vector caracteristic sau set.

Complexitate

Operație	Timp
test / set / clear / toggle	O(1)
parcurgerea tuturor submulțimilor	O(2ⁿ)

O singură operație pe biți e instantanee. Parcurgerea tuturor celor 2ⁿ submulțimi crește exponențial — fezabilă doar pentru n mic (de obicei n ≤ 20).

Greșeli frecvente

Capcane reale la măștile de biți:

Prioritatea operatorilor: m & 1 << k se evaluează ciudat din cauza priorității. Scrie m & (1 << k) cu paranteze.
Shift care depășește: 1 << 31 pe int cu semn e overflow; pentru biți înalți sau măști pe 64 de biți folosește 1LL << k.
Test greșit: m & (1 << k) == 1 e fals pentru k > 0 (bitul izolat nu e 1, ci 2ᵏ). Compară cu 0: (m & (1 << k)) != 0.
Confuzi setarea cu comutarea: OR adaugă (idempotent), XOR comută (adaugă/scoate alternativ). Pentru „adaugă sigur" folosește OR.

De reținut

O mască de biți = o mulțime într-un întreg; bitul k = „elementul k e prezent".
Test m & (1<<k), adaugă m | (1<<k), șterge m & ~(1<<k) — toate O(1).
Folosește pentru mulțimi mici (≤ 64) și parcurgerea submulțimilor (2ⁿ, n mic); paranteze obligatorii.