OPERATORI PE BIȚI ÎN C++

OPERATORI PE BIȚI ÎN C++

Vom analiza operatorii pe biţi din C, precum şi utilitatea acestora prin câteva aplicaţii simple.
Lista operatorilor pe biţi:
~ - negaţie pe biţi
& - şi pe biţi (and)
| - sau pe biţi (or)
^ - sau exclusiv pe biţi (xor)
<< - deplasare la stânga pe biţi (shift left)
>> - deplasare la dreapta pe biţi (shift right)

Să menţionăm că operatorii logici pe biţi se aplică numai operanzilor de tip întreg. În exemplele următoare, vom considera că numerele sunt reprezentate pe 16 biţi fără semn (adică de tip unsigned short).
Negaţia pe biţi este operator unar şi are ca efect schimbarea biţilor 0 în 1 şi biţilor 1 în 0. În consecinţă, dacă a = 0000000000001110(2), atunci ~a = 1111111111110001(2)
Operatorii &, |, ^ sunt operatori binari. Tabelele operaţiilor sunt următoarele:


p q p & q p | q p ^ q
0 0 0 0 0
0 1 0 1 1
1 0 0 1 1
1 1 1 1 0

Considerând op ca fiind oricare din operatorii &, |, ^, o expresie de forma x op y operează asupra biţilor operanzilor x şi y. Astfel, dacă x = 1110(2) şi y = 1101(2) , atunci x & y = 1100(2), x | y = 1111(2), iar x ^ y = 0011(2).
Operatorii de deplasare, << şi >>, sunt operatori binari. Expresia x << i este echivalentă cu expresia x * 2i. De fapt acest operator elimină cei mai din stânga i biţi ai lui x şi adaugă la dreapta i biţi de 0. De exemplu, dacă x = 0000000000001110(2), atunci x << 2 înseamnă 0000000000111000(2) = 56 (adică 14 * 4).
Expresia x >> i este echivalentă cu x div 2i (împărţirea întreagă a lui x prin 2i). Operatorul de deplasare la dreapta elimină cei mai din dreapta i biţi ai lui x şi adaugă la stânga i biţi de 0. De exemplu, dacă x = 0000000000001110(2), atunci x >> 2 înseamnă 0000000000000011(2) = 3 (adică 14 div 4).

Probleme cu rezolvare

1. Se consideră un număr natural n. Să se verifice dacă n este par sau impar.
Rezolvare: Utilizăm operatorul &. Acesta are rol de testare a biţilor. Dacă n este impar, atunci reprezentarea sa în baza 2 va avea cel mai din dreapta bit pe 1. De exemplu, n = 13 se scrie în baza 2 ca 1101. Atunci 1101 & 1 = 1. Dacă n este par, atunci cel mai din dreapta bit va fi 0. De exemplu, n = 14 se scrie în baza 2 ca 1110. Atunci 1110 & 1 = 0. Iată că pentru orice număr n, expresia n & 1 furnizează ca rezultat cel mai din dreapta bit. Putem scrie atunci următoarea secvenţă:
cin >> n ;
if (( n & 1 ) == 1)
cout << "Număr impar" ;
else
cout << "Număr par" ;

De menţionat faptul că operatorii pe biţi au o prioritate mică, de aceea am preferat o pereche suplimentară de paranteze în expresia instrucţiunii if. Expresia n & 1 == 1 este interpretată de compilator ca fiind n & (1 == 1)
2. Se citeşte un număr natural k <= 15. Să se afişeze valoarea 2k.

Rezolvare: Ne bazăm pe operatorul de deplasare la stânga pe biţi. Expresia care furnizează răspunsul corect este 1 << k. Deci secvenţa va fi:

cin >> k ;
cout << (1 << k) ;

3. Se consideră un număr natural n. Să se determine câtul şi restul împărţirii lui n la 8. Generalizare: să se determine câtul şi restul împărţirii lui n la un număr care este putere a lui 2.

Rezolvare: Pentru determinarea câtului se utilizează deplasarea la dreapta cu 3 biţi (ceea ce este echivalent cu împărţirea prin 23). Pentru rest se utilizează expresia n & 7 (unde 7 vine de la 23- 1 ). Deoarece 7 = 1112 atunci toţi biţii lui n vor fi anulaţi, cu excepţia ultimilor 3 cei mai din dreapta. Generalizearea se obţine imediat, înlocuind 23 cu 2k.

