Tips & Tricks – Operatii pe Biti

Operatiile pe biti sunt o tehnica foarte utilizata si raspandita in special in domeniul optimizarii vitezei si al memoriei.In urmatoarele randuri voi prezenta operatiile de baza pe biti precum si cateva tips & tricks cu acestea.

Operatorii logici pe biti sunt analogi cu operatorii logici normali, exceptand faptul ca se aplica unei valori bit cu bit si nu ca unui tot unitar. De exemplu, sa luam operatorul de negare normal (!) si cel de negare pe biti (~). Operatorul ! converteste o valoare true (sau diferita de zero) in false iar o valoare false in una true. Operatorul ~ converteste fiecare bit in parte in opusul sau (1 in 0 si 0 in 1).

1. Operatorul SI pe biti (&)

Operatorul SI pe biti (&) combina doua valori intregi pentru a obtine o valoare intreaga noua. Fiecare bit din noua valoare este 1 numai daca amandoi bitii corespunzatori din valorile initiale sunt 1. Daca oricare sau amandoi bitii corespunzatori sunt 0, atunci bitul rezultat este setat tot la 0.

Exemplu :

a      = 1 0 0 0 0 1 1 1
b      = 0 1 1 0 0 1 0 0
a & b  = 0 0 0 0 0 1 0 0

2. Operatorul SAU pe biti (|)

Operatorul SAU pe biti (|) combina doua valori intregi pentru a obtine o valoare intreaga noua. Fiecare bit din noua valoare este 1 daca unul sau altul, sau amandoi, bitii corespunzatori din valorile initiale este 1. Daca amandoi bitii corespunzatori sunt 0, atunci bitul rezultat este setat tot la 0.
Exemplu :

a      = 1 0 0 0 0 1 1 1
b      = 0 1 1 0 0 1 0 0
a | b  = 1 1 1 0 0 1 1 1

3. Operatorul SAU exclusiv pe biti ( ^ )

Operatorul SAU exclusiv pe biti (^) combina doua valori intregi pentru a obtine o valoare intreaga noua. Fiecare bit din noua valoare este 1 daca unul sau altul, dar nu amandoi, bitii corespunzatori din valorile initiale este 1. Daca amandoi bitii corespunzatori sunt 0, sau amandoi sunt 1 atunci bitul rezultat este setat la 0.
Exemplu :

a      = 1 0 0 0 0 1 1 1
b      = 0 1 1 0 0 1 0 0
a | b  = 1 1 1 0 0 0 1 1

4. Operatorul de negare pe biti ( ~ )

Operatorul de negare pe biti ( ~ ) combina o valoare pentru a obtine o valoare intreaga noua.Fiecare bit din noua valoare este 1 daca bitii corespunzatori valorii initiale sunt 0 si.Cand bitii din valoarea initiala sunt 1 atunci noua valoare devine 0.
Exemplu :

a      = 1 0 0 0 0 1 1 1
~a      = 0 1 1 1 1 0 0 0

5. Operatorul de deplasare spre stanga ( << )

Operatorul de deplasare spre stanga ( << ) deplaseaza toti bitii din valoarea initiala cu n pozitii spre stanga si completeaza pozitiile cu zerouri.
a<<n deplaseaza bitii din a cu n pozitii spre stanga

Deoarece fiecare pozitie a unui bit reprezinta o valoare de doua ori mai mare decat a bitului din dreapta sa , deplasarea cu o pozitie la stanga este echivalenta cu inmultirea valorii cu 2. Analog, deplasarea cu 3 pozitii este echivalenta cu inmultirea cu 2^3, iar deplasarea cu n pozitii este echivalenta cu inmultirea cu 2^n.

6. Operatorul de deplasare spre dreapta ( >> )

Operatorul de deplasare spre dreapta (>>) deplaseaza toti bitii din valoarea initiala cu n pozitii spre dreapta si completeaza pozitiile cu zerouri.

Deplasarea cu o pozitie la dreapta este echivalenta cu o impartire intreaga la 2. In general, deplasarea cu n pozitii la dreapta este echivalenta cu o impartire intreaga la 2^n.

7. Cateva tehnici pentru manipularea bitilor

Este de mentionat ca numerotarea bitilor incepe de la dreapta spre stanga cu valoarea 1.Astfel bitul n va fi al n-lea bit al valorii respective de la dreapta spre stanga.

