代码之家 › 专栏 › 技术社区 › twolfe18

在Java原语中找到最高阶1

bit-manipulation java

twolfe18 · 技术社区 · 15 年前

我需要在Java中找到最高长度的1,在一些长,内,短裤。例如,如果我有一个像 00110101 ,我需要一个返回2的方法(最高顺序1的索引)。

现在,我知道您可以使用for循环进行此操作,例如:

for(int i=0; i<8; i++)
    if((x & 1<<i) != 0) return i;
return -1;

但这比我想做的要慢得多。我知道现代的CPU在芯片上有这样的指令,所以我想知道如何调用它,而不是使用显式循环。

编辑:如果您只返回原语中所有索引的话,就可以获得奖励积分。

谢谢。

6 回复 | 直到 10 年前

meriton 15 年前

Integer.numberOfLeadingZeros(i) + 1

该方法使用了一种很好的分而治之的方法,复制到这里供您查看:

public static int numberOfLeadingZeros(int i) {
    // HD, Figure 5-6
    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;
}

Aaron Digulla 15 年前

“页面” Bit Twiddling Hacks “包含很多比特黑客。一是如何找到 index of the highest order bit .

yu_sha 15 年前

我不知道这是否更快。但它没有回路。

if(i==0) return -1;

highest=0;
if (i & 0xffff0000)
{
   highest+=16;
   i>>=16;
}
if (i & 0xff00)
{
   highest+=8;
   i>>=8;
}
if (i & 0xf0)
{
   highest+=4;
   i>>=4;
}
if (i & 0xC)
{
   highest+=2;
   i>>=2;
}
if (i & 0x2)
{
   highest+=1;
}

return highest;

Kevin Day 15 年前

我不知道如何命中CPU指令,但我知道如果展开循环并使用显式位屏蔽,这将更快。

另外,字符不是8位…我想你可能是指一个字节。

Carl Smotricz 15 年前

据我所知,奔腾和朋友们并没有现成的指令。所以要做的就是使用一个合适的算法。

快速得到答案的关键是使用二进制搜索。你看到的是 long 64位?6每次比较都会给你最高的分数。

这段代码得到了一个由64个if语句组成的难看的树,但是只有一小部分语句会被执行,所以运行时很好。

如果您需要示例代码,我可以这样做。但我不想。

FelixM 15 年前

Java被编译成与平台无关的字节码,您不能期望对CPU指令的支持。否则,您的代码或integer.highestonebit()应该尽可能快。