在Java中查找左/右最多未设置位的索引的最有效方法是什么？

Question

我们假设我们有int x = 371二进制格式101110011.我想找到最左边未设置位的索引(在这种情况下为7),以及最右边未设置位的索引(在本例中为2).这样做最有效的方法是什么？

这就是我所拥有的:

public class BitOperatons {

    public static int setBit(int x, int i) {
        int y = x | (1 << i);
        return y;
    }

    public static boolean isBitSet(int x, int i) {
        int y = setBit(0, i);
        return y == (x & y);
    }    

    public static int findLeftMostSetBit(int x) {
        for (int i = 31; i >= 0; i--) {
            if (isBitSet(x, i))
                return i;
        }
        return -1;
    }

    public static int findRightMostUnsetBit(int x) {
        for (int i = 0; i <= 31; i++) {
            if (! isBitSet(x, i))
                return i;
        }
        return -1;
    }

    public static int findLeftMostUnsetBit(int x) {
        int k = findLeftMostSetBit(x);
        for (int i = k; i >= 0; i--) {
            if (! isBitSet(x, i))
                return i;
        }
        return -1;
    }

    public static1+ void main(String[] args) {
        int x = 
            (1 << 0) |
            (1 << 1) |
            (1 << 4) |
            (1 << 5) |
            (1 << 6) |
            (1 << 8);
        System.out.println(findLeftMostUnsetBit(x));
        System.out.println(findRightMostUnsetBit(x));
    }

}

如果我没错,我当前的实现需要线性时间.我们可以做得更好吗？

Answer 1

下面是Integer.numberOfLeadingZeros的源代码.正如所指出的那样,它取自HD(Hacker's Delight by Henry S. Warren,Jr)

主要思想是使用二进制搜索,而不是逐个迭代这些位.如果你对比特感兴趣,请检查一下这本书.这是一件很棒的艺术品.

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

Answer 2

Integer 类中有一些可用的方法。

Integer.numberOfTrailingZeros(Integer.lowestOneBit(~yourValue))会对最低的未设置位执行此操作，对于最高的未设置位则有点棘手，因为我们首先必须确定最高的设置位。

int leadingZeroBits = Integer.numberOfLeadingZeros(Integer.highestOneBit(yourValue));
result = Integer.
       numberOfTrailingZeros(Integer.highestOneBit((~yourValue)<<leadingZeroBits)
      -leadingZeroBits;`

应该对最高未设置位执行此操作。

这可能比线性时间更快，因为处理器通常具有机器指令来快速确定前导/尾随零位（但不确定虚拟机是否使用它们编辑：我现在确定；-）。

编辑：似乎他们在 1.6.0_18，ID 6823354 中添加了对前导/尾随零使用 asm 内在函数