Container-ul bitset (STL)

Urmatorul articol prezinta avantajele folosirii container-ului bitset din STL (Standard Template Library) si cateva elemente specifice acestuira. Mentionez de la inceput ca pentru o intelegere completa sunt necesare cunostintele de baza in ceea ce priveste STL.

• Ce este bitset ?

Bitset este un container special creat pentru a retine biti (0 sau 1, true sau fals). Seamana cu un array obisnuit, insa diferentele sunt vadite cand vine vorba despre alocarea memoriei : fiecare element „consuma” exact un bit, ceea ce este de opt ori mai putin decat cel mai mic tip al limbajului C++, char).

Fiecare element poate fi accesat prin pozitia sa. De exemplu avem :

1000010

unde primul bit (bits[0]) are valoarea 0, al doilea are valoarea 1, al treilea valoarea 0 si tot asa. Observam ca bitii sunt numerotati de la 0 incepand din dreapta.

• Cum declaram si citim un container de tip bitset ?

Pentru a declara un container de tip bitset trebuie sa includem in lista de preprocesare elementul :

#include <bitset>

insotit de

using namespace std;

Declarare propriu-zisa se face astfel :

bitset <8> bits;

Ceea ce inseamna ca am declarat un container numit bits, de 8 elemente (fiecare ocupand cate un bit) de tip bitset.

Citirea se realizeaza astfel :

cout << "Introduceti elementele : ";    /* facultativ */cin >> bits;

Putem defini elementele containerului si astfel :

bitset <4> first (string("1001"));      /* putem declara un bitset si ca string */

• Cum afisam elementele unui bitset ?

Afisam elementele containerului folosindu-ne de variabile.

void afisare (){int i;for (i=0; i<n; ++i)           /* n este numarul de elemente din container */cout << bits[i] << " ";}

Sa vedem acum cateva functii care ne ajuta sa lucram cu bitset :

• Size ()

Size returneaza dimensiunea (numarul de elemente din container).

bitset <8> bits;
cout << "In bits avem " << bits.size () << "elemente.\n";

• Count ()

Functia .count  () numara cate elemente cu valoara 1 se gasesc in container. Daca vrem sa aflam atat numarul de elemente cu valoarea 1, cat si numarul de elemente cu valoarea 0 din container, putem scadea valoare returnata de .count  () din dimensiunea containerului (dimensiunea exacta se poate afla folosind.size () ).

bitset <5> bits (string("11010"));
printf ("Bits contine %d elemente 1 si %d elemente 0\n", bits.count (), bits.size () - bits.count () );

• None ()

Verifica daca toti bitii sunt diferiti de 1 (adica sunt 0). Va returna o valoare pozitiva (1) daca in container toate elementele au valoarea 0 si o valoare egala cu 0 daca avem cel putin un element cu valoarea 1.

bitset <5> bits;
if (bits.none ())
        printf ("In bits toate elementele sunt 0\n");
else
         printf ("In bits avem cel putin un element cu valorea 1\n");

• Any ()

Verfica daca exista vreun element cu valoarea 1 in container. Va returna valoarea 0 daca nu avem niciun element cu valoarea 1 si 1 invers.

bitset <5> bitset;
if (!bits.any ())
     printf ("Nu avem niciun element cu valoarea 1\n");
else
     printf ("Avem cel putin un element cu valoarea 1\n");

• Set  ()

Set () fara paramentru transforma toate elementele in 1. Parametrii pe care ii putem specifica sunt :

set (x, y) unde x reprezinta pozitia bitului care va lua valoara y

set (x) unde x reprezinta pozitia care va lua valoarea 1

Exemplu :

bitset <4> bits;bits.set ();    /* 1111 */
bits.set (1, 0);   /*1101 */
bits.set (0, 0);  /* 1100 */
bits.set (1);     /* 1110 */

• Reset ()

Reset () transforma toate elementele in 0.

bitset <4> bits;
bits.set ();     /* 1111 */
bits.reset ();  /* 0000 */

• Flip  ()

Flip () transforma toti bitii de 0 in 1 si invers.

bitset <5> bits (string("10011"));
bits.flip ();    /* 01100 */

• Test ()

Test () verifica daca un anumit bit este 0 sau 1.

bitset <5> bits (string("01011"));
cout << "Containerul contine :\n";
cout << boolalpha;
for (size_t i=0;  i<bits.size();  ++i)
        cout << bits.test (i)  << "\n";Programul va afisa :

