了解Integer.highestOneBit（）方法实现背后的逻辑

Question

Java Integer类具有静态方法highestOneBit方法，该方法将在指定值的最高位一位的位置返回一个单个一位的值；如果指定值本身等于零，则返回零。

例如，int 17的输入将返回16；由于17可以二进制表示为10001，因此它将返回剩下的最远的一位，等于16。

在Integer类中，它在Java文档中具有以下实现。

    public static int highestOneBit(int i) {
    // HD, Figure 3-1
    i |= (i >>  1);
    i |= (i >>  2);
    i |= (i >>  4);
    i |= (i >>  8);
    i |= (i >> 16);
    return i - (i >>> 1);
}

我只想知道以这种方式实现它的逻辑以及使用移位操作的逻辑。谁能给它一点点光。

Answer 1

该算法针对给定i的二进制表示为：

0..01XXXXXXX...XXXX

价值

0..011111111...1111

这就是5位|=操作员的工作。

然后，在return语句中，从中减去右移一位的值

0..001111111...1111

得到结果

0..010000000...0000

它是如何工作的：

最高的1位是第32位（最左侧）。假设输入数字在该位中为1：

1XXXXXXX XXXXXXXX XXXXXXXX XXXXXXXX

您或那个值右移1 (i >> 1)并得到

11XXXXXX XXXXXXXX XXXXXXXX XXXXXXXX

然后您或该新值的值右移2 (i >> 2)并得到

1111XXXX XXXXXXXX XXXXXXXX XXXXXXXX

然后，您或该新值的值右移4 (i >> 4)并得到

11111111 XXXXXXXX XXXXXXXX XXXXXXXX

然后，您或该新值的值右移8 (i >> 8)并得到

11111111 11111111 XXXXXXXX XXXXXXXX

最后，您或该新值的值向右移16 (i >> 16)并得到

11111111 11111111 11111111 11111111

如果最高的1位小于第32位，则这些操作仍会将其右边的所有位都设为1，并使其余（较高的位）保持为0。