Dându-se un număr natural n, să se găsească bitul de 1 cel mai semnificativ al lui n.

Exemplu. Pentru n = 10, reperezentarea sa binară este 1010, iar cel mai semnificativ bit de 1 este cel de pe poziția 3:

Explicarea algoritmului

Să comparăm problema în baza 10 (baza pe care o folosim noi de obicei). Dacă am vrea să determinăm poziția celei mai semnificative cifre (exemplu: pentru n = 52034, poziția este 5, dacă numărăm de la 1), practic va trebui să calculăm numărul de cifre ale lui n în baza 10.

Vom proceda similar. Cât timp n are cifre binare (n ≠ 0), îl vom împărți la 2 și vom contoriza numărul de împărțiri făcute. Acest număr este poziția celui mai semnifiactiv bit al lui n.

Va trebui să scădem 1 din răspuns, deoarece dacă un număr are k cifre binare și cifrele sale sunt numerotate de la 0, atunci cea mai semnificativă cifră se află pe poziția k - 1.

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 semnificativ bit de 1
    int poz = 0;
    while(n != 0) { //Cât timp n are cifre
        n = n / 2; //Tăiem ultima cifră (împărțim la 2 pentru că lucrăm în baza 2)
        poz++; //Incrementăm poziția celui mai semnificativ bit
    }
    cout << poz - 1; //Afișăm poziția: scădem 1 pentru că numărăm cifrele de la 0
    return 0;
}

Alte resurse și bibliografie

• InfoGenius
• Campion.edu.ro
• PbInfo