Operații pe biți în C++: măști și aplicații

Operațiile pe biți prelucrează reprezentarea binară a numerelor întregi. Operatorii & și | combină biții prin ȘI și SAU, ^ aplică SAU exclusiv, ~ inversează biții, iar << și >> deplasează pozițiile. Nu îi confunda cu operatorii logici && și ||.

O mască are biți aleși pentru a testa sau modifica o proprietate. Numerotăm pozițiile de la zero, începând cu bitul cel mai puțin semnificativ. Bitul k reprezintă puterea 2^k.

Cum funcționează

Masca pentru poziția k este 1u << k. Testul (x & mask) != 0 arată dacă bitul este unu. Operația x | mask îl setează, x & ~mask îl șterge, iar x ^ mask îl comută. Celelalte poziții rămân nemodificate deoarece masca are zero în afara poziției urmărite.

Folosim tipuri fără semn și deplasări valide. Deplasarea cu un număr negativ sau cu o valoare cel puțin egală cu lățimea tipului nu este validă. În exemplele școlare este tentant să scrii simplu 1<<k, însă literalul cu semn poate introduce dificultăți la biții mari. Limitele explicite sunt mai importante decât prescurtarea.

Identitatea x & (x-1) șterge bitul unu cel mai din dreapta pentru x nenul. Repetând operația putem număra biții setați. De asemenea, un număr fără semn nenul este putere a lui doi exact când această expresie produce zero. Condiția x!=0 este obligatorie, deoarece și zero ar satisface singur testul bitwise.

Exemplu urmărit pas cu pas

Pentru x=10, reprezentarea pe patru biți este 1010. Dacă k=0, bitul este zero; setarea produce 1011, adică 11, ștergerea păstrează 10, iar comutarea produce 11. Numărarea aplică 1010 & 1001 = 1000, apoi 1000 & 0111 = 0000, deci găsește doi biți unu.

Programul presupune 0 <= x <= 32767 și 0 <= k <= 14. Aceste limite păstrează exemplul valid și pe implementări cu unsigned int de cel puțin 16 biți. Pentru măști mai mari alegi un tip cu lățime explicită și verifici din nou domeniul deplasării.

Implementare C++17

#include <iostream>
int main() {
    unsigned int x;
    int k;
    std::cin >> x >> k;
    unsigned int mask = 1u << k;
    std::cout << ((x & mask) != 0) << ' ' << (x | mask) << ' ' << (x & ~mask) << ' '
              << (x ^ mask) << '\n';
    int count = 0;
    while (x) {
        x &= x - 1;
        ++count;
    }
    std::cout << count << '\n';
}

De ce funcționează și cât costă

O mască cu un singur bit unu izolează exact poziția cerută. În scăderea x-1, bitul unu cel mai din dreapta devine zero și biții inferiori devin unu; operația & elimină exact acel bit din x. Numărul iterațiilor coincide astfel cu numărul biților setați.

Operațiile pe un tip de dimensiune fixă au cost constant în modelul uzual. Bucla de numărare execută câte un pas pentru fiecare bit unu, cel mult lățimea tipului. Memoria suplimentară este O(1).

Greșeli frecvente

Operatorul ^ nu înseamnă ridicare la putere în C++. Pune paranteze în expresii mixte și nu te baza pe o prioritate ghicită. Nu folosi o mască numerică drept condiție logică fără să înțelegi ce biți testezi.

Exersează

Pentru 12, scrie reprezentarea binară și rezultatul după ștergerea bitului de pe poziția 2.

Rezolvare explicată: 12 este 1100 în baza doi. Masca poziției 2 este 0100; după x & ~mask rămâne 1000, adică 8. Bitul poziției 3 rămâne neschimbat.

Continuă să înveți

Baze de numerație, operatori și tipuri.

Întrebări frecvente

Este x^2 pătratul lui x?

Nu. În C++, ^ este SAU exclusiv pe biți. Pătratul unui număr se calculează prin x*x, cu un tip numeric suficient pentru rezultat.

Cum testez dacă bitul k este setat?

Construiești masca 1u<<k și verifici dacă x & mask este diferit de zero. Poziția k trebuie să fie validă pentru tipul folosit.

Cum recunosc o putere a lui doi?

Pentru un număr fără semn, verifici x!=0 și (x & (x-1))==0. Condiția de nenul exclude zero, care nu este putere a lui doi.

Care este diferența dintre & și &&?

& combină fiecare pereche de biți. && combină valori de adevăr și poate opri evaluarea după primul operand fals. Nu sunt interschimbabile.

De ce folosim unsigned pentru măști?

Tipurile fără semn oferă o reprezentare și reguli aritmetice mai potrivite manipulării biților. Tot trebuie respectate limitele deplasărilor și lățimea tipului.