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

Alte resurse și bibliografie

• InfoGenius
• PbInfo
• Campion.edu.ro