Operații pe biți

De ce contează?

Un panou cu becuri: fiecare bec e aprins (1) sau stins (0). Poți combina două panouri după reguli simple — „aprins doar unde ambele sunt aprinse", „aprins unde măcar unul e". Operațiile pe biți sunt exact aceste reguli aplicate becurilor unui număr.

Cei patru operatori + deplasările

Operatorii pe biți lucrează pe fiecare bit, independent:

Operator	Nume	Regulă
`&`	AND	1 doar dacă ambii biți sunt 1
`\|`	OR	1 dacă măcar unul e 1
`^`	XOR	1 dacă biții diferă
`~`	NOT	inversează fiecare bit
`<<`	shift stânga	`n << k` = n · 2ᵏ
`>>`	shift dreapta	`n >> k` = n / 2ᵏ

Pe un exemplu: 12 și 10

12 = 1100, 10 = 1010. Aliniem biții și aplicăm operația pe coloane:

12 = 1100 în binar (8 + 4).

10 = 1010 în binar (8 + 2). Aplici operația coloană cu coloană față de 12 de mai sus.

Operație	rezultat binar	zecimal
`12 & 10`	1000	8
`12 \| 10`	1110	14
`12 ^ 10`	0110	6

Trucuri folosite des

#include <iostream>
using namespace std;

int main() {
    int n = 13;                  // 1101 in binar
    cout << (n & 1) << "\n";     // 1 -> n e impar (ultimul bit)
    cout << (n >> 1) << "\n";    // 6 -> imparte la 2
    cout << (n << 1) << "\n";    // 26 -> inmulteste cu 2
    cout << (1 << 4) << "\n";    // 16 -> 2^4
    return 0;
}

Observația-cheie

n & 1 izolează ultimul bit → testul de paritate. n >> 1 taie ultimul bit (împărțire la 2). 1 << k construiește puterea 2ᵏ — esențial la măștile de biți (lecția-punte).

Atenție la prioritate

Operatorii pe biți au prioritate mai mică decât comparațiile. Asta surprinde:

if (n & 1 == 0)        // GRESIT: se evalueaza ca n & (1 == 0) = n & 0 = 0
if ((n & 1) == 0)      // CORECT: pune paranteze

Complexitate

Operație	Timp	Spațiu
`&`, `\|`, `^`, `~`, `<<`, `>>`	O(1)	O(1)

Toate sunt instrucțiuni unice de procesor — extrem de rapide. De aceea trucurile pe biți înlocuiesc des operații aritmetice mai lente (% 2, / 2, * 2).

Greșeli frecvente

Capcane reale la operațiile pe biți:

Prioritatea: n & 1 == 0 se citește n & (1 == 0). Pune mereu paranteze: (n & 1) == 0.
Shift prea mare: 1 << 31 pe int cu semn dă overflow. Pentru biți înalți folosește 1LL << k (long long).
Confuzi & cu && (sau | cu ||): & e pe biți, && e logic. 2 & 1 = 0, dar 2 && 1 = 1 (true). Sensuri complet diferite.
XOR pentru schimb fără temp: a ^= b; b ^= a; a ^= b; funcționează, dar e fragil dacă a și b sunt aceeași variabilă; preferă swap.

De reținut

& (ambii 1), \| (măcar unul), ^ (diferă), ~ (inversează), <</>> (·2ᵏ / :2ᵏ).
n & 1 = paritate; 1 << k = 2ᵏ; toate O(1), mai rapide decât aritmetica echivalentă.
Operatorii pe biți au prioritate mică → pune paranteze la comparații.