java 计算 int 中使用的位数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2935793/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Count bits used in int
提问by sigvardsen
If you have the binary number 10110 how can I get it to return 5? e.g a number that tells how many bits are used? There are some likewise examples listed below:
如果你有二进制数 10110 我怎样才能让它返回 5？例如，一个数字说明使用了多少位？下面列出了一些同样的例子：
- 101 should return 3
- 000000011 should return 2
- 11100 should return 5
- 101010101 should return 9
- 101 应该返回 3
- 000000011 应该返回 2
- 11100 应该返回 5
- 101010101 应该返回 9
How can this be obtained the easiest way in Java? I have come up with the following method but can i be done faster:
如何在 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;
}
回答by meriton
Easiest?
最简单？
32 - Integer.numberOfLeadingZeros(value)
If you are looking for algorithms, the implementors of the Java API agree with your divide-and-conquer bitshifting approach:
如果您正在寻找算法，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;
}
Edit: As a reminder to those who trust in the accuracy of floating point calculations, run the following test harness:
编辑：提醒那些相信浮点计算准确性的人，请运行以下测试工具：
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);
}
}
The first detected deviation is:
第一个检测到的偏差是：
ffffffffffff 48 49
回答by starblue
Unfortunately there is no Integer.bitLength()method that would give you the answer directly.
不幸的是，没有Integer.bitLength()方法可以直接给你答案。
An analogous method exists for BigInteger, so you could use that one:
存在一种类似的方法BigInteger，因此您可以使用该方法：
BigInteger.valueOf(value).bitLength()
Constructing the BigIntegerobject will make it somewhat less efficient, but that will only matter if you do it many millions of times.
构造BigInteger对象会降低它的效率，但这只有在你执行数百万次时才有意义。
回答by Chris
You want to compute the base 2 logarithm of the number - specifically:
您想计算数字的以 2 为底的对数 - 特别是：
1 + floor(log2(value))
Java has a Math.log method which uses base e, so you can do:
Java 有一个使用基数 e 的 Math.log 方法，因此您可以执行以下操作：
1 + Math.floor(Math.log(value) / Math.log(2))回答by wallyk
Be careful what you ask for. One very fast technique is to do a table lookup:
小心你的要求。一种非常快速的技术是进行查表：
int bittable [] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, ... };
int numbits (int v)
{
return bittable [v];
}
where bittablecontains an entry for every int. Of course that has complications for negative values. A more practical way would be to count the bits in bitfields of the number
wherebittable包含每个 int 的条目。当然，这对负值来说很复杂。更实用的方法是计算数字位域中的位数
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;
}
回答by Victor Liu
回答by Ken
From here, a way to do it with just bitwise-and and addition:
从这里开始，一种只需按位与加法即可实现的方法：
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;
}
回答by Jacob Abraham
Integer.toBinaryString(value).length()
Integer.toBinaryString(value).length()
回答by LuCio
Another solution is to use the length()of a BitSetwhich according to the API
另一种解决方案是根据API使用length()a BitSetwhich
Returns the "logical size" ... the index of the highest set bit ... plus one.
返回“逻辑大小”......最高设置位的索引......加一。
To use the BitSetyou need to create an array. So it is not as simple as starting with a pure int. But you get it out of the JDK box - tested and supported. It would look like this:
要使用BitSet您需要创建一个数组。所以它并不像从一个纯int. 但是您可以将它从 JDK 盒子中取出 - 经过测试和支持。它看起来像这样：
public static int bitsCount(int i) {
return BitSet.valueOf(new long[] { i }).length();
}
Applied to the examples in the question:
应用于问题中的示例：
bitsCount(0b101); // 3
bitsCount(0b000000011); // 2
bitsCount(0b11100); // 5
bitsCount(0b101010101); // 9
When asking for bits the BitSetseems to me to be the appropriate data structure.
当要求位时，BitSet在我看来是合适的数据结构。
回答by realworldcoder
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;
}
回答by cyanide
If you are looking for the fastest (and without a table, which is certainly faster), this is probably the one:
如果您正在寻找最快的（并且没有桌子，这肯定更快），这可能是一个：
public static int bitLength(int i) {
int len = 0;
while (i != 0) {
len += (i & 1);
i >>>= 1;
}
return len;
}
