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

Admin 1
Viewed 1348

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.

logarithm math algorithm java
4 Answers

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

2lg n = n,

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

1 = n / 2lg 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.

user_5015570

Its follows trivially from the logarithmic identity log(a/b) = log(a) - log(b).

You are searching for the largest integer x so that:

x <= log2(n)

Using the identity above and taking in account that log2(2) = 1 we get:

x <= log2(n/2) + log2(2)
x <= log2(n/2) + 1
x <= log2(n/4) + 2
x <= log2(n/8) + 3
...
x <= log2(1) + k            
x <= k                   (since log2(1) = 0)

So x is the number of times you divided n by 2 before reaching 1.

user_40399760

The answer is purely Mathmatics,

log₂(n) = ln(n)/ln(2) = x

By applying the rules of exponential:

ln(n) = ln(2)*(x)

n = 2^x

Therefore you have to divide by 2 until the value is smaller than 1 in order to get the closest int to it.

user_67852500

We are looking for the largest integer x such that x <= log_2(N) i.e. 2^x <= N

or equivalent 2^x <= N < 2^{x+1}

Let N_0=N

and for k > 0, N_k the quotient of the division of N_{k-1} by 2 and r_k in {0, 1} the remainder (N_{k-1} = 2.N_k + r_k)

We have:

2^{x-1} <= N_1 + (r_1 / 2) < 2^x

But 0 <= r_1 / 2 <= 1/2 and the others numbers are integers so that is equivalent to

2^{x-1} <= N_1 < 2^x

We have successively:

2^{x-1} <= N_1 < 2^x

2^{x-2} <= N_2 < 2^{x-1}

…

2^{x-x} <= N_x < 2^{x-x+1}

The last is also written 1 <= N_x < 2

But N_x is an integer so N_x = 1

Hence x is the number of division by 2 of N remaining greater or equal than 1.

Instead of starting from N_1, we can start from N_0 = N and stay greater than 1.

user_53994940
Related