Calculating the largest int less than the base 2 log of N

Question

I have been reading Algorithms, 4th Edition, and it defines a question as follows:

Write a static method lg() that takes an int value N as an argument and returns the largest int not larger than the base-2 logarithm of N in Java. Do not use Math.

I discovered the following solution:

public static int lg(int N) {
    int x = 0;
    for (int n = N; n > 1; n/= 2) x++;
    return x;
}

I am wondering why that solution works. Why does dividing by 2 continuously allow us to find the largest integer less than the base 2 logarithm of the argument? I do understand Java, just not how this particular algorithm works.

Thank you.

Answer 1

This has to do with properties of exponents and logarithms. The main observation you need is that

2^{lg n} = n,

because logarithms are the inverses of exponentials. Rearranging that expression gives

1 = n / 2^{lg n}.

In other words, the value of lg n is the number of times you have to divide n by two in order to drop it to 1. This, by the way, is a really great intuition to have when studying algorithms, since log terms show up all the time in contexts like these.

There are some other nuances here about how integer division works, but this is the basic idea behind why that code works.