std::bitset în C++: biți, măști și mulțimi

std::bitset reprezintă un număr fix de poziții binare și oferă operații pentru setarea, testarea și combinarea lor. Este util pentru mulțimi mici de stări, măști de proprietăți și calcule care procesează multe valori logice împreună.

Parametrul N este cunoscut la compilare. Un bitset nu este un vector de dimensiune aleasă liber la citire și nu trebuie confundat cu reprezentarea textuală a unui număr binar.

Cum funcționează

Poziția zero este bitul cel mai puțin semnificativ, afișat în dreapta. bitset<8>(5) are reprezentarea 00000101, deoarece 5=2^2+2^0. Afișarea arată toate cele opt poziții, inclusiv zerourile de la început. Dacă numărul inițial are biți dincolo de capacitate, reprezentarea păstrează numai pozițiile disponibile; programul limitează intrările la 0..255 pentru a evita o trunchiere neintenționată.

Operația set(i) pune unu, reset(i) pune zero, iar flip(i) inversează poziția. Fără argument, aceste operații afectează toate pozițiile. test(i) verifică un bit cu control al poziției și poate semnala o poziție invalidă; accesul prin operator[] cere respectarea limitelor. count numără biții unu, any verifică existența unuia, none verifică absența lor, iar all verifică dacă toate pozițiile sunt unu.

Dacă interpretăm bitul i drept apartenența lui i la o mulțime, operatorul & produce intersecția, | reuniunea și ^ diferența simetrică. Complementul ~ inversează toate cele N poziții, deci depinde de universul fix ales. Două măști care reprezintă universuri diferite nu pot fi comparate fără o convenție comună.

Deplasarea la stânga sau la dreapta mută pozițiile și introduce zerouri. Biții care ies din cele N poziții sunt pierduți. Aceste operații pe bitset au semantica tipului bibliotecii și nu trebuie confundate cu toate regulile deplasărilor pe întregi cu semn. Conversia prin to_ulong sau to_ullong este posibilă numai dacă valoarea încape în tipul rezultat; pentru un bitset mare, conversia poate eșua. Programul folosește N=8 și citește două numere, afișează operațiile de mulțimi, apoi modifică explicit trei poziții.

Exemplu urmărit pas cu pas

Pentru 5 și 3, reprezentările sunt 00000101 și 00000011. Intersecția este 00000001, reuniunea 00000111, iar diferența simetrică 00000110. Primul număr are doi biți setați.

După set(0), reset(7) și flip(1), prima mască devine 00000111. Prima operație nu schimbă nimic deoarece bitul zero era deja unu, a doua nu schimbă nimic deoarece bitul șapte era zero, iar ultima activează bitul unu. Urmărirea fiecărei poziții clarifică diferența dintre setare și inversare.

Implementare C++17

#include <bitset>
#include <iostream>
int main() {
    unsigned int x, y;
    std::cin >> x >> y;
    std::bitset<8> a(x), b(y);
    std::cout << a << '\n'
              << (a & b) << '\n'
              << (a | b) << '\n'
              << (a ^ b) << '\n'
              << a.count() << '\n';
    a.set(0);
    a.reset(7);
    a.flip(1);
    std::cout << a << '\n';
}

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

Operațiile se aplică independent fiecărei poziții. Pentru intersecție, rezultatul este unu exact când ambele mulțimi conțin elementul; pentru reuniune este suficientă una. Modificările punctuale păstrează toate celelalte poziții.

Memoria este proporțională cu N biți, cu organizarea internă a implementării. Operațiile asupra întregului bitset procesează grupuri de biți, dar nu trebuie numite universal O(1) dacă N crește în analiza problemei. Pentru N fix, precum opt în exemplu, costul este limitat de acea dimensiune.

Greșeli frecvente

Nu număra caracterele unu dintr-un text când ai deja count. Nu folosi un indice egal cu N. Nu presupune că ~ înseamnă complement față de toate numerele naturale: universul este numai 0..N-1. Nu confunda ^ cu ridicarea la putere.

Exersează

Pentru măștile 1010 și 1100 pe patru biți, calculează intersecția și reuniunea.

Rezolvare explicată: Intersecția este 1000, iar reuniunea 1110. Prima păstrează doar poziția comună, iar a doua toate pozițiile prezente în cel puțin una dintre măști.

Continuă să înveți

Operații pe biți, baze de numerație și vectori caracteristici.

Întrebări frecvente

Bitul zero este în stânga sau în dreapta la afișare?

În dreapta, fiind bitul cel mai puțin semnificativ. Indexarea logică și ordinea vizuală a cifrelor trebuie diferențiate.

Pot citi N de la tastatură pentru bitset?

Nu în această formă. N este un parametru stabilit la compilare. Pentru dimensiune dinamică trebuie aleasă altă reprezentare.

Ce numără count?

Numărul pozițiilor care conțin unu, nu valoarea numerică a măștii și nici lungimea textului afișat.

Ce diferență este între set și flip?

set face bitul unu indiferent de starea veche. flip îl inversează, deci două aplicări succesive revin la starea inițială.

Ce reprezintă XOR pentru mulțimi?

Diferența simetrică: elementele prezente în exact una dintre cele două mulțimi. Elementele comune sunt eliminate.