java - 了解 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

值(value)

0..011111111...1111

这就是 5 个 |= 运算符所做的。

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

0..001111111...1111

得到结果

0..010000000...0000

它是如何工作的:

第 32(最左边)位可能的最高 1 位。假设输入数字的那个位是 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。