truncated binary logarithm

Question

I have a question about this problem, and any help would be great!

Write a program that takes one integer N as an argument and prints out its truncated binary logarithm [log2 N]. Hint: [log2 N] = l is the largest integer ` such that 2^l <= N.

I got this much down:

int N = Integer.parseInt(args[0]);  
    double l = Math.log(N) / Math.log(2);
    double a = Math.pow(2, l);

But I can't figure out how to truncate l while keeping 2^l <= N

Thanks

---

This is what i have now:

int N = Integer.parseInt(args[0]);

    int i = 0; // loop control counter
    int v = 1; // current power of two
    while (Math.pow(2 , i) <= N) {


    i = i + 1;
    v = 2 * v; 
    }

    System.out.println(Integer.highestOneBit(N)); 

This prints out the integer that is equal to 2^i which would be less than N. My test still comes out false and i think that is because the question is asking to print the i that is the largest rather than the N. So when i do

Integer.highestOneBit(i)

the correct i does not print out. For example if i do: N = 38 then the highest i should be 5, but instead it prints out 4.

Then i tried this:

            int N = Integer.parseInt(args[0]);

    int i; // loop control counter
    for (i= 0; Math.pow(2 , i) == N; i++) {

    }
            System.out.println(Integer.highestOneBit(i)); 

Where if i make N = 2 i should print out to be 1, but instead it is printing out 0.

I've tried a bunch of things on top of that, but cant get what i am doing wrong. Help would be greatly appreciated. Thanks

Answer 1

I believe the answer you're looking for here is based on the underlying notion of how a number is actually stored in a computer, and how that can be used to your advantage in a problem such as this.

Numbers in a computer are stored in binary - a series of ones and zeros where each column represents a power of 2:

(Above image from http://www.mathincomputers.com/binary.html - see for more info on binary)

The zeroth power of 2 is over on the right. So, 01001, for example, represents the decimal value 2^0 + 2^3; 9.

This storage format, interestingly, gives us some additional information about the number. We can see that 2^3 is the highest power of 2 that 9 is made up of. Let's imagine it's the only power of two it contains, by chopping off all the other 1's except the highest. This is a truncation, and results in this:

01000

You'll now notice this value represents 8, or 2^3. Taking it down to basics, lets now look at what log base 2 really represents. It's the number that you raise 2 to the power of to get the thing your finding the log of. log2(8) is 3. Can you see the pattern emerging here?

• The position of the highest bit can be used as an approximation to it's log base 2 value.

2^3 is the 3rd bit over in our example, so a truncated approximation to log base 2(9) is 3.

So the truncated binary logarithm of 9 is 3. 2^3 is less than 9; This is where the less than comes from, and the algorithm to find it's value simply involves finding the position of the highest bit that makes up the number.

Some more examples:

12 = 1100. Position of the highest bit = 3 (starting from zero on the right). Therefore the truncated binary logarithm of 12 = 3. 2^3 is <= 12.

38 = 100110. Position of the highest bit = 5. Therefore the truncated binary logarithm of 38 = 5. 2^5 is <= 38.

This level of pushing bits around is known as bitwise operations in Java.

Integer.highestOneBit(n) returns essentially the truncated value. So if n was 9 (1001), highestOneBit(9) returns 8 (1000), which may be of use.

A simple way of finding the position of that highest bit of a number involves doing a bitshift until the value is zero. Something a little like this:

// Input number - 1001:
int n=9;
int position=0;
// Cache the input number - the loop destroys it.
int originalN=n;

while( n!=0 ){
    position++; // Also position = position + 1;
    n = n>>1; // Shift the bits over one spot (Overwriting n).
    // 1001 becomes 0100, then 0010, then 0001, then 0000 on each iteration. 
    // Hopefully you can then see that n is zero when we've 
    // pushed all the bits off.
}

// Position is now the point at which n became zero.
// In your case, this is also the value of your truncated binary log.
System.out.println("Binary log of "+originalN+" is "+position);