Operaţii pe biţi

Acest articol a fost adăugat de Mihai Gheorghe •GheorgheMihai Intră aici dacă doreşti să scrii articole sau află cum te poţi implica în celelalte proiecte infoarena!

(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).