Operații pe biți

În informatică și în programare, bitul reprezintă unitatea de bază pentru stocarea informațiilor în memorie. Orice activitate desfășurată folosind un sistem de calcul (inclusiv articolul pe care îl citiți acum) are la bază o înșiruire de biți folosiți pentru a reda informația sub o formă accesibilă pentru oameni.

Din acest considerent, biții au ajuns să fie studiați în mod amănunțit, iar în cele ce urmează, vom prezenta sistemul binar, operațiile pe biți și diverse proprietăți, observații și tehnici pe care le putem folosi pentru a rezolva probleme de algoritmică, dar și modurile în care putem integra cunoștințele drept pași intermediari pentru rezolvarea altor probleme de algoritmică.

Sistemul binar

De-a lungul acestui articol, vom lucra cu numere reprezentate în formă binară (în baza 2), deci formate din cifre de 0 și de 1. De exemplu, dacă vrem să scriem numărul 27 în binar, reprezentarea acestuia va fi:

Deși de obicei nu lucrăm cu zerourile nesemnificative, în acest caz ele au fost prezentate pentru înțelegerea conceptului, precum și datorită faptului că așa cum ar trebui cunoscut deja, tipurile de date din limbajele C/C++ (și alte limbaje) au un număr de biți clar definit (de exemplu, int este un tip de date pe 32 de biți, char este un tip de date pe 8 biți ș.a.m.d.).

Legătura dintre o bază oarecare și baza 10

În cele ce urmează, prezentăm algoritmul de transformare a unui număr din baza 10 în baza $k$ și invers. Remarcăm faptul că acest algoritm funcționează indiferent de baza de la care plecăm, atâta timp cât baza 10 este parte din calculele noastre.

Transformarea unui număr din baza 10 în baza $k$

Pentru a transforma un număr din baza 10 în baza $k$, vom împărți repetat numărul la $k$, până când numărul va deveni 0, iar resturile împărțirilor pe care le obținem vor crea numărul în baza $k$, în ordine inversă.

Mai jos puteți găsi o scurtă implementare în limbajul C++.

int n, k;  // transformam n in baza k
cin >> n >> k;
int nrcif = 0, v[32];  // cifrele in baza k

// obtinem cifrele, una cate una
while (n > 0) {
    int c = n % k;
    nrcif++;
    v[nrcif] = c;
    n /= k;
}

// pentru a le afisa, le vom afisa invers
for (int i = nrcif; i >= 1; i--) {
    cout << v[i];
}
cout << '\n';

Transformarea unui număr din baza $k$ în baza 10

Pentru a transforma un număr din baza $k$ în baza 10, vom lua cifrele numărului, de la dreapta la stânga, și vom adăuga la răspunsul nostru $cif \cdot k^i$, unde $cif$ este cifra curentă, $k$ este baza de la care plecăm și $i$ este numărul pasului la care suntem.

Mai jos puteți găsi o scurtă implementare în limbajul C++.

int n, k;  // transformam n in baza 10, vom presupune ca se da numarul n drept
           // un numar zecimal dar cu cifre mai mici decat k
cin >> n >> k;
int nrcif = 0, v[32];  // cifrele in baza k

// obtinem cifrele, una cate una
while (n > 0) {
    int c = n % 10;
    nrcif++;
    v[nrcif] = c;
    n /= k;
}

// pentru a le afisa, le vom afisa invers
int putere = 1;
int zecimal = 0;  // numarul convertit in baza 10
for (int i = 1; i <= nrcif; i++) {
    zecimal += putere * v[i];  // adunam cifra inmultita cu puterea lui k
    putere *= k;  // la fiecare pas, crestem exponentul cu 1, inmultind cu k
}
cout << zecimal << '\n';

Operații pe biți

Pe lângă operațiile specifice lucrului cu diverse baze de numerație, putem lucra cu biți folosind operațiile consacrate pe biți, care ne vor permite să folosim eficiența lucrului cu biți la maxim. Pentru a efectua aceste operații, va trebui să știm ce operatori putem folosi. O bună parte din cunoștinte se vor lega de sintaxa învățată anterior, în special cele referitoare la operatorii logici.

În contextul algoritmic, putem vorbi de următorii operatori:

Operatorul AND ("și" pe biți)