Containerul contine :

true

true

false

true

false

• To_string ()

Transforma un container bitset intr-un string.

string sir;
bitset<4> bits;      /*  0000 */bits.set();            /* 1111 */sir = bits.to_string<char,char_traits<char>,allocator<char> > ();cout << "sir : " << sir << "\n";

• To_ulong ()

O functie foarte folositoare (my favourite 🙂 ) este to_ulong () care transforma containerul in numar in baza 10.

bitset <4> bits;
cin >> bits;
cout <<  bits << "  in baza 10 este <<   bits.to_ulong () << "\n";

• Incheiere

Pentru a intelege mai bine cele prezentate mai sus, va sfatuiesc sa implementati chiar voi functiile si sa experimentati cat mai mult. De asemenea, cateva probleme care cer si putina algoritmica s-ar putea rezolva folosind o structura de tip bitset :

• Paritate  (infoarena.ro)
• Aritma (.campion)
• Viteza (.campion)

O sursa comentata cu toate aceste functii aplicate poate fi consultata mai jos 🙂 :

lorem ipsum /* Program compilat cu Code :: Blocks
Autor : Albulescu Cosmina (miculprogramator)
*/
#include <stdio.h>
#include <bitset>
#include <iostream>
using namespace std;

bitset <5> mybit;      /* mybit este gol si are 20 de elemente */
bitset <4> first (string("1001"));      /* putem declara un bitset si ca string, e mai useful */
bitset <4> second (string("1000"));
bitset <4> test;

int main ()
{
 printf ("Bitset este un container care retine in fiecare element o valoare 0 sau 1 (1 bit). Fiecare element din bitset ocupa fix 1 bit.\n");
 printf ("Putem face referire la elementele din bitset cu ajutorul pozitiilor (ca la vector), spre exemplu mybitset[3] este al 3-lea element din mybitset\n\n");

 printf ("Cateva operatii intre 2 containere bitset : \n\n");
 cout << first << " & "<< second << " = " << (first & second) << "\n";
 cout << first << " ^ " << second << " = " << (first ^ second) << "\n";
 cout << first << " | " << second << " = " << (first | second) << "\n";

 printf ("Introduceti un nr in binar (de 5 cifre): ");
 cin >> mybit;                       /* mybit.count () numara valorile de 1 din container */
 printf ("mybit are %d de 1 si %d de 0\n\n", int (mybit.count()), int(mybit.size() - mybit.count()));       /* mybit.size() reprezinta marimea containerului , 5 in acest caz */

 cout << "Vom transforma toate valorile de 1 in 0 si toate valorile 0 in 1, din nr cu ajutorul .flip() " << first << "\n";
 first.flip ();      /* cand aplicam .flip() fara paramentru actioneaza asupra intregului container */
 cout << "Noul container arata asa : " <<  first << "\n";    /* cand aplicam .flip (x) schimba primele x valori */

 if (first.none())           /* .none() este 1 cand nu avem niciun bit 1 si 0 cand avem */
 printf ("first nu are niciun bit 1\n\n");
 else
 printf ("first are %d biti 1\n\n", int(first.count()));

 test[1] = 1;
 cout << test << "\n"; /* 0010 */
 test[2] = 1;
 cout << test << "\n";  /* 0110 */
 test.reset ();      /* Transformam toti bitii in 0 */
 cout << test << "\n";   /* 0000 */
 test.set ();    /* cand folosim .set() fara parametrii bitiii se transforma in 1 */
 cout << test << "\n";   /* 1111 */
 test.set (1, 0); /* transformam primul bit in 1; .set(x, y) transforma bitul x in y */
 cout << test << "\n";   /* 1101 */
 test.set (1);      /* transformam inapoi bitul 1 in 1. .set (x) transforma bitul x in 1 pt ca nu am dat parametru y */
 cout << test << "\n"; /* 1111*/

 test.reset();
 printf ("Introduceti un nr in bianr (4 cifre) : ");
 cin >> test;
 cout << test << " in baza 10 este : " << test.to_ulong();   /* .to_ulong() transforma bitset-ul in nr natural ! DE TINUT MINTE !! */

 printf ("\n\nBitset : done, sunt multe lucruri useful aici !\n\n");

 return 0;
}