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