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

Î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ţă 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 numeşte "_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).
 
h2. Aplicaţia #1
 
bq. Să se determine numărul de biţi de 1 din reprezentarea binară a lui $n$.
 
h3. Rezolvare
 
Rezolvarea naivă a acestei probleme ar consta în parcurgerea secvenţială a biţilor lui n. În continuare vă prezint această rezolvare:
==code(cpp)|
int count(long n){
  int num = 0;
  for (int i = 0; i < 32; i++)
     if (n & (1 << i)) num++;
  return num;
}
==
 
Dacă ne uităm cu atenţie şi analizăm rezultatul operaţiei $n & (n - 1)$ putem obţine o soluţie mai bună. Să luăm un exemplu:
$n           = 11011101010000{~2~}$
$n - 1       = 11011101001111{~2~}$
$n & (n - 1) = 11011101000000{~2~}$
 
Se vede clar de aici că efectul operaţiei $n & (n - 1)$ este anularea celui mai nesemnificativ bit cu valoarea 1.
De aici ideea algoritmului:
==code(cpp)|
int count(long n){
   int num = 0;
   if (n)
      while (n &= n - 1) num++;
   return num;
}
==
 
Dar este acest algoritm mai rapid? Am testat pentru toate numerele de la $1$ la $2^24^$ şi rezultatele au fost $2,654$ secunde folosind metoda naivă şi $0.821$ folosind a doua metodă.
Rezultatul mult mai bun al celei de-a doua metode se bazează în principal pe faptul că ea execută un număr de paşi egali cu numărul de biţi cu valoarea 1 din număr, deci în medie jumătate din numărul de paşi efectuaţi de prima metodă.
 
h2. Aplicaţia #2
 
bq. Să se determine paritatea numărului de biţi de 1 din reprezentarea binară a unui număr $n$.
 
h3. Rezolvare
 
Din cele prezentate mai sus se pot determina două metode evidente:
==code(cpp)|
int parity(long n){
  int num = 0;
  for (int i = 0; i < 32; i++)
     if (n & (1 << i)) num ^= 1;
  return num;
}
==
 
==code(cpp)|
int parity(long n){
   int num = 0;
   if (n)
      while (n &= n - 1) num ^= 1;
   return num;
}
==
 
Putem obţine o a treia rezolvare făcând câteva observaţii pe un exemplu:
Considerăm $n = 11011011{~2~}$. Rezultatul căutat este dat de valoarea @1 ^ 1 ^ 0 ^ 1 ^ 1 ^ 0 ^ 1 ^ 1@.
Împărţim pe n în partea lui superioară şi partea lui inferioară:
1 1 0 1 ^ 1 0 1 1 = 0 1 1 0
Aplicăm asupra rezultatului acelaşi procedeu:
0 1 ^ 1 0 = 1 1
şi
1 ^ 1 = 0
 
Să scriem algoritmul care reiese din acest exemplu, luând în considerare faptul că numărul n este reprezentat pe 32 de biţi:
==code(cpp)|
int parity(long n){
   n = ((0xFFFF0000 & n) >> 16) ^ (n & 0xFFFF);
   n = ((0xFF00 & n) >> 8) ^ (n & 0xFF);
   n = ((0xF0 & n) >> 4) ^ (n & 0xF);
   n = ((12 & n) >> 2) ^ (n & 3);
   n = ((2 & n) >> 1) ^ (n & 1);
   return n;
}
==
 
Deşi constanta multiplicativa este mai mare, numărul de operaţii are ordin logaritmic faţă de numărul de biţi ai unui cuvânt al calculatorului.

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