Acest operator ia drept parametri două numere $a$ și $b$ și calculează pentru fiecare bit rezultatul operației logice AND. Cu alte cuvinte, pentru o poziție $i$, dacă ambii biți de pe poziția $i$ din $a$ și $b$ sunt egali cu 1, operația AND va returna 1 pentru acea poziție. Altfel, va returna 0. Mai jos puteți găsi un tabel de adevăr a acestei operații, notată în limbajele C/C++ cu &:

Operatorul OR ("sau" pe biți)

Acest operator ia drept parametri două numere $a$ și $b$ și calculează pentru fiecare bit rezultatul operației logice OR. Cu alte cuvinte, pentru o poziție $i$, dacă cel puțin unul din biții de pe poziția $i$ din $a$ și $b$ sunt egali cu 1, operația OR va returna 1 pentru acea poziție. Altfel, va returna 0. Mai jos puteți găsi un tabel de adevăr a acestei operații, notată în limbajele C/C++ cu |:

Operatorul XOR ("sau exclusiv" pe biți)

Acest operator ia drept parametri două numere $a$ și $b$ și calculează pentru fiecare bit rezultatul operației logice XOR. Cu alte cuvinte, pentru o poziție $i$, dacă exact unul din biții de pe poziția $i$ din $a$ și $b$ sunt egali cu 1, operația XOR va returna 1 pentru acea poziție. Altfel, va returna 0. Mai jos puteți găsi un tabel de adevăr a acestei operații, notată în limbajele C/C++ cu ^:

Shiftarea pe biți

Un alt operator care este folosit în foarte multe contexte este shiftarea pe biți, atât la stânga, cât și la dreapta. Operatorul este folosit atunci când vrem să înmulțim sau să împărțim un număr cu o putere a lui 2, lucru ce ne poate fi foarte folositor atunci când vrem să aflăm valoarea unui bit anume, să inițializăm o valoare minimă sau maximă, precum și în multe alte cazuri similare.

Shiftarea la stânga, notată cu << este folosită atunci când vrem să înmulțim un număr cu o putere a lui 2. Modul de folosire al acestui operator este a<<b, care are semnificația că înmulțim $a$ cu $2^b$.

Shiftarea la dreapta, notată cu >> este folosită atunci când vrem să împărțim un număr cu o putere a lui 2. Modul de folosire al acestui operator este a>>b, care are semnificația că împărțim $a$ cu $2^b$.

Proprietăți, aplicații și legături între operații pe biți

Atunci când vine vorba de operații pe biți, există diverse legături, proprietăți și trucuri pe care le putem folosi pentru a ajunge să rezolvăm mai ușor anumite probleme. Aici voi menționa cele mai frecvent întâlnite asemenea proprietăți, precizând pentru fiecare dintre ele utilitatea ei.

Lucrul cu submulțimi

Așa cum veți vedea în detaliu dacă veți citi articolul specific combinatoricii, lucrul cu submulțimi va reprezenta o aplicație importantă a lucrului cu biți, cele $2^n$ submulțimi ale unei mulțimi cu dimensiunea $n$ putând fi toate codificate folosind câte un număr în intervalul $[0, 2^n - 1]$.

Pentru mai multe detalii, puteți citi aici articolul nostru care privește în detaliu submulțimile din perspectiva combinatoricii. Totuși, aplicațiile prezentate acolo se aplică în totalitate și din perspectiva articolului curent.

Alternativ, puteți citi mai multe detalii de pe articolul de pe cp-algorithms despre enumerarea submulțimilor.

Probleme suplimentare

• morse ONI 2006
• intervale RoAlgo Contest #3
• Bit Showdown RoAlgo Contest #9
• patratele OJI 2022
• Matmare RoAlgo PreOJI 2024
• The Brand New Function
• Searching for Soulmates USACO
• Powered Addition
• Data Structures Fan
• castel OJI 2018
• Sheikh (Easy version)
• Three Days Ago
• 2+ Doors
• Preparing Olympiad
• Petr and a Combination Lock
• CSES Xor Pyramid
• Probleme cu operații pe biți de pe kilonova
• Probleme cu operații pe biți de pe codeforces

Lectură suplimentară

• Articol de pe USACO Guide
• Bitwise operations for beginners
• Bitwise operations for beginners, part 2
• Operații pe biți - Infoarena
• Operații pe biți - CPPI Sync
• Operații pe biți - Dan Pracsiu
• Bit Manipulation - cp-algorithms
• Curs lot juniori 2015
• Easy explanation about Bitwise operations [Tutorial]