1.Setarea unui bit la valoarea 1
Expresia a|b te va ajuta sa setezi valorile bitilor noii valori.Daca la oricare pozitie exista in b sau in a un 1,noua valoare va avea pe pozitia respectiva 1.
Spre exemplu,daca vrem sa setam prima pozitia a bitilor cu 1, vom avea o operatie de genul : a|1
Alte exemple:

a | 1 (seteaza pozitia 1 a bitilor in 1)
a | 2 (seteaza pozitia 2 a bitilor in 1)
a | 4 (seteaza pozitia 3 a bitilor in 1)
a | 8 (seteaza pozitia 4 a bitilor in 1)
a | 16 (seteaza pozitia 5 a bitilor in 1)

Observam ca pentru a seta al n-lea bit trebuie sa facem operatia SAU pe biti cu 2^(n-1).

2.Comutarea bitilor
Expresia a^b realizeaza inversarea bitilor.Pe pozitia unde bitul are valoarea 1 noua valoare va fi 1 si invers.
a ^ 1 (inverseaza bitul de pe pozitia 1)
s.a.m.d

3.Testarea valorii unui bit
Operatia a == 1 este total gresita.Pentru a testa daca bitul de pozitia n este 1 sau 0 trebuie sa facem o operatie SI pe biti(&) cu valoarea 2^(n-1).
Spre exemplu :
(a & 1) este adevarata doar daca valoarea de pe pozitia 1 este 1.
….
(a & 8) este adevarata doar daca valoarea de pozitia 4 este 1.
s.a.m.d.

Aici voi prezenta o mica modalitate de economisire a memoriei.Spre exemplu avem o problema in care trebuie sa stim daca numerele din intervalul [1,n], n <= 1.000.000.000 sunt necesare pentru a face solutia finala.
Ne imaginam urmatorul scenariu : Nu ne-a venit in minte ideea de a calcula la fiecare pas daca valoarea este necesara si a face calcule in continuare pe ecuatie ci ne-am gandit sa facem un vector si sa punem 1 daca valoarea este necesara si 0 in caz contrar.Imediat observam ca vectorul ar fi prea mare pentru asa ceva si riscam sa pierdem la capitolul memorie.Ideea este urmatoarea : vom face un vector de caractere de 8 ori mai mic( char este pe 8 biti) si vom seta fiecare bit din cele n/8 valori cu 1 daca valoarea este necesara si 0 in caz contrar.

Nu voi prezenta o solutie completa pentru ca nu este problema completa ci doar principiul pe care se bazeaza.

Varianta gresita :

#include <iostream>
using namespace std;

#define MAX_N 1000000000
int n,a[MAX_N];
int verificaVal(int);

int main()
{
   int i,x;
   cin>>n;
   for(i = 0; i < n; i++)
   {
      cin>>x;
      a[i] = verificaVal(x);
   }
   for(i = 0; i < n; i++)
   {
      if(a[i] == 1)
      .....................................
   }
   return 0;
}

int verificaVal(int valToVer)
{
  /* aici vom avea o functie care verifica daca valoarea este necesara pentru expresie
   * in cazul in care este necesara returneaza 1
   * si 0 in caz contrar
   */ 

}

Varianta corecta :

#include<iostream>
using namespace std;

#define MAX_N 1000000000/8
int n;
char a[MAX_N];
int verificaVal(int);

int main()
{
   int x;
   cin>>n;
   for(int i = 0; i < n; i++)
   {
      cin>>x;
      a[i >> 3] |= (verificaVal(x)<<(i%8));
   }
   for(i = 0; i < n; i++)
   {
      if((a[i >> 3] & (1<<(i%8))) == 1)
     {
         .....................................
     }
   return 0;
}

int verificaVal(int valToVer)
{
  /* aici vom avea o functie care verifica daca valoarea este necesara pentru expresie
   * in cazul in care este necesara returneaza 1
   * si 0 in caz contrar
   */ 

}

Explicatie :

• i>>3 este echivalent cu i / 8 ne va ajuta sa aflam pe care char din sirul de char-uri se afla valoarea i
• i % 8 ne ajuta sa aflam pe ce bit al charului se afla valoarea i
• a[i >> 3] |= (verificaVal(x)<<(i%8)); seteaza al i % 8-lea bit din al i/8-lea char in valoarea returnata de functia verificaVal()

Tema : Incercati sa rezolvati Ciurul lui Eratostene printr-o metoda asemanatoare.
Tool : Doresti sa faci excertitii pe baza de observatii,atunci ai nevoie de un Convertor din zecimal in binar.

Articolul nu este terminat,daca doriti sa-l completati contactati-ma aici.