Find out number of bits needed to represent a posi

问题:

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.

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

回答2:

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.

回答3:

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.

回答4:

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.

回答5:

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

回答6:

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; }

回答7:

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.)

回答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);.

回答9:

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

回答10:

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

Of course this only works for positive integers.

回答11:

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.

回答12:

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

回答13:

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;
}