Operații pe biți în C++ – Generare de submulțimi și nu numai!

Operațiile pe biți sunt folosite foarte des pentru optimizarea programelor, în special atunci când este nevoie în mod direct de lucrul cu numere în baza $2$ sau cu puteri ale lui $2$ Operatorii pe biți din C++ sunt implementați în limbaje de asamblare, ceea ce îi face foarte rapizi. În acest articol voi prezenta cum funcționează aceștia și câteva aplicații utile ce folosesc operații pe biți.

Operatorii pe biți, după cum le zice și numele, lucrează la nivelul biților numerelor întregi (signed și unsigned). Poate părea ciudat, mai ales având în vedere că cea mai mică zonă de memorie ce are o adresă este byte-ul, care este compus de fapt din 8 biți. În primul rând, pentru a înțelege cum funcționează acești operatori, trebuie înțeles modul în care sunt reprezentați întregii în C++.

Reprezentarea binară a întregilor în C++

Vom începe cu întregii cu semn. Pentru simplitate, mă voi referi direct la tipul int. O variabilă de tip int e reprezentată pe 4 bytes, adică pe 32 de biți. Dintre aceștia, primul bit (cel mai din stânga) se numește bit de semn, deoarece acesta indică semnul numărului. Dacă numărul e pozitiv, valoarea bitului de semn este $0$ iar dacă e negativ $1$ În cazul numerelor pozitive, pe ceilalți 31 de biți, de la stânga la dreapta, se află reprezentarea în baza $2$ a numărului.

În cazul numerelor negative, pe cei 32 de biți (cu tot cu cel de semn), este reprezentat numărul într-un cod complementar față de modulul său, numit Two's complement. Mai există două moduri importante de reprezentare a întregilor negativi, Signed magnitude și One's complement. Ele sunt mai ușor de înțeles pentru oameni, însă calculatoarele lucrează mai încet cu ele. În plus, un dezavantaj major al lor este faptul că $-0$ și $+0$ sunt reprezentați diferit.

În codificarea folosită de C++, pentru numărul negativ $-x$ se va reține reprezentarea lui $2^{32} - x$ Această reprezentare garantează că bitul de semn va fi $1$ doar pentru numerele strict negative. Iată cum arată două numere reținute pe un tip întreg de 8 biți:

01011000 = 2^6 + 2^4 + 2^3 = 88
11011000 = -(2^8 - (2^7 + 2^6 + 2^4 + 2^3)) = -(256 - 216) = -40

