java - 获取数字最左边0位的位置

Question

我正在尝试获取整数的数字 0 的最左边位置

    int a = 83

例如，83的二进制是1010011，所以我们最左边的位0的位置是第6位。我想知道有没有办法只使用按位运算符来找到答案？

Answer 1

TL;DR

private static int leftmostZeroBit(int a) {
    int b = Integer.highestOneBit(a);
    return (b == 0 ? -1 : 31 - Integer.numberOfLeadingZeros(a ^ b ^ (b - 1)));
}

private static int leftmostZeroBit(long a) {
    long b = Long.highestOneBit(a);
    return (b == 0 ? -1 : 63 - Long.numberOfLeadingZeros(a ^ b ^ (b - 1)));
}

说明

不知道这与简单的位搜索循环相比是否有效，但您可以使用以下方法来帮助:
Integer.highestOneBit(int i)
Integer.numberOfLeadingZeros(int i)

它们都使用位操作，因此它们需要不到 32 次迭代(如果使用 Long 版本，则需要 64 次迭代)。

给定示例输入值 1101011，我们希望将其反转为 0010100。

请记住，int 有 32 位，因此其左侧有 25 个 0 位，因此要反转它，我们需要与掩码 1111111 进行异或.

可以通过调用 highestOneBit() 计算该掩码，得到 1000000，减去 1 得到 0111111，将它们组合起来得到面具。

完成 XOR 并得到 0010100 后，我们计算 31 - numberOfLeadingZeros() 以找到前导 1 位的位置，即 4 in这个例子。

然后，我们可以定义对于无效输入，我们希望结果为 -1:

• 000 无效，因为最左边的 0 位没有 1 位
• 111 无效，因为 1 位后面没有 0 位

这为我们提供了答案顶部的代码。

测试

public static void main(String[] args) {
    test(0x6B); // example in answer
    test(0x53); // example in question (83)
    test(0x29);
    test(0x14);
    test(0x0A);
    test(0x05);
    test(0x02);
    test(0x01);
    test(0x00);
    test(0x80000000);
    test(0xFFFFFFFE);
}
private static void test(int a) {
    System.out.printf("%32s: %d%n", Integer.toBinaryString(a), leftmostZeroBit(a));
}

输出

                         1101011: 4
                         1010011: 5
                          101001: 4
                           10100: 3
                            1010: 2
                             101: 1
                              10: 0
                               1: -1
                               0: -1
10000000000000000000000000000000: 30
11111111111111111111111111111110: 0