这可能是非常基本的，但是为了节省我一个小时左右的悲伤，谁能告诉我如何计算出在 Java 中表示给定正整数所需的位数？
例如，我得到一个小数点 11，(1011)。我需要得到答案，4。
我想如果我能弄清楚如何将除最高有效位之外的所有位设置为 0，然后 >>> 它，我就会得到答案。但是……我不能。
joinJpegs
问问题
46973 次
14 回答
35
嗯，答案很简单。如果你有一个 int 值：
int log2(int value) {
return Integer.SIZE-Integer.numberOfLeadingZeros(value);
}
龙也一样……
[编辑] 如果剃须毫秒是这里的问题， Integer.numberOfLeadingZeros(int) 相当有效，但仍然执行 15 次操作...扩展合理的内存量（300 字节，静态），您可以将其减少到 1 到 8操作，具体取决于整数的范围。
于 2009-03-25T02:40:42.017 回答
30
好吧，你可以计算在你只剩下零之前你向右移动了多少次：
int value = 11;
int count = 0;
while (value > 0) {
count++;
value = value >> 1;
}
于 2009-03-25T02:26:43.907 回答
27
我的 Java 有点生疏，但与语言无关的答案（如果有可用的“log2”函数和“floor”函数）将是：
numberOfBits = floor(log2(decimalNumber))+1
假设“decimalNumber”大于0。如果为0，则只需要1位。
于 2009-03-25T02:31:29.697 回答
15
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。
先把程序写成可读的，然后找出慢的地方，然后让它变快。优化前后测试变化。如果更改不足以降低代码的可读性，请不要为更改而烦恼。
于 2009-03-25T02:33:07.807 回答
11
取两个基于数字的日志将报告存储它所需的位数。
于 2009-03-25T02:33:23.577 回答
5
如果你想避免循环并且你关心速度，你可以使用这样的方法：
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; }
于 2009-03-25T05:44:23.120 回答
4
对于非负值，可能最直接的答案是：
java.math.BigDecimal.valueOf(value).bitLength()
（对于负数，它会给出比绝对值小一的位长度，而不是你从二进制补码符号中期望的无穷大。）
于 2009-03-25T11:21:31.607 回答
1
为了完整起见，我想添加一些其他替代方案：
1 BigInteger.valueOf(i).bitLength()
不是很快。此外，BigInteger.bitLength()它存在错误且不可靠（在 Java7 中已修复），因为当需要更多Integer.MAX_VALUE位时（需要非常高的输入数！！[例如 1 次左移Integer.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
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;
}
一个非常快速的解决方案，但仍然是 ye olde 的一半32 - Integer.numberOfLeadingZeros(i);。
于 2012-09-01T02:11:59.943 回答
1
对 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
于 2018-08-22T01:56:21.530 回答
1
这个对我有用！
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;
}
于 2018-10-13T11:56:14.457 回答
1
如果您不想修改原始值，也可以这样做。
unsigned int value = 11;
unsigned int count = 0;
if(value > 0)
{
for(int i=1;i<value;i*=2) // multiply by two => shift one to left
{
++count;
}
}
注意：让编译器担心i*=2变成移位操作来提高性能。
对于我们中间的视觉思想家：
64 32 16 8 4 2 1
0 0 0 1 0 1 1 -> binary representation of decimal number 'value' = 11 (=1+2+8)
我们从i=1右边开始。然后我们继续乘以 2，只要i < value。同时，我们跟踪我们向左移动了多少位。
所以在这个例子中，一旦i达到 16，值就大于 11，因此我们停止。然后我们将计算 4 位：1 *2 *2 *2 *2 = 16 (=2^4).
小心签名号码。在处理可能是正数或负数的有符号数时，您首先必须将负数乘以 -1。此外，您还必须考虑如何考虑符号位。
于 2019-02-11T18:05:59.573 回答
0
这是在 C 中，但我怀疑您可以相当容易地转换为 Java：
于 2009-03-25T04:12:52.590 回答
0
像这样的东西怎么样：
public static int getNumberOfBits(int N) {
int bits = 0;
while(Math.pow(2, bits) <= N){
bits++;
}
return bits;
}
我知道您正在寻找一种不使用循环的方法，但我觉得这是非常困难的，否则因为位只是数字的 2 次方。
于 2013-11-20T18:13:46.247 回答
-1
(int) Math.ceil((Math.log(n) / Math.log(2))
当然，这只适用于正整数。
于 2009-03-25T09:46:36.920 回答