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;
}

Aplicaţia #5

Să se determine indexul celui mai semnificativ bit de 1 din reprezentarea binară a lui n.

h3. Rezolvare

Metodele prezentate la rezolvarea problemei 4 pot fi folosite şi aici, dar vom prezenta o nouă rezolvare. Să luăm următorul şir de operaţii pentru un exemplu:

n = 10000000₂
n = n | (n >> 1)
n = 11000000₂
n = n | (n >> 2)
n = 11110000₂
n = n | (n >> 4)
n = 11111111₂

int indexHigh1(long n){
  n = n | (n >> 1);
  n = n | (n >> 2);
  n = n | (n >> 4);
  n = n | (n >> 8);
  n = n | (n >> 16);
  return count(n) - 1;

Pentru ca această metodă să fie eficientă ne trebuie o metodă count eficientă.

Aplicaţia #6

Să se determine dacă n este o putere a lui 2 (întrebare interviu Microsoft).

int isTwoPower(long n){
  return (n & (n-1) == 0);
}

O altă abordare: preprocesarea

Operaţiile prezentate mai sus sunt implementate în limbajele de asamblare, dar câteodată se folosesc algoritmi naivi şi atunci o implementare inteligentă ajunge să fie mai rapidă decât instrucţiunea din limbajul de asamblare. Pentru unele supercalculatoare aceste instrucţiuni sunt instrucţiuni ale procesorului.
Se pot găsi alţi algoritmi mai rapizi decât cei de mai sus, dar de obicei găsirea unui algoritm mai inteligent este mai grea decât folosirea unei abordări banale care aduce un câştig foarte mare: preprocesarea.
În continuare vom rezolva problemele prezentate anterior folosindu-ne de preprocesarea datelor.

Aplicaţia #1

Determinăm, pentru numerele de la 0 la 2¹⁶ - 1, un tablou num, în care num[i] este egal cu numărul de biţi de 1 din reprezentarea binară a lui i.

int count(long n){
  return num[n & 0xFFFF] + num[n >> 16];
}

Aplicaţia #2

Determinăm, pentru numerele de la 0 la 2¹⁶ - 1, un tablou par, în care par[i] este egal cu paritatea numărului de biţi de 1 din reprezentarea binară a lui i.

int parity(long n){
  return par[n & 0xFFFF] ^ par[n >> 16];
}

Aplicaţia #3

Determinăm, pentru numerele de la 0 la 2¹⁶ - 1, un tablou l, în care l[i] este egal cu cel mai nesemnificativ bit de 1 din reprezentarea binară a lui i.

int low(long n){
  if (l[n & 0xFFFF]) return l[n & 0xFFFF];
  else return l[n >> 16] << 16;
}

Aplicaţia #4

Determinăm, pentru numerele de la 0 la 2¹⁶ - 1, un tablou h, în care h[i] este egal cu cel mai semnificativ bit de 1 din reprezentarea binară a lui i.

int high(long n){
  if (h[n >> 16]) return h[n >> 16] << 16;
  else return h[n & 0xFFFF];
}

Aplicaţia #5

Determinăm, pentru numerele de la 0 la 2¹⁶ - 1, un tablou iH, în care iH[i] este egal cu indexul celui mai semnificativ bit de 1 din reprezentarea binară a lui i şi este egal cu -1 pentru 0.

int indexHigh(long n) {
  if (iH[n >> 16] != -1) return iH[n >> 16] + 16;
  else return iH[n & 0xFFFF];
}