Articole recomandate

Operațiile pe biți, descrise aici sunt foarte rapide și au o serie de aplicații utile în practică. Acesta articol prezintă o parte dintre ele, limbajul de programare folosit fiind C/C++.

Reamintim faptul că biții din reprezentarea internă a unui număr întreg se numerotează începând de la 0, de la dreapta spre stânga.

Înmulțirea cu puteri ale lui 2

Înmulțirea cu o puterea lui 2 se face foarte rapid cu operația de deplasare la stânga pe biți, <<. Astfel, a * 2k este egal cu a << k. Desigur, atenție la overflow!

Împărțirea cu puteri ale lui 2

Câtul împărțirii poate fi determina prin deplasarea la dreapta, >>. Astfel, a / 2k este egal cu a >> k.

Verificarea parității unui număr

Reprezentarea în baza 2 a unui număr par (și reprezentarea sa internă) se termină cu cifra 0, iar a unui număr impar se termină cu 1. Atunci, deoarece reprezentarea lui 1 are un singur bit 1, restul fiind 0, operația n & 1 are rezultat:

• 0, dacă n este par
• 1, dacă n este impar

ÎN general n & 1 reprezintă ultimul bit din reprezentarea internă a lui n.

Verificarea faptului că un număr este putere a lui 2

Puterile lui 2 au un singur bit 1, ceilalți fiind 0. Mai clar, 2k are doar bitul k egal cu 1, ceilalți fiind 0. În plus, 2k-1 are toate cifrele binare 1 – de fapt, primele k cifre (de la dreapta) sunt 1, celelalte fiind 0. Observăm că aplicăm operația & între 2k și 2k-1 vom obține 0.

Pentru a verifica dacă un număr natural oarecare n este putere a lui 2, calculăm expresia n & (n-1). Rezultatul său este 0 dacă și numai dacă n este putere a lui 2.

În general, n & (n-1) are ca rezultat valoarea lui n în care ultimul bit 1 a fost transformat în 0. Dacă n este putere a lui 2, în rezultatul expresiei anterioare singurul bit 1 al lui n devine 0, deci rezultatul este 0.

Cea mai mare putere a lui 2 care îl divide pe n

Este egală cu 2 la puterea numărul de biți 0 de la sfârșitul reprezentării în baza 2 a lui n. Acest număr poate fi determinat rapid ca rezultat al expresiei n & -n. Analizați reprezentările interne a lui n și a lui -n pentru a înțelege mai bine!

Transformarea unui bit în 1

Fie n un număr întreg (de regulă natural), iar k un număr natural. Ne propunem să transformăm bitul k al lui n în 1, operație numită și setare a bitului k, ceilalți biți rămânând nemodificați – considerăm că valoarea lui k este mai mică decât numărul de cifre binare din reprezentarea internă a lui n (16 pentru short și unsigned short, 32 pentru int și unsigned int, etc.).

Transformarea unui bit în 1, precum și următoarele doua aplicații din acest articol (transformarea unui bit în 0 și determinarea valorii unui bit) se fac aplicând o anumită operație pe biți între numărul n și o mască, determinată convenabil pe baza valorii lui k.

În cazul transformării bitului k în 1, masca va avea doar bitul k egal cu 1, restul biților fiind 0. Astfel, masca este 1 << k, iar operația este n | (1 << k). Rezultatul ei are aceeași reprezentare internă ca n, cu excepția bitului k, care este transformat în 1; dacă bitul k era de la început 1, el nu se va modifica.

Mai precis, setarea bitului k se face prin următoarea atribuire: n = n | (1 << k);.

Transformarea unui bit în 0

Transformarea bitului k a lui n în 0, numită și resetarea bitului k, se face folosind o mască în care toți biții sunt 1, cu excepția bitului k sunt 1, bitul k fiind 0. Această mască este: ~(1 << k), ~ fiind operația de complementare a biților.

