Operații pe biți

Operațiile pe biți reprezintă un tip special de operații. Ele se efectuează asupra fiecărui bit al unui număr. În acest context, numerele sunt privite în reprezentarea binară. De exemplu, 2 în reprezentarea binară este 10 și are doi biți, iar numărul 7 este 111 și are trei biți.

Operații logice

• & (AND logic)

Operația de multiplicare se efectuează pe biți și, dacă ambii operanzi au valoarea bitului egală cu 1, operația returnează 1, altfel returnează 0. De exemplu:

int x1 = 2; // 010
int y1 = 5; // 101
Console.WriteLine(x1 & y1); // va afișa 0

int x2 = 4; // 100
int y2 = 5; // 101
Console.WriteLine(x2 & y2); // va afișa 4

În primul caz, avem două numere, 2 și 5. 2 în binar este 010, iar 5 este 101. Pe biți, multiplicăm numerele (0 & 1, 1 & 0, 0 & 1) și obținem 000.

În al doilea caz, avem numărul 4 în loc de 2, care în binar este 100, la fel ca și 5 în primul bit, astfel că obținem (1 & 1, 0 & 0, 0 & 1) = 100, adică numărul 4 în format zecimal.

• | (OR logic)

Similar cu multiplicarea logică, operația se efectuează pe biți, dar acum returnează 1 dacă cel puțin unul dintre biți este 1. De exemplu:

int x1 = 2; // 010
int y1 = 5; // 101
Console.WriteLine(x1 | y1); // va afișa 7 - 111

int x2 = 4; // 100
int y2 = 5; // 101
Console.WriteLine(x2 | y2); // va afișa 5 - 101

• ^ (XOR logic)

Această operație este cunoscută și sub numele de XOR și este utilizată adesea pentru criptare simplă:

int x = 45; // Valoare de criptat - în binar 101101
int key = 102; // Cheie - în binar 1100110

int encrypt = x ^ key; // Rezultatul va fi 1001011 sau 75
Console.WriteLine($"Număr criptat: {encrypt}");

int decrypt = encrypt ^ key; // Rezultatul va fi numărul inițial 45
Console.WriteLine($"Număr decriptat: {decrypt}");

Aici se efectuează din nou operații pe biți. Dacă valorile bitului curent pentru ambele numere sunt diferite, se returnează 1, altfel se returnează 0:

45 ^ 102 =
0101101
^
1100110
=
1001011
= 75

Astfel, obținem din 45 ^ 102 rezultatul 75. Și pentru a decripta numărul, aplicăm aceeași operație asupra rezultatului.

Similar, putem schimba două numere pozitive fără a folosi o variabilă suplimentară:

int a = 9;  // 1001
int b = 5;  // 0101

a = a ^ b;  // a = 1001 ^ 0101 = 1100 = 12
b = a ^ b;  // b = 12 ^ 5 = 1100 ^ 0101 = 1001 = 9
a = a ^ b;  // a = 12 ^ 9 = 1100 ^ 1001 = 0101 = 5

Console.WriteLine($"a: {a}");  // 5
Console.WriteLine($"b: {b}");  // 9

• ~ (NOT logic sau inversiune)

O altă operație pe biți care inversează toți biții: dacă valoarea bitului este 1, devine 0 și invers.

int x = 12;                 // 00001100
Console.WriteLine(~x);      // 11110011   sau -13

Reprezentarea numerelor negative

Pentru reprezentarea numerelor semnate în C#, se folosește codul complementului față de 2 (two’s complement), unde bitul cel mai semnificativ este bitul de semn. Dacă valoarea acestuia este 0, numărul este pozitiv, iar reprezentarea sa binară nu diferă de reprezentarea unui număr nesemnat. De exemplu, 0000 0001 în sistemul zecimal este 1.

Dacă bitul cel mai semnificativ este 1, avem de-a face cu un număr negativ. De exemplu, 1111 1111 în sistemul zecimal reprezintă -1. Astfel, 1111 0011 reprezintă -13.

Pentru a obține un număr negativ dintr-un număr pozitiv, trebuie să îl inversăm și să adăugăm unu:

int x = 12;
int y = ~x;
y += 1;
Console.WriteLine(y);   // -12

Operații de deplasare

Operațiile de deplasare se efectuează de asemenea asupra biților numerelor. Deplasarea poate fi spre dreapta sau spre stânga.

• x << y - deplasează numărul x spre stânga cu y biți. De exemplu, 4 << 1 deplasează numărul 4 (care în binar este 100) cu un bit spre stânga, rezultând 1000 sau numărul 8 în sistemul zecimal
• x >> y - deplasează numărul x spre dreapta cu y biți. De exemplu, 16 >> 1 deplasează numărul 16 (care în binar este 10000) cu un bit spre dreapta, rezultând 1000 sau numărul 8 în sistemul zecimal

Astfel, dacă numărul inițial este divizibil cu doi, deplasarea într-o direcție sau alta echivalează cu împărțirea sau înmulțirea cu doi. De aceea, această operație poate fi utilizată în locul înmulțirii sau împărțirii directe cu doi. De exemplu:

int a = 16; // în binar 10000
int b = 2;
int c = a << b; // Deplasare spre stânga a numărului 10000 cu 2 biți, rezultă 1000000 sau 64 în sistemul zecimal

Console.WriteLine($"Număr deplasat: {c}");    // 64

int d = a >> b; // Deplasare spre dreapta a numărului 10000 cu 2 biți, rezultă 100 sau 4 în sistemul zecimal
Console.WriteLine($"Număr deplasat: {d}");    // 4

Numerele implicate în operații nu trebuie neapărat să fie multipli de 2:

