java - 在 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(Henry S. Warren, Jr 的 Hacker's Delight)

主要思想是使用二进制搜索而不是逐位迭代。如果您对 bit twiddling 感兴趣，请查看这本书。这是一件美妙的艺术品。

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