De ce contează?
Imaginează un panou cu 8 becuri pe perete, fiecare cu propriul întrerupător:
unele aprinse, altele stinse. Vrei să poți aprinde becul 3, să stingi becul 5,
să vezi instant câte sunt aprinse — și, din când în când, să aprinzi toate
becurile pe care celălalt panou le are aprinse, dintr-o singură mișcare. Exact
asta îți oferă un bitset: un rând de comutatoare, compact și foarte rapid.
Ce este
Un bitset<N> este un șir de exact N biți, cu dimensiunea fixată la
compilare. Fiecare bit are două stări: 1 (pornit) sau 0 (oprit). Spre
deosebire de un bool[], unde fiecare element ocupă un octet întreg (8 biți),
bitset stochează literalmente câte un bit pe poziție — deci de circa 8 ori
mai puțină memorie.
Pe un singur bit poți face patru operații simple:
set(i)— pornește bitul de pe pozițiai(îl pune pe1);reset(i)— îl stinge (îl pune pe0);flip(i)— îl inversează (0devine1,1devine0);test(i)— citește valoarea bitului (truedacă e1).
În plus, count() îți spune câți biți sunt 1, iar pe toți biții deodată
poți aplica operatori logici între două bitset-uri: & (and), | (or),
^ (xor) și deplasări <<, >>.
Cheia eficienței: procesorul nu prelucrează biții unul câte unul, ci pe blocuri
de 64 de biți (un cuvânt). Un and între două bitset-uri de N biți costă deci
O(N/64), nu O(N) — de circa 64 de ori mai rapid decât dacă ai parcurge un
bool[] cu un for. De aceea bitset accelerează un ciur sau un DP cu măști.