Atunci, resetarea bitului k a lui n se poate face cu atribuirea: n = n & ~(1 << k);.

Determinarea valorii unui bit

Pentru a determina bitul k al lui n putem folosi expresia (n >> k) & 1. Prin operația n >> k se elimină ultimele k cife binare ale lui n, iar (n >> k) & 1 reprezintă ultimul bit al lui n >> k, deci bitul k al lui n.

O altă variantă ar fi să folosim masca 1 << k, prin operația n & (1 << k). Rezultatul acestei operații este 0, dacă bitul k este 0, respectiv 2k (adică 1 << k), dacă bitul k este 1.

Proprietăți ale disjuncției exclusive ^

Disjuncția exclusivă are o proprietate interesantă, și anume că n ^ n este 0, indiferent de valoarea lui n. Acest lucru are câteva consecințe:

• a ^ b ^ b este egal cu a. Putem realizat astfel un mecanism de cripare:
  • fie n un număr care trebuie criptat și k un număr care reprezintă cheia de criptare;
  • pentru criptare folosim operația n ^ k, prin care obținem numărul criptat c;
  • pentru decriptare folosim operația c ^ k, prin care obținem numărul inițial n;
• dacă avem mai multe valori x și una singură apare de un număr impar de ori (celelalte apărând de număr par de ori), o putem determina calculând suma XOR a numerelor x, adică:
  • S = 0;
  • pentru fiecare x
    • S ^= x;
  • rezultatul este S.
• putem interschimba valorile a două variabile a și b, fără a folosi o variabilă suplimentară:
  • a = a ^ b;
  • b = a ^ b;
  • a = a ^ b;

Principiul lui Dirichlet sau Principiul cutiei sau Principiul porumbeilor este o generalizare a următoarei afirmații: Dacă avem trei pantofi, atunci avem sigur cel puțin doi pantofi drepți sau cel puțin doi pantofi stângi.

El este cunoscut în mai multe variante echivalente:

1. Dacă avem n cutii în care punem n+1 bile, atunci va exista cel puțin o cutie cu cel puțin două bile.
   • Dacă avem n porumbei și n-1 cuști, atunci cel puțin o cușcă va conține cel puțin doi porumbei.
2. Dacă N obiecte trebuie plasate în M containere, unde N>M, atunci cel puțin un container va conține mai mult decât un obiect.
3. Dacă plasăm \( k \times n+1 \) obiecte în \( n \) cutii (\( n,k \in \mathbb{N} \)), atunci cel puțin \( k + 1 \) vor fi în aceeași cutie.

Aplicații

Șosete

Avem N perechi de șosete de culori diferite. Ele sunt într-un sertar într-o cameră fără lumină. Câte șosete trebuie extrase din sertar pentru a fi siguri că avem două șosete împerechiate?

Soluție: Avem N culori (cutii). Conform principiului cutiei, dacă alegem N+1 șosete, vom avea cel puțin două de aceeași culoare. În pus, dacă alegem N șosete, pot fi de culori diferite două câte două. Răspunsul este deci N+1.

Aniversări

Într-o școală sunt 367 de elevi. Arătați că cel puțin doi dintre își serbează ziua de naștere la aceeași dată.

Soluție: Într-un an sunt cel mult N=366 zile (cutii). Avem M>N obiecte (elevi), deci cel puțin doi elevi își vor serba ziua de naștere la aceeași dată.

Numere

În orice mulțime de N+1 numere naturale există cel puțin două a căror diferență se divide cu N.

Soluție: Resturile posibile la împărțirea cu N sunt 0, 1, 2, ..., N-1. Deoarece avem N+1 numere, vom avea două numere cu același rest al împărțirii la N. Diferență lor se divide cu N!

Pătrate perfecte

În orice mulțime cu 7 pătrate perfecte există cel puțin două a căror diferență se divide cu 10.

