• Acasă
  • Despre noi
  • Autori
  • Mărturii
  • Arhivă
  • Trimite Articol
  • Contact

WORLDIT

Lumea în 1 și 0.

  • Știri
    • Tehnologie
    • Tehnologie mobilă
    • Securitate
    • Developers
    • Știință
    • Benzi desenate
    • Jocuri
    • Intern
  • Tehnic
    • Browser
    • C#
    • C/C++
    • Challenge
    • HTML/CSS
    • Javascript, Ajax, jQuery
    • Open Source
    • PHP
    • Python
    • Securitate IT
    • Socializare
    • WordPress
    • Altele
  • Recenzii
  • Interviuri
  • Evenimente

Tips & Tricks – Operatii pe Biti

3
  • Publicat de Andrei Avădănei
  • în C/C++
  • — 25 iul., 2009 at 1:28 pm

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.

Etichete: binarbitioperatii pe bititips and tricks

— Andrei Avădănei a scris 1246 articole

Andrei scrie pe worldit.info din vara lui 2011. Este fondatorul Asociatiei Centrul de Cercetare in Securitate Informatica din Romania - CCSIR si coordoneaza DefCamp, cea mai importanta conferinta de securitate informatica & hacking din Europa Centrala si de Est. Andrei ofera in cadrul Bit Sentinel servicii de securitate informatica, penetration testing, security management, recuperarea de pe urma unui atac cibernetic, training-uri si workshop-uri.

  • Articolul anterior Orb, casca Bluetooth care se poarta pe deget
  • Articolul următor Easy video camera

3 Comentarii

  1. Andonie Andrei spune:
    august 29, 2009 la 10:37 pm

    Bun, bun acest articol, l-am scos la imprimanta deoarece sunt sigur ca o sa imi fie de folos. Merci…

  2. Andrei Misarca spune:
    august 30, 2009 la 10:24 am

    Cum inmultirea si impartirea cu puteri ale lui 2 se poate face foarte rapid pe biti, ar fi fost nedrept ca modulo sa ramana pe dinafara. Asadar, x % 2^k x & (2^k – 1). Mai pe scurt x % 8 din prezentarea de mai sus este echivalent cu x & 7. Explicatia e simpla. Cand faci & cu k biti de 1, isi vor pastra valoarea doar ultimii k biti din numar, adica exact restul impartirii la 2^k 🙂

  3. Andrei Lita spune:
    octombrie 29, 2011 la 6:36 pm

    buna observatie @ Andrei Misarca , dar linia de cod 20 din varianta corecta este gresit , corect era ” if((a[i >> 3] & (1<<(i%8))) == 1<<(i%8)) " deoarece numarul 1 este 1<<0 dar ceea ce doresti este sa afli daca acel 1 pus la acea pozitie nu sa transformat in 0 .


  • Facebook

    WorldIT.info
  • Ultimele Atacuri Cibernetice din Romania – RO Hacked

    [wp_rss_retriever url="https://rohacked.bit-sentinel.com/feed/" excerpt="none" items="5" read_more="false" new_window="true" thumbnail="false" cache="0"] RO Hacked este registrul atacurilor cibernetice din România.
  • Caută

  • Articole Recomandate

    • Recent Posts
    • Tags
    • Număr record de participanți la DefCamp 2015, cel mai important eveniment dedicat securității cibernetice din Europe Centrala si de Estdecembrie 2, 2015
    • La DefCamp 2015 vei afla prin ce tehnici pot fi evitate măsurile de securitate ale sistemelor informatice criticeoctombrie 16, 2015
    • Ultima sansa sa rezervi bilete de tip Early Bird la DefCamp 2015septembrie 1, 2015
    • 15 sfaturi despre cum poti deveni un programator bun venite de la specialisti romaniaugust 4, 2015
    • algoritmica Android antivirus Apple Avadanei Andrei benzi desenate BitDefender blog browser C++ Chrome concurs eveniment Facebook Firefox Google google chrome hacking html5 infografic informatica internet Internet Explorer IT javascript linux Microsoft Mozilla Firefox online PHP programare retea sociala review Romania securitate Tehnologie Twitter web Windows Windows 7 Wordpress WorldIT worldit.info Yahoo! YouTube
  • februarie 2023
    L Ma Mi J V S D
     12345
    6789101112
    13141516171819
    20212223242526
    2728  
    « dec.    
  • Link-uri Sponsorizate

    • laptop second hand

    • Calculatoare Second Hand

    • cod voucher pc garage

  • Home
  • Tehnic
  • C/C++
  • Tips & Tricks – Operatii pe Biti
  • Important

    • Bit Sentinel
    • Centrul de Cercetare în Securitate Informatică din România
    • DefCamp
  • Prieteni

    • BetiT.ro
    • bijuterii handmade
    • Computerica | Resurse gratuite PC
    • Descopera.org
    • Gadgeturi si IT – Giz.ro
  • Prieteni

    • PC – Config
    • RO Hacked
    • Stiri IT

Copyright © 2009-2014 WORLDIT. Toate drepturile Rezervate.
Termeni și condiții | Contact | Licența Creative Commons