De ce contează?
Imaginează-ți un rând de becuri pe perete, numerotate de la 0. Fiecare bec are un singur întrerupător: aprins sau stins. Privind tot rândul deodată citești instant ce e prezent și ce lipsește — nu verifici fiecare bec pe rând. Acum surpriza: un singur număr întreg ține tot rândul. Fiecare bit al lui e un bec, iar a aprinde sau stinge un bec devine o singură operație pe acel număr.
Ideea-cheie
Un int nu e doar „un număr". În memorie el e o secvență de 32 de biți, fiecare
0 sau 1. Putem reinterpreta acești biți ca pe răspunsuri da/nu: bitul de pe
poziția k ne spune dacă elementul k este prezent (1) sau absent (0).
Astfel un singur întreg devine o mulțime de până la ~32 de elemente. În loc
să ții un bool prezent[32], ții un singur număr și lucrezi pe biții lui. Asta
se numește mască de biți (engl. bitmask).
Exemplu: masca scrisă în binar 1011 (care valorează 11 în baza 10) înseamnă
pozitie: 3 2 1 0
bit: 1 0 1 1Citim de la dreapta: bitul 0 = 1 (prezent), bitul 1 = 1 (prezent), bitul 2 = 0
(absent), bitul 3 = 1 (prezent). Deci masca 1011 reprezintă mulțimea
{0, 1, 3}. Un singur număr a codat patru răspunsuri.
Schimbarea de perspectivă: nu mai citești un int ca pe o valoare numerică, ci
ca pe o mulțime. Fiecare bit k este un flag — 1 înseamnă „elementul k este
în mulțime", 0 înseamnă „nu este". Citești biții de la dreapta (poziția 0) spre
stânga. Un singur număr ține astfel apartenența a până la 32 de elemente deodată.