Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

Number of digits in the binary representation of an integer

Revision en1, by BumbleBee, 2018-01-05 21:02:39

I usually find the number of digit in the binary representation of an integer in the following way:

int digit = 1 + (int)log2(n);

I used to think that this way is absolutely correct as I never found any error. But today I got WA in problem number B (Codeforces Round 456) due to finding the number of digits in this way and I understood that this way isn't 100% correct. An integer n = 288230376151711743 was given in the case in which I got WA verdict.

While testing the error, I printed the 2 base log of 288230376151711743 using the log2() function of C++ and it printed 58. According to that 2^58 should be equal to 288230376151711743, but it isn't. 2^58 is equal to 288230376151711744.

So I guess, the value of log2(288230376151711743) is 57.99999999... or something like that which is very close to 58 and due to precision issues log2() function returns 58 in this case.

To avoid such errors I changed the way of finding the number of digits in binary in the following way:

int digit = 1 + (int)log2(n);
long long int x=(long long int)pow(2,d-1);
if(x>n) d--;

After changing my code in this way I got AC verdict, but I am still not sure about the accuracy of my way.

I want to know how much accurate is this way of finding the number of digits. If it is still not accurate, kindly suggest some other ways of finding the number of digits in the binary form of an integer which are accurate and efficient enough.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English BumbleBee 2018-01-05 21:02:39 1531 Initial revision (published)