在Java原语中找到最高阶1

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;
}

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

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

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;

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

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

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

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

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

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

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