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.

h2. Aplicaţia #3
 
bq. Să se determine cel mai puţin semnificativ bit de 1 din reprezentarea binară a lui n.
 
h3. Rezolvare
 
Rezolvarea naivă se comportă bine în medie, deoarece numărul de cicluri până la găsirea unui bit cu valoarea 1 este de obicei mic, dar din cele discutate mai sus putem găsi ceva mai bun.
Asa cum am arătat $n & (n - 1)$ are ca rezultat numărul $n$ din care s-a scăzut cel mai puţin semnificativ bit. Folosind această idee obţinem următoarea funcţie:
==code(cpp)|
int low1(long n){
   return n ^ (n & (n - 1));
}
==
 
Exemplu:
$n                 = 11011000{~2~}$
$n-1               = 11010111{~2~}$
$n & (n - 1)       = 11010000{~2~}$
$n                 = 11011000{~2~}$
$n ^ (n & (n - 1)) = 00001000{~2~}$
 
Această funcţie este foarte importantă pentru structura de date 'Arbori Indexaţi Binar':problema/aib prezentată într-un un articol mai vechi din 'GInfo':http://www.ginfo.ro/revista/13_1/focus.pdf.
 
h2. Aplicaţia #4
 
bq. Să se determine cel mai semnificativ bit cu valoarea 1 din reprezentarea binară a lui n.
 
h3. Rezolvare
 
Putem aplica şi aici ideile prezentate mai sus: cea naivă şi cea cu eliminarea biţilor, dar putem găsi şi ceva mai bun.
O abordare ar fi cea a căutării binare (aplicabilă şi în problema anterioară). Verificăm dacă partea superioară a lui n este 0. Dacă nu este 0, atunci căutăm bitul cel mai semnificativ din ea, iar dacă este, ne ocupăm de partea inferioară, deci reducem la fiecare pas problema la jumătate.
==code(cpp)|
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;
}
==