}
==

h2. Aplicaţia #5
 
bq. 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{~2~}$
$n = n | (n >> 1)$
$n = 11000000{~2~}$
$n = n | (n >> 2)$
$n = 11110000{~2~}$
$n = n | (n >> 4)$
$n = 11111111{~2~}$
 
Se observă că aplicând o secvenţă asemănătoare de instrucţiuni cu cea de mai sus putem face ca un număr $n$ să se transforme în alt număr care are un număr de biţi de 1 egal cu 1 + indexul celui mai semnificativ bit cu valoarea 1 din $n$. De aici algoritmul este următorul:
==code(cpp)|
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ă.
 
h2. Aplicaţia #6
 
bq. Să se determine dacă $n$ este o putere a lui 2 (întrebare interviu Microsoft).
 
==code(cpp)|
int isTwoPower(long n){
  return (n & (n-1) == 0);
}
==
 
 
h2. 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.
 
h3. Aplicaţia #1
 
bq. Determinăm, pentru numerele de la 0 la $2^16^ - 1$, un tablou $num$, în care $num[i]$ este egal cu numărul de biţi de 1 din reprezentarea binară a lui $i$.
 
De aici obţinem soluţia:
==code(cpp)|
int count(long n){
  return num[n & 0xFFFF] + num[n >> 16];
}
==
 
h3. Aplicaţia #2
 
bq. Determinăm, pentru numerele de la 0 la $2^16^ - 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$.
 
De aici obţinem soluţia:
==code(cpp)|
int parity(long n){
  return par[n & 0xFFFF] ^ par[n >> 16];
}
==
 
h3. Aplicaţia #3
 
bq. Determinăm, pentru numerele de la 0 la $2^16^ - 1$, un tablou $l$, în care $l[i]$ este egal cu cel mai nesemnificativ bit de 1 din reprezentarea binară a lui $i$.
 
De aici obţinem soluţia:
==code(cpp)|
int low(long n){
  if (l[n & 0xFFFF]) return l[n & 0xFFFF];
  else return l[n >> 16] << 16;
}
==
 
h3. Aplicaţia #4
 
bq. Determinăm, pentru numerele de la 0 la $2^16^ - 1$, un tablou $h$, în care $h[i]$ este egal cu cel mai semnificativ bit de 1 din reprezentarea binară a lui i.
 
De aici obţinem soluţia:
==code(cpp)|
int high(long n){
  if (h[n >> 16]) return h[n >> 16] << 16;
  else return h[n & 0xFFFF];
}
==
 
h3. Aplicaţia #5
 
bq. Determinăm, pentru numerele de la 0 la $2^16^ - 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.
 
De aici obţinem soluţia:
==code(cpp)|
int indexHigh(long n) {
  if (iH[n >> 16] != -1) return iH[n >> 16] + 16;
  else return iH[n & 0xFFFF];
}
==