Find out number of bits needed to represent a positive integer in binary?

java bit-manipulation bits
joinJpegs picture joinJpegs · Mar 25, 2009 · Viewed 44.9k times · Source

This is probably pretty basic, but to save me an hour or so of grief can anyone tell me how you can work out the number of bits required to represent a given positive integer in Java?

e.g. I get a decimal 11, (1011). I need to get the answer, 4.

I figured if I could work out how to set all the bits other than the most significant bit to 0, and then >>> it, I'd get my answer. But... I can't.

Answer

Varkhan picture Varkhan · Mar 25, 2009

Well, the answer is pretty simple. If you have an int value:

int log2(int value) {
    return Integer.SIZE-Integer.numberOfLeadingZeros(value);
}

The same exists for Long...

[Edit] If shaving milliseconds is an issue here, Integer.numberOfLeadingZeros(int) is reasonably efficient, but still does 15 operations... Expanding a reasonable amount of memory (300 bytes, static) you could shave that to between 1 and 8 operations, depending on the range of your integers.

Related questions

Extract bit sequences of arbitrary length from byte[] array efficiently

I'm looking for the most efficient way of extracting (unsigned) bit sequences of arbitrary length (0 <= length <= 16) at arbitrary position. The skeleton class show how my current implementation essentially handles the problem: public abstract class BitArray { byte[] bytes = new …

Read More
Bitwise operator for simply flipping all bits in an integer?

I have to flip all bits in a binary representation of an integer. Given: 10101 The output should be 01010 What is the bitwise operator to accomplish this when used with an integer? For example, if I were writing a method like …

Read More
Java "Bit Shifting" Tutorial?

I would be thankful for a good tutorial, that explain for java newbies how in java all the "bit shifting" work. I always stumble across it, but never understood how it works. It should explain all the operations and concepts …

Read More