Pentru celelalte tipuri întregi cu semn treaba stă fix la fel, doar că 32-ul luat ca exemplu va fi înlocuit cu numărul de biți folosit de tipul respectiv. De exemplu, dacă ne referim la un tip cu semn pe trei biți (care de fapt nu există, întrucât $3$ nu este o putere a lui $2$ numerele ce pot fi reprezentate pe el sunt:

000 =  0
001 =  1
010 =  2
011 =  3
100 = -4
101 = -3
110 = -2
111 = -1

După cum se poate vedea, se numără de la $0$ la numărul pozitiv maxim $\htmlClass{katexified}{(} 3$ iar după ce bitul de semn devine $1$ se numără de la cel mai mic număr negativ $\htmlClass{katexified}{(} -4$ la cel mai mare $\htmlClass{katexified}{(} -1$

La întregii fără semn e aproape la fel, doar că nu există bit de semn, deoarece se știe că toate valorile ce se pot reține într-un tip întreg fără semn sunt pozitive. Așadar, pe cei 32 de biți ai unui unsigned int, se reține reprezentarea în baza $2$ a numărului stocat în variabila respectivă.

Operatorii pe biți în C++

Acum putem analiza cum funcționează fiecare operator pe biți din C++. În funcție de numărul de operanzi, operatorii pot fi unari sau binari. În plus, există și operatori compuși de atribuire pe biți.

Operatorul de negație pe biți (~)

Operatorul de negație pe biți (~) este singurul operator unar pe biți. Acesta schimbă fiecare bit al operandului în opusul său. Deci, biții $0$ vor deveni $1$ iar biții $1$ vor deveni $0$

 x = 00010110
~x = 11101001

Operatorii logici pe biți (|, &, ^)

Acești operatori efectuează operații logice asupra biților de pe aceeași poziție din cele două numere. Pentru simplitate, voi nota cei doi operanzi cu $a$ și $b$ rezultatul cu $c$ iar cu $x_i$ bitul de pe poziția $i$ din $x$

După aplicarea disjuncției pe biți (|), $c_i$ va fi $1$ dacă măcar unul dintre $a_i$ și $b_i$ este $1$ iar $0$ în caz contrar.

01110010 |
11000110
--------
11110110

Dacă operația efectuată este conjuncția pe biți (&), $c_i$ va fi $1$ dacă $a_i$ și $b_i$ sunt ambele $1$ iar $0$ dacă nu.

01010100 &
11001110
--------
01000100

În cazul disjuncției exclusive, numită și XOR (^), $c_i$ ia valoarea $1$ dacă $a_i$ e diferit de $b_i$ sau $0$ dacă $a_i$ și $b_i$ sunt egale.

10110111 ^
00011010
--------
10101101

Pentru a rezuma, iată un tabel cu rezultatele operatorilor logici binari pe biți:

Operatorii de deplasare a biților (<<, >>)

Vom nota operandul din stânga cu $a$ iar pe cel din dreapta cu $b$ Operatorul de deplasare la stânga (shift left, <<) mută toți biții lui $a$ la stânga cu $b$ poziții. Biții noi, ce vor apărea la dreapta, vor fi $0$ Cu alte cuvinte, se șterg primii $b$ biți din $a$ iar în dreapta sunt inserați $b$ biți cu valoarea $0$ Operatorul de deplasare la dreapta (shift right, >>) funcționează asemănător, doar că direcția de deplasare este, desigur, la dreapta. În ambele cazuri, $b$ poate fi chiar și negativ.

a      = 00110010
a << 3 = 10010000
a      = 00110010
a >> 1 = 00011001

După cum am zis, există și operatori compuși de atribuire pe biți (|=, &=, ^=, <<=, >>=). Aceștia lucrează direct asupra primului operand, rezultatul operației fiind stocat în acesta.

(a |= b) <=> (a = a | b)
(a &= b) <=> (a = a & b)
(a ^= b) <=> (a = a ^ b)
(a <<= b) <=> (a = a << b)
(a >>= b) <=> (a = a >> b)

Aplicații cu operațiile pe biți în C++

Problema 1.

Să se calculeze $2^k$

Observăm că $2^k$ are toți biții $0$ mai puțin pe cel de pe poziția $k$ (pozițiile începând cu $0$ de la dreapta la stânga). Soluția va fi dată de expresia 1 << k. Iată un exemplu:

1      = 00000001 = 2^0
1 << 3 = 00001000 = 2^3

Problema 2.

Să se determine câtul și restul împărțirii lui $n$ la $2^k$

Iată un exemplu:

n       = 01101010 = 2^6 + 2^5 + 2^3 + 2^1
n / 2^2 = 00011010 = 2^4 + 2^3 + 2^1
n % 2^2 = 00000010 = 2^1

Se observă că $n / 2^k$ se obține prin deplasarea la dreapta a $k$ biți, iar restul împărțirii este dat de ultimii $k$ biți ai lui $n$ Pentru punerea acestora în evidență, vom realiza & cu $2^k - 1$

01101010 &
00000011
--------
00000010

Deci, soluția este:

n >> k             // câtul
n & ((1 << k) - 1) // restul

Problema 3.

Să se determine valoarea bitului de pe poziția $k$ din numărul $n$

Soluția este să efectuăm & cu un număr care are $1$ doar pe poziția $k$ adică $2^k$

01011000 &   00011000 &
01000000     01000000
--------     --------
01000000     00000000

Rezultatul va fi $0$ dacă bitul este $0$ sau o valoare nenulă (mai exact $2^k$ dacă bitul e $1$ Soluția:

bool bit = n & (1 << k);

Problema 4.

Să se verifice dacă $n$ este o putere a lui $2$

Dacă $n$ este egal cu $2^k$ atunci $n - 1$ va avea ultimii $k$ biți $1$ Efectuând & între $n$ și $n - 1$ vom obține $0$ doar dacă $n$ este o putere a lui $2$

n     = 00010000 &
n - 1 = 00001111
        --------
        00000000

Avem însă un caz special, când $n$ este $0$ Prin urmare, mai întâi ne vom asigura că $n$ este nenul, soluția fiind:

bool isPowOf2 = n && !(n & (n - 1));

Problema 5.

Să se afișeze descompunerea în baza $2$ a numărului pozitiv $n$

Pur și simplu afișăm fiecare bit al lui $n$ de la stânga la dreapta. Putem afișa și bitul de semn, pentru că acesta oricum este $0$ pentru numerele pozitive. La fiecare pas accesăm bitul de pe poziția $i$ așa cum am explicat la problema 3.

for (int i = 31; i >= 0; i--)
    cout << (bool) (n & (1 << i));

Problema 6.

Să se marcheze cu $1$ bitul de pe poziția $k$ din numărul $n$

Ideea este să folosim disjuncția pe biți între $n$ și $2^k$

n      = 01101010 |
1 << k = 00010000
         --------
         01111010

Indiferent de valoarea inițială a bitului de pe poziția $k$ din $n$ valoarea lui va deveni $1$ iar ceilalți biți vor rămâne la fel.

n |= (1 << k);

Problema 7.

Să se marcheze cu $0$ bitul de pe poziția $k$ din numărul $n$

De data asta, scopul este să schimbăm bitul de pe poziția $k$ în $0$ indiferent de valoarea lui inițială, și să îi păstrăm pe restul cum erau. Putem realiza asta efectuând & cu un număr care are toți biții $1$ mai puțin pe cel de pe pe poziția $k$ Se poate observă că acest număr e de fapt ~(1 << k).

n         = 11011101 &
~(1 << k) = 10111111
            --------
            10011101

Prin urmare, soluția este:

n &= ~(1 << k)

Problema 8.

Să se codifice și apoi să se decodifice numărul $n$ folosind operația XOR.

Ne vom folosi de proprietatea a ^ b ^ b == a. Aceasta este adevărată pentru că b ^ b == 0, a ^ 0 == a, iar XOR-ul este asociativ. Vom considera p parola folosită în codificare. Atunci, n ^ p va fi $n$ul codificat, iar n ^ p ^ p $n$ul decodificat.

Problema 9.

Se dă un caracter x ce reprezintă o literă. Dacă x este o literă mare, să se convertească într-o literă mică, iar dacă x este o literă mică, să se convertească într-o literă mare.

Soluția imediată nu folosește operații pe biți, ci un simplu if.

if ('a' <= x && x <= 'z')
    x += 'A' - 'a';
else
    x += 'a' - 'A';

Însă, putem găsi o soluție mult mai scurtă, ce folosește operația XOR. Se știe că în tabelul ASCII, caracterul 'A' se află pe poziția 65, iar 'a' pe 97. Observăm că 97 - 65 == 32, 97 ^ 65 == 32, iar 32 == 1 << 5. Așadar, rezultatul operației x ^= 'a' ^ 'A' este practic scăderea sau adunarea lui 32 la codul caracterului x, în funcție de valoarea inițială a bitului său de pe poziția 5.

'E' =  69 = 01000101 ^
       32 = 00100000
            --------
'e' = 101 = 01100101

's' = 115 = 01110011 ^
       32 = 00100000
            --------
'S' =  83 = 01010011

Deci, răspunsul este:

x ^= 'a' ^ 'A';

Problema 10.

Să se determine numărul biților cu valoarea $1$ din $n$

O soluție imediată este parcurgerea biților lui $n$ La fiecare bit $1$ incrementăm răspunsul. Însă, putem observa că, în urma operației n &= (n - 1), se anulează cel mai din dreapta bit $1$ din $n$

n     = 01101000 &
n - 1 = 01100111
        --------
        01100000

De aici ne vine ideea să eliminăm la fiecare pas cel mai din dreapta bit de $1$ până când $n$ devine $0$ Această soluție este mai eficientă deoarece numărul de pași este egal cu numărul biților de $1$ din $n$

int cntBits(int n) {
    int cnt = 0;
    if (n)
        do
            cnt++;
        while (n &= (n - 1));
    return cnt;
}

Problema 11.

Să se determine cel mai puțin semnificativ bit de $1$ (least significant bit, LSB) din $n$ pentru $n$ nenul. Adică, dacă acesta se află pe poziția $k$ să se determine $2^k$

O soluție naivă este să parcurgem biții lui $n$ de la dreapta la stânga până dăm de unul care are valoarea $1$

int lsb(int n) {
    for (int i = 1; ; i <<= 1)
        if (n & i)
            return i;
}

O soluție mai eficientă se obține folosindu-ne de rezultatul de la problema anterioară. Se observă că dacă efectuăm XOR între $n$ și numărul rezultat după eliminarea ultimului bit de $1$ din $n$ obținem chiar $\mathrm{LSB}(n)$

n           = 01011000 ^
n & (n - 1) = 01010000
              --------
LSB(n)      = 00001000

Deci, iată cum arată funcția pentru calcularea $\mathrm{LSB}(n)$

inline int lsb(int n) {
    return n ^ (n & (n - 1));
}

O soluție și mai eficientă, și totodată ușor de reținut, se bazează pe modul de reprezentare al întregilor cu semn în C++:

inline int lsb(int n) {
    return -n & n;
}

Aceasta este o problemă esențială în implementarea arborilor indexați binar.

+n      = 00010110 &
     -n = 11101010
          --------
+n & -n = 00000010

Implementarea unui vector caracteristic pe biți

Operațiile pe biți pot fi folosite și pentru optimizarea memoriei folosită de programe, nu doar a timpului de rulare. De multe ori avem nevoie de folosirea unui vector cu multe valori de tip bool, de exemplu în Ciurul lui Eratostene. Ideea constă în compactarea vectorului reținând în fiecare bit câte o valoare booleană. Astfel, memoria ocupată de vector va fi de $\log_2 n$ ori mai mică! Prin $\log_2 n$ mă refer la numărul de biți necesari pentru a reprezenta un întreg.

Deci, dacă vectorul nostru este de tipul int, atunci folosim de $32$ de ori mai puțini bytes. Dacă e de tipul short int, folosim de $8$ ori mai puțină memorie etc. Dar asta nu înseamnă că, dacă dimensiunea tipului de date ales e mai mare, atunci facem mai multă economie. Mai degrabă, dacă sizeof(tip) ar fi mai mare și n-am compacta vectorul, atunci am consuma de sizeof(tip) ori mai multă memorie.

În STL există clase care pun în practică ideea asta, dar iată o implementare simplă a ei:

short int v[VMAX];

bool getBit(int pos) {
    int ind = pos >> 4; // poziția din v unde se află bitul
    int bit = pos & 15; // poziția bitului în v[ind]
    return v[ind] & (1 << bit);
}

void setBit(int pos, bool val) {
    int ind = pos >> 4; // / 16
    int bit = pos & 15; // % 16
    if (val)
        v[ind] |= 1 << bit;
    else
        v[ind] &= ~(1 << bit);
}

Generarea submulțimilor folosind operații pe biți

Modul în care sunt reprezentați întregii în C++ poate fi considerat de asemenea un bun mod de a reprezenta o submulțime a unei mulțimi date: Dacă valoarea bitului de pe poziția $k$ din întregul respectiv este $1$ înseamnă că al $k$lea element al mulțimii inițiale este luat, iar dacă este $0$ nu e luat. De obicei, când folosim un întreg pentru a codifica o submulțime în acest mod, el se va numi bitmask (mască de biți).

A = {0, 1, 2, 3}
0000 = {}          1000 = {3}
0001 = {0}         1001 = {0, 3}
0010 = {1}         1010 = {1, 3}
0011 = {0, 1}      1011 = {0, 1, 3}
0100 = {2}         1100 = {2, 3}
0101 = {0, 2}      1101 = {0, 2, 3}
0110 = {1, 2}      1110 = {1, 2, 3}
0111 = {0, 1, 2}   1111 = {0, 1, 2, 3}

Pentru a genera toate submulțimile unei mulțimi cu $n$ elemente, nu vom avea decât să iterăm de la $0$ la $2^n$ (numărul de submulțimi), exclusiv:

int nrSubm = 1 << n;
for (int subm = 0; subm < nrSubm; subm++)
    prelucrare(subm);

Această soluție este mai simplă și mai clară decât cea recursivă. În plus, în unele situații suntem chiar obligați să o folosim, cum ar fi în problemele de programare dinamică pe stări exponențiale, ca Ubuntzei.

Un alt avantaj al bitmask-urilor este că permit efectuarea în $O(1)$ a operațiilor pe mulțimi. Reuniunea a două mulțimi a și b va fi a | b, iar intersecția va fi dată de a & b.

Generarea submulțimilor unei submulțimi

Că tot vorbim de bitmask-uri, merită să prezint și cum putem genera submulțimile unui bitmask fără să construim un vector auxiliar în care să reținem pozițiile biților nenuli din bitmask-ul dat. Soluția constă într-un simplu for:

for (int subm = mask; subm; subm = (subm - 1) & mask)
    prelucrare(subm);

De remarcat că submulțimea nulă nu este procesată, așa că, dacă avem nevoie de ea, va trebui procesată după for.

Acest algoritm generează toate submulțimile lui mask, fără repetiție, în ordine descrescătoare din punct de vedere lexicografic. Să vedem de ce funcționează: Când scădem $1$ din subm, setăm cel mai puțin semnificativ bit al său la $0$ și toți biții de la dreapta lui la $1$ Apoi, când facem & între mask și subm - 1, ștergem surplusul de biți $1$ care nu apar în mask. Practic, am eliminat cel mai mic element al submulțimii și am adăugat toate elementele mai mici decât el, care fac parte din mulțimea dată.

00001101
00001100
00001001
00001000
00000101
00000100
00000001
00000000

Această metodă de generare a submulțimilor este utilă mai ales atunci când vrem să generăm toate submulțimile tuturor submulțimilor lui $\{0, 1, \ldots, n - 1\}$ Adică:

for (int mask = 0; mask < (1 << n); mask++)
    for (int subm = mask; subm; subm = (subm - 1) & mask)
        prelucrare(mask, subm);

Aparent, complexitatea celor două for-uri este $O(2^n \cdot 2^n) = O(4^n)$ De fapt, complexitatea este egală cu numărul submulțimilor submulțimilor lui $\{0, 1, \ldots, n - 1\}$ Acesta este dat de formula de mai jos, a cărei valoare vom vedea că este mai mică decât $4^n$

Putem rescrie formula astfel:

Acum, se vede destul de ușor că asta e dezvoltarea binomului $(1 + 2)^n$ care este egal cu $3^n$ Deci, complexitatea algoritmului este $O(3^n)$ nu $O(4^n)$

Probleme recomandate

• Panda
• Ubuntzei
• Rețeta2
• Jocul Flip

Dacă aveți vreo întrebare despre operațiile pe biți în C++, lăsați un comentariu mai jos și vă voi ajuta