Dându-se un număr natural n, să se găsească bitul de 1 cel mai puțin semnificativ al lui n.
Exemplu. Pentru n = 10, reperezentarea sa binară este 1010, iar cel mai puțin semnificativ bit de 1 este cel de pe poziția 1:
Explicarea algoritmului
Vom parcurge biții numărului pe rând, de la poziția 0 până când întrecem valoarea n. Când întâlnim un bit de 1, ne oprim și afișăm poziția.
Cum parcurgem biții unui număr?
Vom genera puterile de 2: 20 = 1, 21 = 2, 22 = 4, …, până când întrecem valoarea n. Știm că o putere 2k are în reprezentarea sa binară k cifre de 0, după care o cifră de 1:
22 = 4 = 10
24 = 16 = 10000
20 = 1 = 1
Cu această observație, dacă facem AND între 2^i și n, putem afla dacă al i-lea bit din număr este 1 sau 0.
Implementare C++
Iată codul în C++:
#include <iostream>
using namespace std;
int main()
{
//Declarăm și citim numărul nostru, n
int n;
cin >> n;
//Determinăm cel mai puțin semnificativ bit de 1
int i = 0, j = 1; //i este poziția curentă (0, 1, 2, …), j = 2^i (1, 2, 4, …)
while(j <= n) {
if(j & n) { //Verificăm dacă al i-lea bit este 1
cout << i;
break;
}
i++; //Creștem puterea
j = j * 2;
}
return 0;
}