在二进制中表示一个正整数需要多少位？

Question

这可能是相当基础的问题，但为了节省我几个小时的烦恼，有人能告诉我如何在Java中计算表示给定正整数所需的位数吗？

例如，我有一个十进制数11（1011），我需要得到答案4。

我想知道如何将最高有效位以外的所有位设置为0，然后使用>>>运算符得到答案。但是，我不会做，请帮忙解答。

- joinJpegs

Answer 1

好的，答案非常简单。如果您有一个int值：

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

对于长整型也存在同样的方法...

[编辑] 如果毫秒级别的性能是一个问题，那么可以使用Integer.numberOfLeadingZeros(int)方法，它的效率相当高，但仍然需要执行15个操作... 如果扩展一定数量的内存（300字节，静态），则可以将此数字减少到1至8个操作，具体取决于您的整数范围。

- Varkhan

---

这是最快的解决方案。而且比被采纳的答案更容易理解！ - TofuBeer

这可能是最快的解决方案，但从技术上讲它并不是万无一失的。尝试使用value = 0调用它，结果为：0。这有两个错误：首先，在数学上讲，log2（0）是未定义的。其次，在原始问题的背景下：当您想要存储一个值为零的整数时，您至少需要一个比特来完成。 - Matthias

如果这是唯一的问题，它可以被特别处理，而且仍然比其他答案更易理解且性能更好。 - TofuBeer

从Javadoc中可以看出：请注意，此方法与以2为底的对数密切相关。对于所有正整数值x：floor(log2(x)) = 31 - numberOfLeadingZeros(x) ceil(log2(x)) = 32 - numberOfLeadingZeros(x - 1) - mike

Answer 2

你可以数一下在最终变为零之前，需要向右位移多少次：

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

- jeffamaphone

---

哦！是的，那很简单。我本来期望有一些神奇的位运算技巧……感谢您的快速回复，我现在会使用它，但我很想知道是否有任何不需要循环等方法。 - joinJpegs

不适用于负数。尝试使用 while (value != 0) { ++count; value >>>= 1; }。>>> 是逻辑（无符号扩展）右移操作符。 - Tom Hawtin - tackline

@whataheck >> 1 表示向下取整除以2（因此-1“除以2”仍为-1）。>>> 1 将数字视为正数（无符号）并除以2。 - Tom Hawtin - tackline

@Tom Hawtin - tackline 好的..但是当我在我的程序中尝试使用 value >> 1;时，会出现编译错误"value >> 1"不是一个语句。 - crackerplace

@Tom Hawtin - tackline 也就是说，>> 1 是用于负数的，但在Java中我们没有无符号数，因此在进行此操作之前，每个数字都表示为位，即使它是负数。那么为什么我们需要两个运算符，一个用于正数，另一个用于负数呢？ - crackerplace

Answer 3

我的Java有点生疏，但是如果有“log2”函数和“floor”函数（不考虑编程语言的限制），答案将会是：

numberOfBits = floor(log2(decimalNumber))+1

假设"decimalNumber"大于0。如果它是0，那么你只需要1位。

- gnovice

---

我认为 decimalNumber 应该是 decimalNumber + 1。log_2 256 等于 8，但需要 9 位来表示。log_2 0 是未定义的，但需要零位来表示。 - strager

@strager：我认为你接近了答案。我需要使用“floor”而不是“ceil”，然后再加上1。显然，首先需要检查“decimalNumber == 0”。例如，尝试一下255（应该得到8）。 - gnovice

@gnovice，啊，好的。我自己也不确定。谢谢你的查看。=] - strager

当然，它不适用于负整数，有时您也必须计算这些数字的位数 :) 但是，如果您正在压缩数据，则我认为更好的方法是存储表示符号的位，然后存储其绝对值，因为-1将占用32位，而1将占用2位（1个用于1，另一个用于符号）。 - Statement