Soluție: Un pătrat perfect se poate termina cu cifra 0, 1, 4, 5, 6 sau 9, adică resturile posibile la împărțirea unui pătrat perfect la 10 sunt 0 1 4 5 6 9. Sunt 6 resturi posibile și 7 numere, deci vor fi cel puțin două cu același rest; diferența lor va fi divizibilă cu 10.

Pătrate

Arătați că oricum am plasa 5 puncte pe suprafața unui pătrat cu latura 1, există două puncte între care distanța este cel mult \( \frac{\sqrt{2}}{2} \).

Soluție: Împărțim pătratul inițial în patru pătrate cu latura \( \frac{1}{2} \). Unul dintre pătrate va conține cel puțin două puncte, iar distanța dintre ele este cel mult egală cu diagonala pătratului, adică \( \frac{\sqrt{2}}{2} \).

Operațiile pe biți sunt operații foarte eficiente, deoarece ele lucrează direct cu biții din reprezentările în memorie ale operanzilor. Înțelegerea lor presupune înțelegerea reprezentării în memorie a datelor întregi.

Reprezentarea în memorie a valorilor întregi

Valorile întregi se reprezintă în memorie ca o secvență de biți (cifre binare, 0 și 1). Acestă secvență poate avea 8, 16, 32 sau 64 de biți.

Reprezentarea în memorie a datelor de tip întreg se face în mod similar pentru toate tipurile cu semn (char, short int, int, long long int) și similar pentru toate tipurile fără semn (unsigned char, unsigned short int, unsigned int, unsigned long long int).

În exemplele care urmează vom folosi tipurile reprezentate pe 16 biți: unsigned short int, respectiv short int.

Reprezentarea în memorie a valorilor de tip unsigned short int

Tipul unsigned short int memorează valori mai mari sau egale cu 0. Acestea se reprezintă în memorie astfel:

• se transformă numărul în baza 2 și se memorează, adăugând la început cifre de 0 nesemnificative, atâtea câte sunt necesare până la completarea celor 16 biți.
• dacă reprezentarea în baza 2 a numărului are mai mult de 16 cifre, se vor memora numai ultimele 16 cifre – numărul se va trunchia.

Astfel, valorile fără semn care se pot reprezenta pe 16 biți sunt cuprinse între 0 și 216-1, adică 0 și 65535.

• 0 se reprezintă 0000000000000000
• 65535 se reprezintă 1111111111111111
• 5 se reprezintă 0000000000000101
• 133 se reprezintă 0000000010000101

Reprezentarea în memorie a valorilor de tip short int

Tipul short int memorează atât valori pozitive, cât și valori negative. Astfel, dintre cei 16 biți disponibili, cel mai din stânga (numit bit de semn) stabilește semnul numărului. Dacă acest bit este 0, numărul este pozitiv, dacă acest bit este 1, numărul este negativ. Astfel, se pot memora 32768 valori negative, de la -32768 la -1, și 32768 pozitive sau zero, de la 0 la 32767.

Reprezentarea numerelor pozitive se face exact ca mai sus: se transformă numărul în baza 2 și se completează cu zerouri nesemnificative.

Nu la fel se face reprezentarea numerelor întregi negative. Această reprezentare se face conform pașilor următori, numită reprezentare în cod complementar:

1. se determină reprezentarea în memorie a numărului ce reprezintă valoarea absolută a numărului inițial. Aceasta are bitul de semn 0.
2. se determină complementul față de 1 a reprezentării de la pasul anterior – fiecare bit 1 devine 0 și fiecare bit 0 devine 1.
3. se adună 1 la valoarea obținută

De exemplu, pentru reprezentarea în memorie a numărului -133 (considerat de tip short int) se procedează astfel:

1. se determină reprezentarea în memorie a lui 133 și se obține:
   0000000010000101
2. se obține complementul față de 1:
   1111111101111010
3. se adună 1 și se obține:
   1111111101111011