int a = 22; // în binar 10110
int b = 2;
int c = a << b; // Deplasare spre stânga a numărului 10110 cu 2 biți, rezultă 1011000 sau 88 în sistemul zecimal

Console.WriteLine($"Număr deplasat: {c}");    // 88

int d = a >> b; // Deplasare spre dreapta a numărului 10110 cu 2 biți, rezultă 101 sau 5 în sistemul zecimal
Console.WriteLine($"Număr deplasat: {d}");    // 5

Exemplar de aplicare practică a operațiilor pe biți

Multe persoane subestimează operațiile pe biți, neînțelegând la ce folosesc. Totuși, ele pot ajuta la rezolvarea unor probleme specifice. În primul rând, ele ne permit să manipulăm datele la nivel de bit. Un exemplu: avem trei numere cu valori între 0 și 3:

int value1 = 3;  // 0b0000_0011
int value2 = 2;  // 0b0000_0010
int value3 = 1;  // 0b0000_0001

Știm că valorile acestor numere nu vor depăși 3, și dorim să comprimăm datele cât mai mult posibil. Putem stoca cele trei numere într-un singur număr. Operațiile pe biți ne vor ajuta să facem acest lucru.

int value1 = 3;  // 0b0000_0011
int value2 = 2;  // 0b0000_0010
int value3 = 1;  // 0b0000_0001
int result = 0b0000_0000;

// stocăm în result valorile din value1
result = result | value1; // 0b0000_0011
// deplasăm biții în result cu 2 biți spre stânga
result = result << 2;   // 0b0000_1100
// stocăm în result valorile din value2
result = result | value2;  // 0b0000_1110
// deplasăm biții în result cu 2 biți spre stânga
result = result << 2;   // 0b0011_1000
// stocăm în result valorile din value3
result = result | value3;  // 0b0011_1001

Console.WriteLine(result);  // 57

Analizăm acest cod. Mai întâi, definim toate numerele value1, value2, value3. Pentru stocarea rezultatului, definim variabila result, care implicit este 0. Pentru claritate, îi atribuim valoarea în format binar:

int result = 0b0000_0000;

Stocăm primul număr în result:

result = result | value1; // 0b0000_0011

Aici folosim operația logică OR pe biți - dacă unul dintre biți este 1, bitul rezultat va fi 1. Practic:

0b0000_0000
|
0b0000_0011
=
0b0000_0011

Astfel, am stocat primul număr în result. Vom stoca numerele în ordine. Deci, mai întâi, în result va fi primul număr, apoi al doilea și al treilea. De aceea, deplasăm biții lui result cu doi biți spre stânga (numerele noastre ocupă în memorie cel mult doi biți):

result = result << 2;   // 0b0000_1100

Practic:

0b0000_0011 << 2 =
0b0000_1100

Repetăm operația logică OR și stocăm al doilea număr:

result = result | value2;  // 0b0000_1110

ceea ce este echivalent cu:

0b0000_1100
|
0b0000_0010
=
0b0000_1110

Repetăm deplasarea cu doi biți spre stânga și stocăm al treilea număr. În final, obținem în reprezentarea binară numărul 0b0011_1001. În sistemul zecimal, acest număr este 57. Dar acest lucru nu este important, pentru că ne interesează biții specifici ai numărului.

Este de remarcat că am stocat trei numere într-un singur număr și în variabila result mai este loc liber. De fapt, nu contează câți biți trebuie să stocăm. În acest exemplu, stocăm doar doi biți.

Pentru a restaura datele, folosim ordinea inversă:

result = 0b0011_1001
// obținerea inversă a datelor
int newValue3 = result & 0b0000_0011;
// deplasăm datele cu 2 biți spre dreapta
result = result >> 2;
int newValue2 = result & 0b0000_0011;
// deplasăm datele cu 2 biți spre dreapta
result = result >> 2;
int newValue1 = result & 0b0000_0011;
Console.WriteLine(newValue1);    // 3
Console.WriteLine(newValue2);   // 2
Console.WriteLine(newValue3);   // 1

Obținem numerele în ordinea inversă celei în care au fost stocate. Știind că fiecare număr ocupă doar doi biți, trebuie doar să obținem ultimii doi biți. Pentru aceasta, folosim masca de biți 0b0000_0011 și operația logică AND, care returnează 1 dacă ambii biți corespunzători sunt 1. Astfel, operația:

int newValue3 = result & 0b0000_0011;

este echivalentă cu:

0b0011_1001
&
0b0000_0011
=
0b0000_0001

Astfel, ultimul număr este 0b0000_0001 sau 1 în sistemul zecimal.

Dacă știm structura datelor, putem compune o mască de biți pentru a obține numărul dorit:

result = 0b0011_1001;
int recreatedValue1 = (result & 0b0011_0000) >> 4;
Console.WriteLine(recreatedValue1);

Aici obținem primul număr, care știm că ocupă biții 4 și 5. Folosim operația AND cu masca de biți 0b0011_0000 și apoi deplasăm numărul cu 4 biți spre dreapta.

0b0011_1001
&
0b0011_0000
=
0b0011_0000
>> 4
=
0b0000_0011

Similar, dacă știm exact structura în care sunt stocate datele, le putem stoca direct în poziția necesară în numărul result:

int value1 = 3;  // 0b0000_0011
int value2 = 2;  // 0b0000_0010
int value3 = 1;  // 0b0000_0001
int result = 0b0000_0000;

// stocăm în result valorile din value1
result = result | (value1 << 4);
// stocăm în result valorile din value2
result = result | (value2 << 2);
// stocăm în result valorile din value3
result = result | value3;  // 0b0011_1001

Console.WriteLine(result);  // 57