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

Question

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.

Thanks for your help!

Answer 1

Well, you can just count how many times you shift right before you're left with just zero:

int value = 11;
int count = 0;
while (value > 0) {
    count++;
    value >> 1;
}

Answer 2

My Java is a bit rusty, but the language-agnostic answer (if there is a "log2" function and a "floor" function available) would be:

numberOfBits = floor(log2(decimalNumber))+1

Assuming that "decimalNumber" is greater than 0. If it is 0, you just need 1 bit.

Answer 3

Integer.toBinaryString(number).length();

Good grief... why the down votes?

public class Main
{
    public static void main(final String[] argv)
    {
        System.out.println(Integer.toBinaryString(0).length());
        System.out.println(Integer.toBinaryString(1).length());
        System.out.println(Integer.toBinaryString(2).length());
        System.out.println(Integer.toBinaryString(3).length());
        System.out.println(Integer.toBinaryString(4).length());
        System.out.println(Integer.toBinaryString(5).length());
        System.out.println(Integer.toBinaryString(6).length());
        System.out.println(Integer.toBinaryString(7).length());
        System.out.println(Integer.toBinaryString(8).length());
        System.out.println(Integer.toBinaryString(9).length());
    }
}

Output:

1
1
2
2
3
3
3
3
4
4

Answer 4

Taking the two based log of the nubmer will report the number of bits required to store it.

Answer 5

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

   int log2(int value) {
       return 32-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.

Answer 6

This is in C, but I suspect you could convert to Java fairly easily:

Find the log base 2 of an N-bit integer in O(lg(N)) operations

Answer 7

If you're trying to avoid a loop and you care about speed, you can use a method like this:

int value = ...;
int count = 0;
if( value < 0 ) { value = 0; count = 32; }
if( value > 0x7FFF ) { value >>= 16; count += 16; }
if( value > 0x7F ) { value >>= 8; count += 8; }
if( value > 0x7 ) { value >>= 4; count += 4; }
if( value > 0x3 ) { value >>= 2; count += 2; }
if( value > 0x1 ) { value >>= 1; count += 1; }

Java doesn't have unsigned integers, so that first if( value < 0 ) is a little questionable. Negative numbers always set the most significant bit, so arguably require the full word to to represent them. Adapt that behavior if you care.

Incidentally, to handle a 64-bit integer, replace the if( value < 0 ) line with these two:

if( value < 0 ) { value = 0; count = 64; }
if( value > 0x7FFFFFFF ) { value >>= 32; count += 32; }

Answer 8

(int) Math.ceil((Math.log(n) / Math.log(2))

Of course this only works for positive integers.

Answer 9

For non-negative values, probably the most direct answer is:

java.math.BigDecimal.valueOf(value).bitLength()

(For negative numbers it will give the bit length of the absolute value, rather than infinity you'd expect from two's complement notation.)