Operații pe biți

Intuiția

Orice număr întreg este, în memorie, un șir de biți: cifre binare de 0 și 1. Numărul 13 se scrie 1101 — patru întrerupătoare, dintre care trei aprinse. Operațiile pe biți nu lucrează cu valoarea numărului ca întreg, ci cu fiecare bit în parte, toți deodată.

Sunt cinci unelte. ȘI (AND) păstrează un bit doar dacă e aprins în ambele numere. SAU (OR) aprinde un bit dacă e aprins măcar într-unul. XOR aprinde bitul dacă e aprins în exact unul. NOT inversează fiecare bit. Iar shift-ul mută tot rândul de biți la stânga sau la dreapta. Din aceste cinci ies toate șabloanele utile.

Vezi cum funcționează

Algoritmul pas cu pas

Lucrăm pe 13 = 1101. Numerotăm biții de la dreapta la stânga, începând de la 0. Citește 1101 ca pe patru becuri:

Testez fiecare bit cu masca 1 deplasat la stânga cu poziția dorită:

• bitul 0: masca este 0001. 1101 ȘI 0001 = 0001 → bit aprins, valoare 1.
• bitul 1: masca este 0010. 1101 ȘI 0010 = 0000 → bit stins, valoare 0.
• bitul 2: masca este 0100. 1101 ȘI 0100 = 0100 → bit aprins, valoare 1.
• bitul 3: masca este 1000. 1101 ȘI 1000 = 1000 → bit aprins, valoare 1.

Observă bitul 1: e singurul stins. Hai să-l setăm (să-l aprindem), fără să atingem ceilalți biți. Folosim SAU cu masca 0010:

1101 SAU 0010 = 1111. Bitul 1 s-a aprins; ceilalți (SAU cu 0) au rămas neatinși:

Verificare: 1111 în zecimal este 8 + 4 + 2 + 1 = 15. Deci a seta bitul 1 al lui 13 dă 15 — exact ce trebuia.

Implementare C++

În cod folosim simbolurile: << pentru shift stânga, >> pentru shift dreapta, & pentru ȘI, | pentru SAU, ^ pentru XOR, ~ pentru NOT.

#include <iostream>
using namespace std;

// returneaza valoarea bitului k al lui n (0 sau 1)
int testeazaBit(int n, int k) {
    return (n & (1 << k)) != 0;   // mascam bitul k si vedem daca e aprins
}

// aprinde bitul k al lui n
int seteazaBit(int n, int k) {
    return n | (1 << k);          // SAU cu masca pune 1 pe pozitia k
}

// stinge bitul k al lui n
int stergeBit(int n, int k) {
    return n & ~(1 << k);         // SI cu masca inversata pune 0 pe pozitia k
}

// comuta bitul k al lui n (1 devine 0, 0 devine 1)
int comutaBit(int n, int k) {
    return n ^ (1 << k);          // XOR cu masca inverseaza fix bitul k
}

int main() {
    int n = 13;                   // 13 = binar 1101

    cout << testeazaBit(n, 0) << "\n";   // 1
    cout << testeazaBit(n, 1) << "\n";   // 0
    cout << testeazaBit(n, 2) << "\n";   // 1

    n = seteazaBit(n, 1);                // 1101 | 0010 = 1111
    cout << n << "\n";                   // 15

    cout << comutaBit(n, 1) << "\n";     // 1111 ^ 0010 = 1101 -> 13 din nou

    // paritate, inmultire si impartire cu putere a lui 2
    cout << (n & 1) << "\n";             // 1 -> 15 e impar
    cout << (n << 1) << "\n";            // 30 -> n inmultit cu 2
    cout << (n >> 1) << "\n";            // 7  -> n impartit la 2 (partea intreaga)
    return 0;
}

Ultimul bit, n & 1, este 0 când n e par și 1 când e impar — deci paritatea într-o singură operație. Un shift stânga cu o poziție înmulțește cu 2 (mută toți biții cu un loc mai sus), iar un shift dreapta împarte cu 2, păstrând partea întreagă.

Complexitate

Fiecare operație (ȘI, SAU, XOR, NOT, shift) lucrează pe toți biții numărului dintr-o singură instrucțiune hardware, indiferent cât de mare e numărul. Testarea, setarea sau ștergerea unui bit costă deci timp constant — niciodată o buclă.