这可能是非常基本的,但对我来说节省一个小时左右的悲痛谁能告诉我如何才能制定出位代表在Java中给定的正整数需要多少?
例如我得到一个小数11,(1011)。我需要得到答案,4。
我想如果我能工作,如何比最显著位之外的所有位设置为0,然后>>>它,我会得到我的答案。但是......我不能。
那么,你可以算了算你有多少次右移之后,剩下的只是零之前:
int value = 11;
int count = 0;
while (value > 0) {
count++;
value = value >> 1;
}
这是C,但我怀疑,你可以很容易转换成Java:
Find the log base 2 of an N-bit integer in O(lg(N)) operations
什么是这样的:
public static int getNumberOfBits(int N) {
int bits = 0;
while(Math.pow(2, bits) <= N){
bits++;
}
return bits;
}
我知道你正在寻找一种方式,不使用循环,但我觉得这是相当两岸前进,否则因为位仅仅是两到数字的力量。
这一次对我的作品!
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;
}
你也可以像这样做,如果你不希望修改原始值。
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乘以负数。此外,你将不得不考虑要如何把符号位考虑。
(int) Math.ceil((Math.log(n) / Math.log(2))
当然,这仅适用于正整数。
那么,答案是非常简单的。如果你有一个int值:
int log2(int value) {
return Integer.SIZE-Integer.numberOfLeadingZeros(value);
}
同样存在长...
[编辑]如果刮毫秒是这里的问题,Integer.numberOfLeadingZeros(INT)是合理有效的,但仍然没有15个操作...扩展内存的合理数量(300个字节,静态),你可以刮胡子,为1和8之间操作,这取决于你的整数范围。
我的Java是有些生疏,但语言无关的答案(如果有“的log 2”功能,并提供了“地板”功能)将是:
numberOfBits = floor(log2(decimalNumber))+1
假设“DecimalNumber设置”大于0如果是0,你只需要1位。
Integer.toBinaryString(数字)。长度();
天哪......为什么向下票?
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。
编写程序是可读的,然后再找出它是缓慢的,然后使它更快。之前和您优化测试更改后。如果变化是不是让代码的可读性不改变打扰的代价够大。
以数字的两个基于日志将报告存储它所需的比特数。
如果你想避免循环和你所关心的速度,你可以用这样的方法:
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没有无符号整数,使第一,如果(值<0)是有点问题的。负数始终设置最显著位,所以可以说是需要完整的单词来代表他们。如果你关心适应这种行为。
顺便提及,以处理一个64位整数,取代与这些两个如果(值<0)线:
if( value < 0 ) { value = 0; count = 64; }
if( value >= 0x7FFFFFFF ) { value >>= 32; count += 32; }
对于非负值,可能是最直接的答案是:
java.math.BigDecimal.valueOf(value).bitLength()
(对于负数,它会给少了一个位长度比的绝对值,而不是无限你从二进制补码的期望。)
我想补充一些其他的替代品,只是为了完整起见:
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
,这是一个数字如此之高,你的脑袋可能会爆炸。注意,估计的宇宙containes一些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);
。
超过2的指数折半查找比位移位(top voted answer)解决方案,如果数字是巨大的(千位十进制数字),这可能是有价值的,你知道最大可用位,你不希望产生的表快:
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