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 232 - 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:

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:

După cum se poate vedea, se numără de la 0 la numărul pozitiv maxim (3), iar după ce bitul de semn devine 1, se numără de la cel mai mic număr negativ (-4) la cel mai mare (-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.

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.

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.

Î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.

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

a b a | b a & b a ^ b
0 0 0 0 0
0 1 1 0 1
1 0 1 0 1
1 1 1 1 0

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.

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.

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

Problema 1.

Să se calculeze 2k.

Observăm că 2k 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:

Problema 2.

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

Iată un exemplu:

Se observă că n / 2k 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 2k - 1:

Deci, soluția este:

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ă 2k.

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

Problema 4.

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

Dacă n este egal cu 2k, 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.

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:

Problema 5.

Să se afișeze descompunerea în baza 2 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.

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 2k.

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.

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).

Prin urmare, soluția este:

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 == 0a ^ 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.

Î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 = 25. 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.

Deci, răspunsul este:

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 soluția. Însă, putem observa că, în urma operației n &= (n - 1), se anulează cel mai din dreapta bit 1 din n.

De aici reiese soluția de mai jos. Aceasta este mai eficientă deoarece numărul de pași este egal cu numărul biților de 1.

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 2k.

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.

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 LSB(n):

Deci, iată cum arată funcția pentru calcularea LSB(n):

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++:

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

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 8 ori mai mică! Există și alternative STL la asta, dar iată o implementare simplă:

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).

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

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 submulțimi. Reuniunea a două submulțimi a și b va fi a | b, iar intersecția va fi dată de a & b.

Probleme recomandate

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

Îți place conținutul acestui site?

Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație. Află aici cum o poți face!