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

Question

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

    int a = 83

例如83的二进制是1010011所以最左边的位0的位置是第6位。请问有没有办法只用位运算符求答案？

Answer 1

据我所知，您可以使用按位运算符，但单独使用是不行的。您必须使用条件运算符来获取输出，因为程序必须从右到左检查最后一次出现的 0 或从左到右第一次出现的 0。

Answer 2

你可以这样做：

    int a = 83
    int mask = 1;
    // This loop finds the leftmost 1 bit
    while(a > mask) 
        mask <<= 1;
    mask >>= 1;
    // This loop starts from the leftmost 1 bit and searches for the first 0 going right
    while((a & mask) != 0) 
        mask >>= 1;

    System.out.println(Math.log(mask) / Math.log(2) + 1); // 6

最后"log"部分是必须给出最左边0位的位置索引

Answer 3

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.[=30 进行异或运算=]

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

完成 XOR 并得到 0010100 后，我们计算 31 - numberOfLeadingZeros() 以找到前导 1 位的位置，在本例中为 4。

然后我们可以定义我们希望结果为 -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

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

get position of leftmost 0 bit of a number

java

bitwise-operators