Java 找出用二进制表示正整数所需的位数？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/680002/
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
Find out number of bits needed to represent a positive integer in binary?
提问by joinJpegs
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?
这可能是非常基本的，但是为了节省我一个小时左右的悲伤，谁能告诉我如何计算在 Java 中表示给定正整数所需的位数？
e.g. I get a decimal 11, (1011). I need to get the answer, 4.
例如，我得到一个十进制 11，(1011)。我需要得到答案，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.
我想如果我能想出如何将除最重要位以外的所有位设置为 0，然后 >>> 它，我会得到我的答案。但是……我不能。
采纳答案by i_am_jorf
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;
}
回答by gnovice
My Java is a bit rusty, but the language-agnostic answer (if there is a "log2" function and a "floor" function available) would be:
我的 Java 有点生疏，但与语言无关的答案（如果有可用的“log2”函数和“floor”函数）将是：
numberOfBits = floor(log2(decimalNumber))+1
Assuming that "decimalNumber" is greater than 0. If it is 0, you just need 1 bit.
假设“decimalNumber”大于0。如果是0，则只需要1位。
回答by TofuBeer
Integer.toBinaryString(number).length();
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.
对于那些抱怨速度的人... 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.
先把程序写成可读，然后找出它慢的地方，然后让它更快。在优化之前和之后测试更改。如果更改不够大，以降低代码可读性为代价，请不要理会更改。
回答by ojblass
Taking the two based log of the number will report the number of bits required to store it.
取两个基于数字的日志将报告存储它所需的位数。
回答by Varkhan
Well, the answer is pretty simple. If you have an int value:
嗯，答案很简单。如果您有一个 int 值：
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.
[编辑] 如果在这里刮毫秒是一个问题，Integer.numberOfLeadingZeros(int) 是相当有效的，但仍然执行 15 次操作......扩展合理数量的内存（300 字节，静态），您可以将其刮到 1 到 8 之间操作，取决于整数的范围。
回答by Jim Mischel
This is in C, but I suspect you could convert to Java fairly easily:
这是在 C 中，但我怀疑你可以很容易地转换为 Java：
Find the log base 2 of an N-bit integer in O(lg(N)) operations
回答by AHelps
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.
Java 没有无符号整数，因此首先 if( value < 0 ) 有点问题。负数总是设置最高有效位，因此可以说需要完整的字来表示它们。如果您关心，请调整该行为。
Incidentally, to handle a 64-bit integer, replace the if( value < 0 ) line with these two:
顺便说一句，要处理 64 位整数，请将 if( value < 0 ) 行替换为以下两个：
if( value < 0 ) { value = 0; count = 64; }
if( value >= 0x7FFFFFFF ) { value >>= 32; count += 32; }
回答by AHelps
(int) Math.ceil((Math.log(n) / Math.log(2))
Of course this only works for positive integers.
当然，这只适用于正整数。
回答by Tom Hawtin - tackline
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.)
（对于负数，它会给出比绝对值少 1 的位长度，而不是您期望从二进制补码表示法中得到的无穷大。）
回答by Unai Vivi
I would like to add some other alternatives, just for the sake of completeness:
为了完整起见，我想添加一些其他替代方案：
1BigInteger.valueOf(i).bitLength()
1BigInteger.valueOf(i).bitLength()
Not very fast. Furthermore, BigInteger.bitLength()it's bugged and unreliable (fixed in Java7), since when more than Integer.MAX_VALUEbits are needed (freakishly high input number needed!! [such as 1 left-shifted Integer.MAX_VALUEtimes, aka 2^Integer.MAX_VALUE]) the result overflows and negative numbers appear for the next 2^(2*Integer.MAX_VALUE)-2^Integer.MAX_VALUEnumbers, 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(Gas in Giga, 1024*1024*1024).
不是很快。此外，BigInteger.bitLength()它存在漏洞且不可靠（在 Java7 中已修复），因为当Integer.MAX_VALUE需要多于位时（需要非常高的输入数字！！[例如 1Integer.MAX_VALUE次左移，又名2^Integer.MAX_VALUE]）结果溢出并且下一个2^(2*Integer.MAX_VALUE)-2^Integer.MAX_VALUE数字出现负数，这是一个很高的数字，你的头可能会爆炸。请注意，估计宇宙包含大约 10^80 个原子；这个数字是2^4G（G如在 Giga 中，1024*1024*1024）。
2
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);.
一个非常快的解决方案，但仍然是 ye olde 的一半32 - Integer.numberOfLeadingZeros(i);。
