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

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)

Answer 2

Consider N in binary form, without all the zeros at the left.

For example, for 19 it would be 10011.

Each N/=2 is shifting this one bit at the right:

• 10011
• 1001
• 100
• 10
• 1
• 0

When N is equal to 0 then lgN (which is the number of step) is equal to log(N).

Answer 3

lg N is smaller than k:

• if and only if N is smaller than 2^k
• if and only if dividing N by 2, k times, results in 0 (remember that integer division rounds down).

So, the least integer greater than lg N is the number of divisions by 2 required to get to 0, and that's what the loop does.

Answer 4

Assuming everything else is correct, the code would be using a "lgN" variable that exists outside of the loop. When the loop finishes, "lgN" would be the answer.

Answer 5

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 6

yes, for base 2 logarithm... (ln N)/(ln 2), not the natural logarithm

Answer 7

It appears this is calculating log_2 of N. So think in terms of binary, how many bits does it take to represent N? The way you find out is count the number of times you can divide N by 2 (shift the bits in N to the right 1 space). The number of times you do this before N reaches 0 is the value you're calculating.

Answer 8

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 9

It is a for loop. Its initial condition is that lgN has the value zero. The loop continues so long as N is greater than zero. At each iteration in the loop, it adds one to lgN and divides N by 2.

That's a very literal translation of what the loop does. How does it work? Well, the first time through the loop, it increments lgN and divides N by 2. So if N was 1, N is now zero, and we're done. If N was larger than one, we have to iterate again. Every time you can divide N by 2 without getting to zero is another required bit in the binary representation. The code basically asks, "how many times can I divide N by 2 before I reach 0?" and that is the smallest integer larger than lg N.

Answer 10

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 11

For those going off on a tangent and trying to "stop the loop madness" by providing a more efficient solution to a question that wasn't asked, I propose this which is simultaneously more efficient and readable:

 public int bitsNeeded(int n) {
     return 32 - Integer.numberOfLeadingZeros(n);
 }

As the Javadoc for Integer.numberOfLeadingZeros() says:

Note that this method is closely related to the logarithm base 2. For all positive int values x:

• floor(log2(x)) = 31 - numberOfLeadingZeros(x)
• ceil(log2(x)) = 32 - numberOfLeadingZeros(x - 1)

I didn't post this before since it was tangential as I said. The OP was trying to understand the loop, not find the "best" way of doing something.