Mecanismul de memorare numerelor este același pentru toate tipurile întregi. Diferă numai numărul de biți folosiți pentru reprezentare și implicit intervalul din care fac parte valorile reprezentate.

Operatori pe biți

Operațiile pe biți se aplică numai datelor de tip întreg, și presupun manipularea directă a biților din reprezentarea în memorie a operanzilor.

Operatorul de negație ~

Este un operator unar care are ca rezultat numărul obținut prin complementarea față de 1 a biților din reprezentarea numărului inițial (biții 0 devin 1, biții 1 devin 0).

Exemplu:

~ 133 == -134

Reprezentarea lui 133 este 0000000010000101. Prin complementare se obține 1111111101111010. Aceasta este reprezentarea în memorie a lui -134.

Pentru a verifica, îl reprezentăm conform celor de mai sus pe -134:

1. reprezentarea lui 134 este 0000000010000110
2. prin complementare se obține 1111111101111001
3. adunăm 1 și obținem 1111111101111010

Operatorul de conjuncție biți &

Este un operator binar care are ca rezultat numărul obținut prin conjuncția fiecărei perechi de biți ce apar în reprezentare în memorie a operanzilor:

0 & 0 == 0
0 & 1 == 0
1 & 0 == 0
1 & 1 == 1

Exemplu:

Să calculăm 13 & 151.

Reprezentarea lui 13 este 0000000000001101. Reprezentarea lui 151 este 0000000010010111:

0000000000001101 &
0000000010010111

Se obține:

0000000000000101, adică 5

Deci: 13 & 151 == 5

Operatorul de disjuncție pe biți |

Este un operator binar care are ca rezultat numărul obținut prin disjuncția fiecărei perechi de biți ce apar în reprezentare în memorie a operanzilor:

0 | 0 == 0
0 | 1 == 1
1 | 0 == 1
1 | 1 == 1

Exemplu:

Să calculăm 13 | 151.

Reprezentarea lui 13 este 0000000000001101. Reprezentarea lui 151 este 0000000010010111:

0000000000001101 |
0000000010010111

Se obține:

0000000010011111, adică 159

Deci: 13 | 151 == 159

Operatorul de disjuncție exclusivă ^

Este un operator binar care are ca rezultat numărul obținut prin disjuncția exclusivă fiecărei perechi de biți ce apar în reprezentare în memorie a operanzilor:

0 ^ 0 == 0
0 ^ 1 == 1
1 ^ 0 == 1
1 ^ 1 == 0

Exemplu:

Să calculăm 13 ^ 151.

Reprezentarea lui 13 este 0000000000001101. Reprezentarea lui 151 este 0000000010010111:

0000000000001101 ^
0000000010010111

Se obține:

0000000010011010, adică 2 + 8 + 16 + 128 = 154.

Deci: 13 ^ 151 == 154

Operatorul de deplasare spre stânga – shift left <<

Este un operator binar care are ca rezultat numărul obținut prin deplasare spre stânga a biților din reprezentarea în memorie a primului operand cu un număr de poziții egal cu al doilea operand.

Să calculăm 13 << 3.

Reprezentarea lui 13 este 0000000000001101. Deplasând toți biții spre stânga cu 3 poziții se obține: 0000000001101000, adică 104.

Să observăm că 104 este egal cu 13 * 23. În general n << k este n * 2k.

Pentru a calcula 2n putem folosi operația 1 << n.

Operatorul de deplasare spre dreapta – shift right >>

Este un operator binar care are ca rezultat numărul obținut prin deplasare spre dreapta a biților din reprezentarea în memorie a primului operand cu un număr de poziții egal cu al doilea operand.

Să calculăm 133 >> 3.

Reprezentarea lui 133 este 0000000010000101. Deplasând toți biții spre dreapta cu 3 poziții se obține: 0000000000010000 adică 16.

Să observăm că 16 este egal cu 133 / 23. În general n >> k este n / 2k.

Vezi și

• Aplicații ale operațiilor pe biți