java - 检查数字的二进制表示形式中所有设置位后仅跟随未设置位的最佳方法

Question

您能否告诉我有没有最好的方法可以找到这个数字的二进制表示中设置位后面仅跟随未设置的位，例如 -4 - 1006 - 1108 - 100012 - 1100

private static boolean setBitFollowedByUnsetBits(int num) {
    String str = Integer.toBinaryString(num);
    int len = str.length();
    int countof1 = str.indexOf('0');
    int lastIndOf0 = str.lastIndexOf('0');
    int countof0 = lastIndOf0 -countof1;
    int lastIndOf1 = str.lastIndexOf('1');

    if((!(lastIndOf1 > countof1) && (lastIndOf1 < lastIndOf0))) {
        return ((num >> countof0+1)==((2 << countof1-1)-1));
    }   
    return false;
}

这就是我编写的逻辑，但我正在寻找更有效的更好的解决方案。

Answer 1

详细说明@Alberto 的提示:

您正在寻找像 0000 0000 0111 1111 1100 0000 0000 0000 这样的位模式(我假设是 32 位整数):

• 一些前导零位(没有也可以)
• 一个 1 位 block (至少一个)
• 一个零位 block (至少一个)

特殊情况可以是全零位(N==0)，或以一位结尾的数字(没有尾随零位)。我们首先看一下一般情况:

如果有一个二进制数，如 N=xxxx1000，则 N-1 为 xxxx0111，将所有尾部零位替换为一位，将最右边的一位替换为零位，并保持高位不变。

将 N 与 N-1 进行“或”运算，如 int K = N | (N-1);用一位替换尾随的零位:

N   = xxxx1000
N-1 = xxxx0111
      --------
K   = xxxx1111

我们希望 xxxx 部分类似于 0001。现在，让我们反转 K:

~K  = yyyy0000

其中 yyyy 是 xxxx 的按位逆，应该看起来像 1110。因此，我们可以再次检查尾随零位并将其设置为 int L = (~K) | ((~K)-1); 。如果原始数字中只有一个 1 block ，那么结果现在应该是全 1 位。

现在是特殊情况:

• 如果 N 中根本没有一位，则结果也将给出全 1。由于缺少一位 block ，结果应该是 false，需要特殊处理。

• 仅由一组 1 组成的数字也将得到全 1。但由于缺少尾随零位，它应该返回 false，也需要特殊处理，只需查看最后一位是否为零。

所以代码如下:

private static boolean setBitFollowedByUnsetBits(int num) {
    if (num == 0) return false;
    if ((num & 1) == 1) return false;
    int invK = ~ (num | (num-1));
    int indicator = invK | (invK-1);
    return indicator == 0xffffffff;
}