找出表示二进制正整数所需的位数？

Question

这可能是非常基本的,但为了节省我一小时左右的悲伤,任何人都可以告诉我如何计算出代表Java中给定正整数所需的位数？

例如,我得到小数11,(1011).我需要得到答案,4.

我想如果我能弄清楚如何将除最高位之外的所有位设置为0,然后>>>它,我会得到我的答案.但是......我做不到.

Answer 1

嗯,答案很简单.如果你有一个int值:

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

Long存在同样的情况......

[编辑]如果剃须毫秒是一个问题,Integer.numberOfLeadingZeros(int)相当有效,但仍然进行15次操作......扩展合理的内存量(300字节,静态),你可以将其削减到1到8之间操作,取决于整数的范围.

Answer 2

好吧,你可以算一下你离开前只有零次移动的次数:

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

Answer 3

我的Java有点生疏,但与语言无关的答案(如果有"log2"函数和"floor"函数可用)将是:

numberOfBits = floor(log2(decimalNumber))+1

假设"decimalNumber"大于0.如果为0,则只需要1位.

Answer 4

Integer.toBinaryString(数字).长度();

好悲伤...为什么下来投票？

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

输出:

1
1
2
2
3
3
3
3
4
4

这是对各种解决方案速度的简单测试:

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

我机器上的输出是:

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

对于那些抱怨速度的人... https://en.wikipedia.org/wiki/Program_optimization#Quotes.

编写程序首先可读,然后找出它慢的地方,然后加快速度.优化测试之前和之后的变化.如果更改不足以使代码不易读取的费用,请不要理会更改.

Answer 5

取两个基于该数字的日志将报告存储它所需的位数.

Answer 6

如果你试图避免循环而你关心速度,你可以使用这样的方法:

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没有无符号整数,因此首先if(value <0)有点可疑.负数总是设置最重要的位,所以可以说需要完整的单词来表示它们.如果你在意的话,适应这种行为.

顺便提一下,要处理64位整数,请用这两个替换if(value <0)行:

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