Smallest integer larger than lg N

Question

I was reading somewhere that:

The smallest integer larger than lg N is the number of bits required to represent N in binary, in the same way that the smallest integer larger than log10 N is the number of digits required to represent N in decimal.

The Java statement

for (lgN = 0; N > 0; lgN++, N /= 2) ; 

is a simple way to compute the smallest integer larger than lg N

I maybe missing something here but how does the Java statement calculate the smallest integer larger than lg N?

Answer 1

it might be clearer if rewritten as a while loop:

lgN = 0
while( N > 0 ) {
    lgN++;
    N = N/2;
}

Which can be thought of as "how many times do we have to right shift before we have shifted off all the 1s" (leaving us with a zero)

Answer 2

Write it out on paper. Example, for N = 1750

   lgN   N      N > 0?
1   0    1750   y
2   1    875    y
3   2    437    y
4   3    218    y
5   4    109    y
6   5    54     y
7   6    27     y
8   7    13     y
9   8    6      y  
10  9    3      y
11  10   1      y
12  11   0      n  stop; lgN = 11

Answer 3

This is an answer to the question you should ask, namely how to best compute this:

Don't do this with a loop. Calculate it directly:

int bits = (int) Math.floor(Math.log(n)/Math.log(2)) + 1;

Be careful not to let n == 0.

Answer 4

Have any problem just tracing this on sample input?

step 1) N = 10, lgN = 0
step 2) N = 5,  lgN = 1
step 3) N = 2,  lgN = 2
step 4) N = 1,  lgN = 3
step 5) N = 0,  lgN = 4

lgN is 4 in the end. That's the smallest integer larger than log(2, 10)