cin >> n ;
cout << "Câtul este : " << (n >> 3) ;
cout << "Restul este : " << (n & 7) ;

4. Se consideră un număr natural n. Să se verifice dacă n este sau nu o putere a lui 2.

Rezolvare: Acesta este o problemă destul de cunoscută. Dacă n este o putere a lui 2, atunci reprezentarea sa în baza 2 are un singur bit 1, restul fiind 0. O primă idee ar fi deci să numărăm câţi biţi de 1 are n în baza 2. Dar o soluţie mai rapidă se bazează pe ideea că dacă n este o putere a lui 2, deci de forma 0000000000100000, atunci n-1 are reprezentarea de forma 0000000000011111, adică bitul 1 s-a transformat în 0, iar biţii de la dreapta sunt acum toţi 1. Deci o expresie de forma n & (n-1) va furniza rezultatul 0 dacă şi numai dacă n este o putere a lui 2.
cin >> n ;
if ( (n & (n-1)) == 0 )
 cout << "n este putere a lui 2" ;
else
cout << "n nu este putere a lui 2" ;

5. Se consideră un număr natural n. Să se afişeze reprezentarea lui n în baza 2.

Rezolvare: Ne bazăm pe faptul că în memorie n este deja reprezentat în baza 2, deci trebuie să-i afişăm biţii de la stânga la dreapta. Presupunând că n este reprezentat pe 16 biţi, pe aceştia îi numerotăm de la dreapta la stânga cu numere de la 0 la 15. Pentru a obţine bitul de pe poziţia i (0 <= i <= 15), utilizăm expresia (n >> i) & 1. Nu rămâne decât să utilizăm expresia pentru fiecare i între 0 şi 15.

cin >> n ;
for (int i=15 ; i >= 0 ; i--)
   cout << ((n >> i) & 1) ;

6. Se consideră două numere naturale n şi i (0 <= i <= 15). Să se marcheze cu 1 bitul i al lui n.

Rezolvare: Vom seta valoarea 1 la bitul i, indiferent de valoarea memorată anterior (0 sau 1). Pentru setare, utilizăm operatorul sau pe biţi. Expresia care realizează aceasta este n | (1 << i) . Să ne amintim dintr-un exerciţiu anterior că 1 << i înseamnă 2i. Expresia n | 2i nu va modifica decât bitul i care ne interesează, restul rămânând nemodificaţi, datorită faptului că dacă b este un bit atunci b | 0 este egal cu b.

7. Se consideră două numere naturale a şi b, ambele cuprinse între 0 şi 255. Se cere să se memoreze cele două numere într-un întreg n reprezentabil pe 16 biţi fără semn (deci de tip unsigned short).

Rezolvare: Cele două numere a şi b pot fi reprezentate pe 8 biţi. De aceea cei 16 biţi ai lui n sunt suficienţi. Stocăm a pe primii 8 biţi ai lui n, iar pe b pe ultimii 8 biţi ai lui n. n = a * 256 + b ; De asemenea, dacă se cunoaşte n, se pot obţine valorile lui a şi b astfel:

a = n >> 8 ; // sau a = n / 256
b = n & 255 ; // sau b = n % 256 ;

8. Codificare/decodificare. Considerăm un număr pe care dorim să-l codificăm, apoi să-l decodificăm.

Rezolvare: O modalitate simplă de codificare şi decodificare este utilizarea operatorului pe biţi XOR. Pentru aceasta considerăm o mască (o parolă) şi ne bazăm pe o proprietate interesantă a operatorului XOR: a ^ b ^ b = a. Deci a ^ b realizează codificarea lui a, iar (a ^ b) ^ b realizează decodificarea. Proprietatea se bazează pe faptul că b ^ b = 0, pentru orice b, iar a ^ 0 = a. Metoda poate fi aplicată şi pentru codificarea unui text utilizând o parolă dată. Cu ajutorul parolei aplicată peste textul iniţial se obţine codificarea, iar o a doua aplicare a parolei peste codificare se obţine textul iniţial. Secvenţa care realizează codificarea/decodificarea unui număr este:
int n, masca;
n = 65 ;
masca = 100 ;
cout << "\n Valoarea inițială a lui n : " << n ;
n = n ^ masca ;
cout<< "\n Valoarea codificată a lui n : " << n ;
n = n ^ masca ;
cout<< "\n Valoarea decodificată a lui n : " << n ;