logo标签列表

计算整数中使用的比特位数

javamathbinarybit-manipulation
4
如果你有二进制数10110，如何让它返回5？例如一个数字，告诉我们使用了多少位？以下是一些类似的例子：
  • 101应该返回3
  • 000000011应该返回2
  • 11100应该返回5
  • 101010101应该返回9
在Java中，最简单的方法是什么？我想出了下面的方法，但是否可以更快地完成？
public static int getBitLength(int value)
{
    if (value == 0)
    {
        return 0;
    }
    int l = 1;
    if (value >>> 16 > 0) { value >>= 16; l += 16; }
    if (value >>> 8 > 0) { value >>= 8; l += 8; }
    if (value >>> 4 > 0) { value >>= 4; l += 4; }
    if (value >>> 2 > 0) { value >>= 2; l += 2; }
    if (value >>> 1 > 0) { value >>= 1; l += 1; }
    return l;
}
1
在Java中，int类型始终使用32位。 - Richard H
看起来你在那里手动展开了一个循环。 - Ken
标题有误导性，因为在 int 中始终使用所有 32 位。 - Steve Kuo
1
我知道标题有点误导，但我不知道该怎么称呼它，如果您有建议，请发送给我，我会编辑标题。 - sigvardsen
请注意，这与log2(value)+1相同。https://dev59.com/LXA75IYBdhLWcg3wboYz - weston
11个回答
12

最简单的方式是什么？

32 - Integer.numberOfLeadingZeros(value)

如果你正在寻找算法，Java API的实现者赞同你的分而治之位移法：

public static int numberOfLeadingZeros(int i) {
    if (i == 0)
        return 32;
    int n = 1;
    if (i >>> 16 == 0) { n += 16; i <<= 16; }
    if (i >>> 24 == 0) { n +=  8; i <<=  8; }
    if (i >>> 28 == 0) { n +=  4; i <<=  4; }
    if (i >>> 30 == 0) { n +=  2; i <<=  2; }
    n -= i >>> 31;
    return n;
}

编辑：对于那些相信浮点计算精度的人，运行以下测试套件作为提醒：

public static void main(String[] args) {
    for (int i = 0; i < 64; i++) {
        long x = 1L << i;
        check(x);
        check(x-1);
    }
}

static void check(long x) {
    int correct = 64 - Long.numberOfLeadingZeros(x);
    int floated = (int) (1 + Math.floor(Math.log(x) / Math.log(2)));
    if (floated != correct) {
        System.out.println(Long.toString(x, 16) + " " + correct + " " + floated);
    }
}

第一个检测到的偏差是：

ffffffffffff 48 49
1
第一个解决方案是最好的 :) - nico
6

很遗憾，没有直接给出答案的Integer.bitLength()方法。

BigInteger有一个类似的方法，因此您可以使用它：

BigInteger.valueOf(value).bitLength()

构造BigInteger对象会使其效率略有降低，但只有在您需要执行数百万次时才会产生影响。

2

您希望计算数字的以2为底的对数 - 具体来说是：

1 + floor(log2(value))

Java有一个使用自然常数e作为底数的Math.log方法，因此您可以执行以下操作：

1 + Math.floor(Math.log(value) / Math.log(2))
@meriton - 相当确定！唯一的问题是当值为0时，你会得到负无穷大和其他美好的东西 :) - Chris
另一个特定的问题是负数，它们具有最高位设置。 - meriton
你很幸运，舍入误差只会在int范围之外显现。然而，对于0xffffffffffffL，你的代码将产生错误的结果49，而不是48。我会在我的答案中添加测试代码。 - meriton
1

小心你所要的。一种非常快速的技术是进行表格查找：

int bittable [] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, ... };
int numbits (int v)
{
    return bittable [v];
}

其中bittable包含每个整数的一个条目。当然，这对负值有一些复杂性。更实用的方法是计算数字的位字段中的位数。

int bittable [16] = {0, 1, 1, 2,  1, 2, 2, 3,  1, 2, 2, 3,  2, 3, 3, 4};
int numbits (int v)
{
    int s = 0;
    while (v != 0)
    {
         s += bittable [v & 15];
         v >>= 4;
    }
    return s;
}
1
这不是在计算设置的位数，而是在查找最高设置位的索引吗？ - Mark Dickinson
1

从这里开始，只需使用按位与和加法即可完成：

int GetHighestBitPosition(int value) {
  if (value == 0) return 0;

  int position = 1;
  if ((value & 0xFFFF0000) == 0) position += 16;
  if ((value & 0xFF00FF00) == 0) position += 8;
  if ((value & 0xF0F0F0F0) == 0) position += 4;
  if ((value & 0xCCCCCCCC) == 0) position += 2;
  if ((value & 0xAAAAAAAA) == 0) position += 1;

  return position;
}
1
你只需要查找最高位为1的位置。请参考此页面，在标题“查找整数的以2为底对数（也称最高位设置的位置）”下方。
1

Integer.toBinaryString(value).length()

0
另一个解决方案是使用BitSet的length()，根据API：

返回“逻辑大小”...最高设置位的索引...加一。

要使用BitSet，您需要创建一个数组。因此，它不像从纯int开始那么简单。但是您可以直接使用JDK - 经过测试和支持。代码如下：
  public static int bitsCount(int i) {
    return BitSet.valueOf(new long[] { i }).length();
  }

应用于问题中的示例：

  bitsCount(0b101); // 3
  bitsCount(0b000000011); // 2
  bitsCount(0b11100); // 5
  bitsCount(0b101010101); // 9

当请求位时，BitSet似乎是适当的数据结构。
0
int CountBits(uint value)
{
    for (byte i = 32; i > 0; i--)
    {
        var b = (uint)1 << (i - 1);
        if ((value & b) == b)
            return i;
    }
    return 0;
}
0
如果你正在寻找最快的方法（而且不需要表格，这肯定更快），那么这可能是最好的选择：
public static int bitLength(int i) {
    int len = 0;

    while (i != 0) {
        len += (i & 1);
        i >>>= 1;
    }

    return len;

}
你为什么要在“len += (i & 1)”中使用'&'运算符？这不只是给你一个位串中所有1的计数吗？ - Y_Y
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接