How to find the largest power of 2 less than the given number

Question

I need to find the largest power of 2 less than the given number.
And I stuck and can't find any solution.

Code:

public class MathPow {
   public int largestPowerOf2 (int n) {
        int res = 2;        
        while (res < n) {
            res =(int) Math.pow(res, 2);
        }
        return res;
   }
}

This doesn't work correctly.

Testing output:

Arguments Actual Expected
-------------------------
9         16     8       
100       256    64      
1000      65536  512     
64        256    32      

How to solve this issue?

Answer 1

Why not use logs?

public int largestPowerOf2(int n) {
    return (int)Math.pow(2, Math.floor(Math.log(n) / Math.log(2));
}

log(n) / log(2) tells you the number of times 2 goes into a number. By taking the floor of it, gets you the integer value rounding down.

Answer 2

Integer.highestOneBit(n-1);

For n <= 1 the question doesn't really make sense. What to do in that range is left to the interested reader.

The's a good collection of bit twiddling algorithms in Hacker's Delight.

Answer 3

Change res =(int)Math.pow(res, 2); to res *= 2; This will return the next power of 2 greater than res.
The final result you are looking for will therefore finally be res / 2 after the while has ended.

To prevent the code from overflowing the int value space you should/could change the type of res to double/long, anything that can hold higher values than int. In the end you would have to cast one time.

Answer 4

You can use this bit hack:

v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;
v >>= 1;