Etichete : array de biti, biti, bitset, C++, containere STL, Olimpiada, operatii pe biti, 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;
}

Recomandam, pe aceeasi tema

Despre autorul articolului :

Albulescu Cosmina - Autorul a scris 223 articole (vezi lista completa).

Contact | @worldIT

Numele meu este Cosmina, iar pe Internet sunt cunoscuta ca "miculprogramator" sau "Coss". Sunt pasionata de informatica, iar ceea ce ma intereseaza cel mai mult este programarea, algoritmica. Perfectiune se numeste ceea ce caut eu si in fiecare zi : caut sa ma autodepasesc. Consider ca ideile tale pot ajuta WorldIT sa se dezvolte, sper sa ni te alaturi !