Operatii pe biti

Operaţii pe biţi

h1. Operatii pe biti

h1. Operaţii pe biţi

== include(page="template/implica-te/scrie-articole" user_id="GheorgheMihai") ==

(Categoria _Algoritmi_, Autor _Cosmin Negruşeri_)

(Categoria _Algoritmi_, Autor _Cosmin Negruşeri_)
 
În cadrul acestui articol vã vom prezenta câteva metode prin care programele se pot optimiza dacã utilizãm eficient operaþiile pe biþi sau folosim operaþii pe biþi în locuri în care, la prima vedere, nu s-ar pãrea cã ar fi necesare.
 
De cele mai multe ori, atât în concursuri cât şi în viaþa de zi cu zi a programatorului, atunci când implementãm o metodã care este folositã de o aplicaþie şi vrem sã facem aceastã metodã eficientã ca timp de execuþie, suntem învãþaþi din şcoalã (sau ar trebui sã fim învãþaþi, chiar dacã unii dintre profesori considerã cã cel mai important algoritm învãþat în liceu este _backtraking_-ul, soluþia tuturor problemelor) sã ne uitãm la complexitatea algoritmului implementat şi dacã observãm cã în practicã algoritmul este mai încet decât ne dorim noi sã fie sã încercãm sã gãsim un algoritm cu un ordin de complexitate mai mic.
 
Nu trebuie sã uitãm cã ceea ce numim complexitatea unui algoritm este o aproximare a vitezei unui algoritm şi nu o mãsurã absolutã. Pentru dimensiuni mici ale datelor, câteodatã nu se observã diferenþa dintre $O(n)$ şi $O(n · log n)$ sau $O(n^3/2^)$. Mie personal mi s-a întâmplat ca la implementarea soluþiei unei probleme care în englezã se numeote "_Bottleneck Minimal Spanning Tree_" sã observ cã rezolvarea în $O(m · log m)$ (folosind algoritmul de gãsire a arborelui parþial de cost minim al lui Kruskal) sã fie mai rapidã decât rezolvarea mai laborioasã în $O(m)$ a acestei probleme. Deci trebuie datã o atenþie egalã cu cea acordatã complexitãþii algoritmului şi dimensiunii factorilor constanþi care apar.
 
În continuare vom încerca sã gãsim soluþii mai rapide decât cele naive pentru unele operaþii de bazã (toate operaþiile vor fi implementate pentru întregi pozitivi reprezentaþi pe 32 de biþi).