@语句：你说的有道理，但是OP说他们只想获取正整数的位数。 - gnovice

Answer 4

Integer.toBinaryString(number).length();

天哪...为什么会有人点踩呢？

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。

首先编写易于阅读的程序，然后查找其慢的部分并使其更快。 在优化之前和之后测试更改。 如果改变量不够大，以至于降低代码可读性的代价不值得，就不要费心去进行改变。

- TofuBeer

---

你可能会得到负评，因为你的解决方案非常昂贵。 - Daniel Brückner

没要求它必须快 :) - TofuBeer

似乎在“真正”的程序中，在我的桌面上执行1亿次操作可能不会成为瓶颈。 - TofuBeer

非常好的基准测试！为了完整起见，您可以添加 BigInteger.valueOf(i).bitLength()（这有点慢：在我的机器上，大约比您的 D 慢 5 或 6 倍） - Unai Vivi

然而，BigInteger.bitLength()在Java 6中存在缺陷且不可靠。http://bugs.sun.com/bugdatabase/view_bug.do;jsessionid=c134915207cae78f258c98a958f3?bug_id=6910473 - Unai Vivi

Answer 5

对该数字取以2为底的对数，可以得到存储该数字所需的位数。

- ojblass

---

A) -2 的声望不会让你死掉 B) 这可能是在审计中有点模糊，与审计主题不太相关，因此被踩了一下，以免再次影响某人。 - Foosh

所以我猜是 int(log2(n)) + 1。 - pronebird

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

- AHelps

---

这会给出错误的结果。当值为4时，它返回2，但实际上应该是3。事实上，在值为8时，它根本不输出3，直接跳到4。 - pdeva

抱歉，应该使用>=符号而不是>符号。我相信现在应该可以正常工作了。 - AHelps

Answer 7

对于非负数值，最直接的答案可能是：

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

（对于负数，它将给出比绝对值小1的位长度，而不是你从二进制补码中期望的无穷大。）

- Tom Hawtin - tackline

---

并不是绝对值的位数长度： System.out.println(BigInteger.valueOf(-1).bitLength()); 输出的是0，而不是1。 - Unai Vivi

@UnaiVivi 嗯，是的。已经更正了。如果方法针对负值抛出 IllegalStateException 而不是执行一些奇怪的操作可能会更好。 - Tom Hawtin - tackline

你有想法为什么他们那样做（对于负数）吗？我看不出他们那样做的任何用处... - Unai Vivi

@UnaiVivi 我认为如果你加上一个数字，你就会得到以二进制补码表示该值所需的最小位数。 - Tom Hawtin - tackline

Answer 8

这个对我有效！

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

为了包括负数，您可以添加一个额外的比特位并使用它来指定符号。

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

- Thiagesh thg

Answer 9

二分查找指数的2比位移(最高票答案)解决方案更快，如果数字很大(数千个十进制数位)，您知道可用的最大位数并且不想生成表格，这可能非常有价值。

    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;

然而，使用前导零的解决方案仍然要快得多：

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

基准测试：

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

- Ilya K.

Answer 10

为了完整起见，我想添加一些其他的选择：

1 BigInteger.valueOf(i).bitLength()

速度不是很快。此外，BigInteger.bitLength()存在错误和不可靠（在Java7中已修复），因为当需要超过Integer.MAX_VALUE位时（需要非常高的输入数字！[例如左移Integer.MAX_VALUE次的1，即2^Integer.MAX_VALUE]), 结果会溢出，并且负数会出现在接下来的2^(2*Integer.MAX_VALUE)-2^Integer.MAX_VALUE个数字中，这个数字非常大，足以让你的头爆炸。请注意，宇宙中估计有10^80个原子；那个数字是2^4G（G表示千兆，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;
}

一个非常快的解决方案，但仍然比古老的 32 - Integer.numberOfLeadingZeros(i); 慢一半。

- Unai Vivi