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

Aplicaţia #1

Să se determine numărul de biţi de 1 din reprezentarea binară a lui n.

Rezolvare

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₂
n - 1  = 11011101001111₂
n & (n - 1) = 11011101000000₂

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²⁴ ş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ă.

Aplicaţia #2

Să se determine paritatea numărului de biţi de 1 din reprezentarea binară a unui număr n.

Rezolvare

int parity(long n){
  int num = 0;
  for (int i = 0; i < 32; i++)
     if (n & (1 << i)) num ^= 1;
  return num;
}

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

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.

Aplicaţia #3

Să se determine cel mai puţin semnificativ bit de 1 din reprezentarea binară a lui n.

Rezolvare

int low1(long n){
   return n ^ (n & (n - 1));
}

Exemplu:
n  = 11011000₂
n-1  = 11010111₂
n & (n - 1)  = 11010000₂
n  = 11011000₂
n ^ (n & (n - 1)) = 00001000₂

Această funcţie este foarte importantă pentru structura de date Arbori Indexaţi Binar prezentată într-un un articol mai vechi din GInfo.

Aplicaţia #4

Să se determine cel mai semnificativ bit cu valoarea 1 din reprezentarea binară a lui n.

Rezolvare

int high1(long n) {
   long num = 0;
   if (!n) return -1;
   if (0xFFFF0000 & n) {
     n = (0xFFFF0000 & n)>>16;
     num += 16;
   }
   if (0xFF00 & n) {
      n = (0xFF00 & n) >> 8;
      num += 8;
   }
   if (0xF0 & n) {
      n = (0xF0 & n) >> 4;
      num += 4;
   }
   if (12 & n) {
      n = (12 & n) >> 2;
      num += 2;
   }
   if (2 & n) {
      n = (2 & n) >> 1;
      num += 1;
   }
   return 1 << num;
}