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.

Answer 1

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.

Answer 2

You can also do it like this, if you don't want to modify the original value.

unsigned int value = 11;
unsigned int count = 0;
if(value > 0)
{
    for(int i=1;i<value;i*=2) // multiply by two => shift one to left
    {
        ++count;
    }
}

Note: Let the compiler worry about turning i*=2 into a bit shift operation to improve performance.

For the visual thinkers among us:

64 32 16  8  4  2  1
 0  0  0  1  0  1  1  -> binary representation of decimal number 'value' = 11 (=1+2+8)

We start with i=1 at the right. Then we keep multiplying by two, for as long as i < value. In the meanwhile, we keep track of how many bits we went to the left.

So in this example, as soon as i reaches 16 the value is larger than 11, and thus we stop. And we will then have counted 4 bits: 1 *2 *2 *2 *2 = 16 (=2^4).

Careful with signed numbers. When dealing with signed numbers that may be positive or negative, you would first have to multiply the negative numbers by -1. Additionally, you would have to consider how you want to take the sign-bit into account.

Answer 3

This one works for me!

int numberOfBitsRequired(int n)
{
    return (int)Math.floor(Math.log(n)/Math.log(2)) + 1;
}

To include negative numbers as well, you can add an extra bit and use it to specify the sign.

public static int numberOfBitsRequiredSigned(int n)
{
    return (int)Math.floor(Math.log(Math.abs(n))/Math.log(2)) + 2;
}

Answer 4

Binary search over the the exponents of 2 is faster than the bit shift (top voted answer) solution, which might be valuable if the numbers are huge (thousands of decimal digits), you know the maximum available bits and you do not want to generate the tables:

    int  minExpVal   = 0;
    int  maxExpVal   = 62;
    int  medExpVal   = maxExpVal >> 1;
    long medianValue = 0l;

    while (maxExpVal - minExpVal > 1) {
        medianValue = 1l << medExpVal;
        if (value > medianValue) {
            minExpVal = medExpVal;
        } else {
            maxExpVal = medExpVal;
        }
        medExpVal = (minExpVal + maxExpVal) >> 1;
    }

    return value == 1l << maxExpVal ?  maxExpVal  + 1 : maxExpVal;

However, the solution using the leading zeros would be still by far faster:

return Long.SIZE - Long.numberOfLeadingZeros(value);

Benchmarks:

Leading zeros time is: 2 ms
BinarySearch time is: 95 ms
BitShift time is: 135 ms

Answer 5

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

Here is a simple test for the speed of the various solutions:

public class Tester 
{
    public static void main(final String[] argv) 
    {
        final int size;
        final long totalA;
        final long totalB;
        final long totalC;
        final long totalD;

        size = 100000000;

        totalA = test(new A(), size);
        totalB = test(new B(), size);
        totalC = test(new C(), size);
        totalD = test(new D(), size);

        System.out.println();
        System.out.println("Total D = " + totalD + " ms");
        System.out.println("Total B = " + totalB + " ms");
        System.out.println("Total C = " + totalC + " ms");
        System.out.println("Total A = " + totalA + " ms");

        System.out.println();
        System.out.println("Total B = " + (totalB / totalD) + " times slower");
        System.out.println("Total C = " + (totalC / totalD) + " times slower");
        System.out.println("Total A = " + (totalA / totalD) + " times slower");
    }

    private static long test(final Testable tester, 
                             final int      size)
    {
        final long start;
        final long end;
        final long total;

        start = System.nanoTime();
        tester.test(size);
        end   = System.nanoTime();
        total = end - start;

        return (total / 1000000);
    }

    private static interface Testable
    {
        void test(int size);
    }

    private static class A
        implements Testable
    {
        @Override
        public void test(final int size)
        {
            int value;

            value = 0;

            for(int i = 1; i < size; i++)
            {
                value += Integer.toBinaryString(i).length();
            }

            System.out.println("value = " + value);
        }    
    }

    private static class B
        implements Testable
    {
        @Override
        public void test(final int size)
        {
            int total;

            total = 0;

            for(int i = 1; i < size; i++)
            {
                int value = i;
                int count = 0;

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

                total += count;
            }

            System.out.println("total = " + total);
        }    
    }

    private static class C
        implements Testable
    {
        @Override
        public void test(final int size)
        {
            int total;
            final double log2;

            total = 0;
            log2  = Math.log(2);

            for(int i = 1; i < size; i++)
            {
                final double logX;
                final double temp;

                logX   = Math.log(i);
                temp   = logX / log2;                
                total += (int)Math.floor(temp) + 1;
            }

            System.out.println("total = " + total);
        }    
    }

    private static class D
        implements Testable
    {
        @Override
        public void test(final int size)
        {
            int total;

            total = 0;

            for(int i = 1; i < size; i++)
            {
                total += 32-Integer.numberOfLeadingZeros(i);
            }

            System.out.println("total = " + total);
        }    
    }
}

Output on my machine is:

value = -1729185023
total = -1729185023
total = -1729185023
total = -1729185023

Total D = 118 ms
Total B = 1722 ms
Total C = 4462 ms
Total A = 5704 ms

Total B = 14 times slower
Total C = 37 times slower
Total A = 48 times slower

For those of you complaining about speed... https://en.wikipedia.org/wiki/Program_optimization#Quotes.

Write the program to be readable first, then find out where it is slow, then make it faster. Before and after you optimize test the change. If the change wasn't large enough for the expense of making the code less readable don't bother with the change.

Answer 6

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

Answer 7

What about something like this:

public static int getNumberOfBits(int N) {
    int bits = 0;
        while(Math.pow(2, bits) <= N){
           bits++;
       }
       return bits;
}

I know you are looking for a way to not use loops, but I feel this is pretty strait forward otherwise since bits are just a two to the power of a number.

Answer 8

I would like to add some other alternatives, just for the sake of completeness:

1 BigInteger.valueOf(i).bitLength()

Not very fast. Furthermore, BigInteger.bitLength() it's bugged and unreliable (fixed in Java7), since when more than Integer.MAX_VALUE bits are needed (freakishly high input number needed!! [such as 1 left-shifted Integer.MAX_VALUE times, aka 2^Integer.MAX_VALUE]) the result overflows and negative numbers appear for the next 2^(2*Integer.MAX_VALUE)-2^Integer.MAX_VALUE numbers, which is a number so high your head could explode. Note that it is estimated the universe containes some 10^80 atoms; that number is 2^4G (G as in Giga, 1024*1024*1024).

2

static int neededBits(int i)
{
    assert i > 0;
    int res;
    int sh;
    res = ((i > 0xFFFF) ? 1 : 0) << 4;
    i >>= res;
    sh = ((i > 0xFF) ? 1 : 0) << 3;
    i >>= sh;
    res |= sh;
    sh = ((i > 0xF) ? 1 : 0) << 2;
    i >>= sh;
    res |= sh;
    sh = ((i > 0x3) ? 1 : 0) << 1;
    i >>= sh;
    res |= sh;
    res |= (i >> 1);
    return res + 1;
}

A very fast solution, but still half as fast as ye olde 32 - Integer.numberOfLeadingZeros(i);.

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 one less than the absolute value, rather than infinity you'd expect from two's complement notation.)

Answer 10

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 11

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 = value >> 1;
}

Answer 12

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

Of course this only works for positive integers.

Answer 13

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 14

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.