在Java原始类型中查找最高位的1

Question

在Java原始类型中查找最高位的1

7

我需要在Java中查找一些longs、ints和shorts中的最高位1。例如，如果我有一个看起来像00110101的char，我需要一个方法返回2（最高位1的索引）。

现在，我知道可以使用for循环来实现：

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

但这种方法比我想要的要慢得多。我知道现代CPU有内置指令可以执行此操作，因此我想知道如何调用它，而不是使用显式循环。

编辑：如果您只能返回原语中所有“1”的索引，则会获得额外的积分。

谢谢。

- twolfe18

你在使用大端机器吗？ - int3

运行你的代码后，我得到的是0而不是2。 - Buhb

出于好奇，你试图解决的问题只能通过这种位操作技巧来解决吗？ - Bart Kiers

1

@unknown，我的代码是反向的，它找到了最低位。无论它是高还是低都不重要。@Bart K，我正在为国际象棋写一个位棋盘。我很想放弃Java，用C来实现，但我有很多丑陋的网络代码，我不想重新编写。 - twolfe18

如果您更喜欢在C语言中进行位操作，为什么不使用JNI呢？此外，如果您正在尝试获取所有“on”索引，也许您的算法可能无法从使用位域中受益... 位域是否真的是您所做的最佳数据结构？ - Kevin Day

显示剩余5条评论

6个回答

3

页面 "位操作技巧" 包含许多位操作技巧。其中之一是如何找到最高位的索引。

- Aaron Digulla

我曾经在我的Java代码中使用这些算法，但是在过去几年中，大部分算法都已经被添加到平台API中了。 - finnw

然而，de Bruijn序列方法仍然比内置的numberOfLeadingZeros和numberOfTrailingZeros中使用的分治方法略快。 - finnw

1

我不知道这是否更快。但它没有循环。

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;

- yu_sha

0

我不知道如何触发CPU指令，但我知道如果展开循环并使用显式位掩码，速度会更快。

此外，char不是8位... 我想你可能是指字节。

- Kevin Day

我在想是不是C语言的char类型是8位的（对吧？...）。Java中的char类型是2个字节，是为了支持unicode编码吗？ - twolfe18

0

据我所知，Pentium及其同类处理器没有为此准备好的指令。因此，需要使用一个不错的算法。

快速获取答案的关键是使用二分查找。你正在查看具有64位的long类型？6次比较将每次给出最高位。

代码将输出一棵大而丑陋的由64个if语句组成的树，但只有其中的一小部分会被执行，因此运行时间很短。

如果您需要示例代码，我可以提供。但我宁愿不这样做。

- Carl Smotricz

不一定需要使用树来表达，可以看看我的答案。 - meriton

正如我所评论的，我喜欢代码的优雅，但我怀疑它的性能是否可接受。 - Carl Smotricz

0

Java 被编译为平台无关的字节码，因此您不能指望支持 CPU 指令。否则，您的代码或 Integer.highestOneBit() 的速度应该是最快的。

- FelixM

我原则上同意，但我认为Java在某些方面以平台相关的方式运作（为了提高效率），但如果平台不支持，则会回退到Java实现。我希望这是其中之一... - twolfe18

1

当然，JVM是特定于平台的，但对于您的情况，JIT编译器必须从字节码中检测出您的真实意图，这可能会很困难。但是，如果速度至关重要，您可以考虑使用平台无关的汇编语言，即C库和JNI。 - FelixM

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- meriton · Accepted Answer

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