Operații pe biți în C++ – Generare de submulțimi și nu numai!

Operații pe biți în C++ – Generare de submulțimi și nu numai!

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 22 sau cu puteri ale lui 22 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 00 iar dacă e negativ 11 În cazul numerelor pozitive, pe ceilalți 31 de biți, de la stânga la dreapta, se află reprezentarea în baza 22 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-0 și +0+0 sunt reprezentați diferit.

În codificarea folosită de C++, pentru numărul negativ x-x se va reține reprezentarea lui 232x2^{32} - x Această reprezentare garantează că bitul de semn va fi 11 doar pentru numerele strict negative. Iată cum arată două numere reținute pe un tip întreg de 8 biți:

01011000 = 2^6 + 2^4 + 2^3 = 88
11011000 = -(2^8 - (2^7 + 2^6 + 2^4 + 2^3)) = -(256 - 216) = -40

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 33 nu este o putere a lui 22 numerele ce pot fi reprezentate pe el sunt:

000 = 0
001 = 1
010 = 2
011 = 3
100 = -4
101 = -3
110 = -2
111 = -1

După cum se poate vedea, se numără de la 00 la numărul pozitiv maxim (3\htmlClass{katexified}{(} 3 iar după ce bitul de semn devine 11 se numără de la cel mai mic număr negativ (4\htmlClass{katexified}{(} -4 la cel mai mare (1\htmlClass{katexified}{(} -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 22 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 00 vor deveni 11 iar biții 11 vor deveni 00

x = 00010110
~x = 11101001

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 aa și bb rezultatul cu cc iar cu xix_i bitul de pe poziția ii din xx

După aplicarea disjuncției pe biți (|), cic_i va fi 11 dacă măcar unul dintre aia_i și bib_i este 11 iar 00 în caz contrar.

01110010 |
11000110
--------
11110110

Dacă operația efectuată este conjuncția pe biți (&), cic_i va fi 11 dacă aia_i și bib_i sunt ambele 11 iar 00 dacă nu.

01010100 &
11001110
--------
01000100

În cazul disjuncției exclusive, numită și XOR (^), cic_i ia valoarea 11 dacă aia_i e diferit de bib_i sau 00 dacă aia_i și bib_i sunt egale.

10110111 ^
00011010
--------
10101101

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

aba | ba & ba ^ b
00000
01101
10101
11110

Operatorii de deplasare a biților (<<, >>)

Vom nota operandul din stânga cu aa iar pe cel din dreapta cu bb Operatorul de deplasare la stânga (shift left, <<) mută toți biții lui aa la stânga cu bb poziții. Biții noi, ce vor apărea la dreapta, vor fi 00 Cu alte cuvinte, se șterg primii bb biți din aa iar în dreapta sunt inserați bb biți cu valoarea 00 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, bb poate fi chiar și negativ.

a = 00110010
a << 3 = 10010000
a = 00110010
a >> 1 = 00011001

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.

(a |= b) <=> (a = a | b)
(a &= b) <=> (a = a & b)
(a ^= b) <=> (a = a ^ b)
(a <<= b) <=> (a = a << b)
(a >>= b) <=> (a = a >> b)

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

Problema 1.

Să se calculeze 2k2^k

Observăm că 2k2^k are toți biții 00 mai puțin pe cel de pe poziția kk (pozițiile începând cu 00 de la dreapta la stânga). Soluția va fi dată de expresia 1 << k. Iată un exemplu:

1 = 00000001 = 2^0
1 << 3 = 00001000 = 2^3

Problema 2.

Să se determine câtul și restul împărțirii lui nn la 2k2^k

Iată un exemplu:

n = 01101010 = 2^6 + 2^5 + 2^3 + 2^1
n / 2^2 = 00011010 = 2^4 + 2^3 + 2^1
n % 2^2 = 00000010 = 2^1

Se observă că n/2kn / 2^k se obține prin deplasarea la dreapta a kk biți, iar restul împărțirii este dat de ultimii kk biți ai lui nn Pentru punerea acestora în evidență, vom realiza & cu 2k12^k - 1

01101010 &
00000011
--------
00000010

Deci, soluția este:

n >> k // câtul
n & ((1 << k) - 1) // restul

Problema 3.

Să se determine valoarea bitului de pe poziția kk din numărul nn

Soluția este să efectuăm & cu un număr care are 11 doar pe poziția kk adică 2k2^k

01011000 & 00011000 &
01000000 01000000
-------- --------
01000000 00000000

Rezultatul va fi 00 dacă bitul este 00 sau o valoare nenulă (mai exact 2k2^k dacă bitul e 11 Soluția:

bool bit = n & (1 << k);

Problema 4.

Să se verifice dacă nn este o putere a lui 22

Dacă nn este egal cu 2k2^k atunci n1n - 1 va avea ultimii kk biți 11 Efectuând & între nn și n1n - 1 vom obține 00 doar dacă nn este o putere a lui 22

n = 00010000 &
n - 1 = 00001111
--------
00000000

Avem însă un caz special, când nn este 00 Prin urmare, mai întâi ne vom asigura că nn este nenul, soluția fiind:

bool isPowOf2 = n && !(n & (n - 1));

Problema 5.

Să se afișeze descompunerea în baza 22 a numărului pozitiv nn

Pur și simplu afișăm fiecare bit al lui nn de la stânga la dreapta. Putem afișa și bitul de semn, pentru că acesta oricum este 00 pentru numerele pozitive. La fiecare pas accesăm bitul de pe poziția ii așa cum am explicat la problema 3.

for (int i = 31; i >= 0; i--)
cout << (bool) (n & (1 << i));

Problema 6.

Să se marcheze cu 11 bitul de pe poziția kk din numărul nn

Ideea este să folosim disjuncția pe biți între nn și 2k2^k

n = 01101010 |
1 << k = 00010000
--------
01111010

Indiferent de valoarea inițială a bitului de pe poziția kk din nn valoarea lui va deveni 11 iar ceilalți biți vor rămâne la fel.

n |= (1 << k);

Problema 7.

Să se marcheze cu 00 bitul de pe poziția kk din numărul nn

De data asta, scopul este să schimbăm bitul de pe poziția kk în 00 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 11 mai puțin pe cel de pe pe poziția kk Se poate observă că acest număr e de fapt ~(1 << k).

n = 11011101 &
~(1 << k) = 10111111
--------
10011101

Prin urmare, soluția este:

n &= ~(1 << k)

Problema 8.

Să se codifice și apoi să se decodifice numărul nn folosind operația XOR.

Ne vom folosi de proprietatea a ^ b ^ b == a. Aceasta este adevărată pentru că b ^ b == 0, a ^ 0 == a, iar XOR-ul este asociativ. Vom considera p parola folosită în codificare. Atunci, n ^ p va fi nnul codificat, iar n ^ p ^ p nnul 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.

if ('a' <= x && x <= 'z')
x += 'A' - 'a';
else
x += 'a' - 'A';

Î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 == 1 << 5. 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.

'E' = 69 = 01000101 ^
32 = 00100000
--------
'e' = 101 = 01100101
's' = 115 = 01110011 ^
32 = 00100000
--------
'S' = 83 = 01010011

Deci, răspunsul este:

x ^= 'a' ^ 'A';

Problema 10.

Să se determine numărul biților cu valoarea 11 din nn

O soluție imediată este parcurgerea biților lui nn La fiecare bit 11 incrementăm răspunsul. Însă, putem observa că, în urma operației n &= (n - 1), se anulează cel mai din dreapta bit 11 din nn

n = 01101000 &
n - 1 = 01100111
--------
01100000

De aici ne vine ideea să eliminăm la fiecare pas cel mai din dreapta bit de 11 până când nn devine 00 Această soluție este mai eficientă deoarece numărul de pași este egal cu numărul biților de 11 din nn

int cntBits(int n) {
int cnt = 0;
if (n)
do
cnt++;
while (n &= (n - 1));
return cnt;
}

Problema 11.

Să se determine cel mai puțin semnificativ bit de 11 (least significant bit, LSB) din nn pentru nn nenul. Adică, dacă acesta se află pe poziția kk să se determine 2k2^k

O soluție naivă este să parcurgem biții lui nn de la dreapta la stânga până dăm de unul care are valoarea 11

int lsb(int n) {
for (int i = 1; ; i <<= 1)
if (n & i)
return i;
}

O soluție mai eficientă se obține folosindu-ne de rezultatul de la problema anterioară. Se observă că dacă efectuăm XOR între nn și numărul rezultat după eliminarea ultimului bit de 11 din nn obținem chiar LSB(n)\mathrm{LSB}(n)

n = 01011000 ^
n & (n - 1) = 01010000
--------
LSB(n) = 00001000

Deci, iată cum arată funcția pentru calcularea LSB(n)\mathrm{LSB}(n)

inline int lsb(int n) {
return n ^ (n & (n - 1));
}

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

inline int lsb(int n) {
return -n & n;
}

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

+n = 00010110 &
-n = 11101010
--------
+n & -n = 00000010

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 log2n\log_2 n ori mai mică! Prin log2n\log_2 n mă refer la numărul de biți necesari pentru a reprezenta un întreg.

Deci, dacă vectorul nostru este de tipul int, atunci folosim de 3232 de ori mai puțini bytes. Dacă e de tipul short int, folosim de 88 ori mai puțină memorie etc. Dar asta nu înseamnă că, dacă dimensiunea tipului de date ales e mai mare, atunci facem mai multă economie. Mai degrabă, dacă sizeof(tip) ar fi mai mare și n-am compacta vectorul, atunci am consuma de sizeof(tip) ori mai multă memorie.

În STL există clase care pun în practică ideea asta, dar iată o implementare simplă a ei:

short int v[VMAX];
bool getBit(int pos) {
int ind = pos >> 4; // poziția din v unde se află bitul
int bit = pos & 15; // poziția bitului în v[ind]
return v[ind] & (1 << bit);
}
void setBit(int pos, bool val) {
int ind = pos >> 4; // / 16
int bit = pos & 15; // % 16
if (val)
v[ind] |= 1 << bit;
else
v[ind] &= ~(1 << bit);
}

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 kk din întregul respectiv este 11 înseamnă că al kklea element al mulțimii inițiale este luat, iar dacă este 00 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).

A = {0, 1, 2, 3}
0000 = {} 1000 = {3}
0001 = {0} 1001 = {0, 3}
0010 = {1} 1010 = {1, 3}
0011 = {0, 1} 1011 = {0, 1, 3}
0100 = {2} 1100 = {2, 3}
0101 = {0, 2} 1101 = {0, 2, 3}
0110 = {1, 2} 1110 = {1, 2, 3}
0111 = {0, 1, 2} 1111 = {0, 1, 2, 3}

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

int nrSubm = 1 << n;
for (int subm = 0; subm < nrSubm; subm++)
prelucrare(subm);

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)O(1) a operațiilor pe mulțimi. Reuniunea a două mulțimi a și b va fi a | b, iar intersecția va fi dată de a & b.

Generarea submulțimilor unei submulțimi

Că tot vorbim de bitmask-uri, merită să prezint și cum putem genera submulțimile unui bitmask fără să construim un vector auxiliar în care să reținem pozițiile biților nenuli din bitmask-ul dat. Soluția constă într-un simplu for:

for (int subm = mask; subm; subm = (subm - 1) & mask)
prelucrare(subm);

De remarcat că submulțimea nulă nu este procesată, așa că, dacă avem nevoie de ea, va trebui procesată după for.

Acest algoritm generează toate submulțimile lui mask, fără repetiție, în ordine descrescătoare din punct de vedere lexicografic. Să vedem de ce funcționează: Când scădem 11 din subm, setăm cel mai puțin semnificativ bit al său la 00 și toți biții de la dreapta lui la 11 Apoi, când facem & între mask și subm - 1, ștergem surplusul de biți 11 care nu apar în mask. Practic, am eliminat cel mai mic element al submulțimii și am adăugat toate elementele mai mici decât el, care fac parte din mulțimea dată.

00001101
00001100
00001001
00001000
00000101
00000100
00000001
00000000

Această metodă de generare a submulțimilor este utilă mai ales atunci când vrem să generăm toate submulțimile tuturor submulțimilor lui {0,1,,n1}\{0, 1, \ldots, n - 1\} Adică:

for (int mask = 0; mask < (1 << n); mask++)
for (int subm = mask; subm; subm = (subm - 1) & mask)
prelucrare(mask, subm);

Aparent, complexitatea celor două for-uri este O(2n2n)=O(4n)O(2^n \cdot 2^n) = O(4^n) De fapt, complexitatea este egală cu numărul submulțimilor submulțimilor lui {0,1,,n1}\{0, 1, \ldots, n - 1\} Acesta este dat de formula de mai jos, a cărei valoare vom vedea că este mai mică decât 4n4^n

k=0nCnk2k\sum_{k = 0}^n C_n^k \cdot 2^k

Putem rescrie formula astfel:

k=0nCnk1nk2k\sum_{k = 0}^n C_n^k \cdot 1^{n - k} \cdot 2^k

Acum, se vede destul de ușor că asta e dezvoltarea binomului (1+2)n(1 + 2)^n care este egal cu 3n3^n Deci, complexitatea algoritmului este O(3n)O(3^n) nu O(4n)O(4^n)

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

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii