Bitmask (operații pe biți)

Un bitmask este un număr întreg folosit pentru a reprezenta o mulțime de biți - fiecare bit e un “steguleț” pornit (1) sau oprit (0).

Operațiile pe biți sunt foarte rapide (O(1)) și se folosesc pentru:

• Reprezentarea submulțimilor
• Operații rapide cu mulțimi (reuniune, intersecție, diferență)
• Verificare paritate
• Optimizări la probleme cu maxim 30-60 de elemente

Operatorii pe biți

Cum funcționează

Numerele sunt stocate în binar. De exemplu:

5  = 0101
3  = 0011

AND (&) - 1 doar unde ambele sunt 1

5 = 0101
3 = 0011
    ----
    0001  =  1

OR (|) - 1 oriunde există un 1

5 = 0101
3 = 0011
    ----
    0111  =  7

XOR (^) - 1 doar unde biții sunt diferiți

5 = 0101
3 = 0011
    ----
    0110  =  6

Shift (<<, >>)

1 << 3  =  1000 (binar) = 8    (1 mutat cu 3 poziții la stânga)
8 >> 2  =  0010 (binar) = 2    (8 mutat cu 2 poziții la dreapta)

1 << k = 2^k. x >> 1 = x / 2 (pentru numere pozitive).

Reprezentarea unei mulțimi cu bitmask

Avem n elemente numerotate de la 0 la n-1. Putem reprezenta orice submulțime cu un număr întreg unde bitul i e 1 dacă elementul i e în mulțime.

n = 4 elemente: {0, 1, 2, 3}

Mulțime {0, 2}:
   bit:  3 2 1 0
   val:  0 1 0 1 = 5

Mulțime {1, 3}:
   bit:  3 2 1 0
   val:  1 0 1 0 = 10

Mulțime {} (vidă):  0
Mulțime {0,1,2,3}:  1111 = 15

Pentru n elemente, avem 2^n submulțimi posibile (numere de la 0 la 2^n - 1).

Operații pe submulțimi

Adăugare element i

mask = mask | (1 << i);   // activează bitul i

Ștergere element i

mask = mask & ~(1 << i);  // dezactivează bitul i

Verificare dacă elementul i e în mulțime

if (mask & (1 << i))     // bitul i este 1
    cout << "i este in multime";

Toggle (inversare) element i

mask = mask ^ (1 << i);   // inversează bitul i

Numărarea elementelor (biții 1)

int cntBits(int mask) {
    int cnt = 0;
    while (mask > 0) {
        cnt = cnt + (mask & 1);
        mask = mask >> 1;
    }
    return cnt;
}

// Sau cu built-in:
int cnt = __builtin_popcount(mask);  // O(1)

Parcurgerea tuturor submulțimilor

int n = 4; // avem 4 elemente
int totalMasks = 1 << n; // 2^4 = 16

for (int mask = 0; mask < totalMasks; mask++) {
    // mask reprezintă o submulțime
    for (int i = 0; i < n; i++) {
        if (mask & (1 << i))
            cout << i << " ";
    }
    cout << endl;
}

Exemplu pentru n=3

mask = 0 (000): {}
mask = 1 (001): 0
mask = 2 (010): 1
mask = 3 (011): 0 1
mask = 4 (100): 2
mask = 5 (101): 0 2
mask = 6 (110): 1 2
mask = 7 (111): 0 1 2

Problema 1: suma submulțimilor

Vector cu n elemente (n <= 20). Pentru fiecare submulțime, calculăm suma. Afișăm suma maximă:

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

int v[21];
int n;

int main()
{
    fin >> n;
    for (int i = 0; i < n; i++)
        fin >> v[i];

    int maxSuma = 0;

    for (int mask = 0; mask < (1 << n); mask++) {
        int suma = 0;
        for (int i = 0; i < n; i++)
            if (mask & (1 << i))
                suma = suma + v[i];
        if (suma > maxSuma)
            maxSuma = suma;
    }

    fout << maxSuma;

    return 0;
}

Complexitate: O(2^n * n). Funcționează pentru n <= 20 (sub un milion de măști).

Problema 2: paritate (XOR magic)

Proprietatea cheie a lui XOR:

• x ^ x = 0
• x ^ 0 = x
• a ^ b ^ a = b (ordinea nu contează)

Elementul unic (cu toate celelalte apar de 2 ori)

Vector cu n elemente, fiecare apare de 2 ori exceptând unul. Găsim elementul unic în O(n) cu O(1) memorie:

int rez = 0;
for (int i = 0; i < n; i++)
    rez = rez ^ v[i];

fout << rez; // elementul unic

De ce funcționează?

Toate elementele care apar de 2 ori se anulează (x ^ x = 0). Rămâne doar elementul unic.

Exemplu: [2, 3, 5, 3, 2]
2 ^ 3 ^ 5 ^ 3 ^ 2 = (2^2) ^ (3^3) ^ 5 = 0 ^ 0 ^ 5 = 5

Trucuri utile

Verificare dacă n este putere de 2

bool estePutereDe2(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

De ce? O putere de 2 are exact un bit setat: 1000.... Scăzând 1, toți biții se inversează: 0111.... AND-ul dă 0.

Cel mai mic bit setat

int lsb = n & (-n);  // izolează cel mai mic bit 1

Verificare paritate (par/impar)

if (n & 1)  // bitul 0 e setat - impar
    cout << "impar";
else
    cout << "par";

Înmulțire/împărțire rapidă cu puteri de 2

x << 1   // x * 2
x << 3   // x * 8
x >> 1   // x / 2
x >> 2   // x / 4

Problema 3: submulțimi cu suma egală cu S

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

int v[21];
int n, s;

int main()
{
    fin >> n >> s;
    for (int i = 0; i < n; i++)
        fin >> v[i];

    int cnt = 0;

    for (int mask = 0; mask < (1 << n); mask++) {
        int suma = 0;
        for (int i = 0; i < n; i++)
            if (mask & (1 << i))
                suma = suma + v[i];
        if (suma == s)
            cnt++;
    }

    fout << cnt;

    return 0;
}

Operații pe mulțimi cu bitmask

Limitări

Cu int (32 biți), putem reprezenta submulțimi de până la 30 de elemente (folosim doar primii 30 de biți ca să evităm bitul de semn).

Cu long long (64 biți), până la 62 de elemente.

Pentru n > 62, avem nevoie de bitset (STL) sau alt mecanism.

Greșeli frecvente

1. Priorități gresite

if (mask & 1 << i)  // GRESIT - & are prioritate mai mică decât <<
if (mask & (1 << i))  // CORECT

Mereu folosește paranteze când combini operatori pe biți cu alte operații.

2. 1 << 31 cu int

int mask = 1 << 31;  // NEDEFINIT pentru int cu semn
long long mask = 1LL << 31;  // CORECT

Pentru biți peste 30, folosește long long și 1LL (literal long long).

3. Confuzia între & și &&

if (mask & (1 << i))   // operație pe biți - OK
if (a && b)            // operație logică (AND pe bool)

& este operație pe biți, && este operație logică.

Ce să reții

• Bitmask = număr întreg folosit ca mulțime de biți.
• Operatori: & (AND), | (OR), ^ (XOR), ~ (NOT), << >> (shift).
• Adăugare: mask | (1 << i). Ștergere: mask & ~(1 << i). Verificare: mask & (1 << i).
• 1 << n submulțimi pentru n elemente - iterăm prin toate.
• XOR auto-anulare: x ^ x = 0 - util pentru elementul unic.
• Folosim paranteze la operații pe biți combinate.
• Complexitate O(2^n) - doar pentru n <= 20-25.