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

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;

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.


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.

Tags:

Algorithm

Java