了解Integer.highestOneBit()方法实现背后的逻辑

Question

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

例如，int 17的输入将返回16；因为17可以用二进制表示为10001，所以它将返回等于16的最左边的位。

在整数类中，它在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);
}

我只想知道以这种方式实现它背后的逻辑以及使用 shift 操作背后的逻辑。谁能给它一些启示。

Answer 1

前五行（i|=（i

为了简单起见，让我们假设＜code＞int＜/code＞是8位。在这种情况下，代码如下：

public static int highestOneBit(int i) {
    i |= (i >>  1);
    i |= (i >>  2);
    i |= (i >>  4);
    return i - (i >>> 1);
}

现在，假设我们的值是128（1000000）。这是会发生的情况：

// i == 10000000
i |= (i >>  1); // i = 10000000 | 11000000 = 11000000 
i |= (i >>  2); // i = 11000000 | 11110000 = 11110000 
i |= (i >>  4); // i = 11110000 | 11111111 = 11111111
return i - (i >>> 1); // 11111111 - 01111111 = 10000000

现在，让我们尝试64（01000000）：

// i == 01000000
i |= (i >>  1); // i = 01000000 | 00100000 = 01100000 
i |= (i >>  2); // i = 01100000 | 00011000 = 01111000 
i |= (i >>  4); // i = 01111000 | 00000111 = 01111111
return i - (i >>> 1); // 01111111 - 00111111 = 01000000

Answer 2

i|=语句有助于计算与i长度相同的一系列语句。例如，对于101011，它计算111111。我已经解释了它在这个答案中是如何工作的（我现在无法重新键入它，因为我在移动设备上）。

所以基本上，一旦你有了一串1，减法本身右移一位就得到了H.O.位。

111111 - (111111 >>> 1) = 111111 - 011111 = 100000

Answer 3

该算法计算给定的＜code＞i＜/code＞，其二进制表示为：

0..01XXXXXXX...XXXX

价值

0..011111111...1111

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

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

0..001111111...1111

得到结果

0..010000000...0000

它是如何工作的：

第32位(最左边)可能的最高1位。假设输入数字的该位为1:

1XXXXXXX XXXXXXXX XXXXXXXX XXXXXXXX

您或该值右移1＜code＞（i

11XXXXXX XXXXXXXX XXXXXXXX XXXXXXXX

然后，您或值右移2（i）的新值

1111XXXX XXXXXXXX XXXXXXXX XXXXXXXX

然后您或该值右移4的新值（i

11111111 XXXXXXXX XXXXXXXX XXXXXXXX

然后你或那个新值，该值向右移动了 8 （i

11111111 11111111 XXXXXXXX XXXXXXXX

最后，您或该值右移16 <代码>的新值(I

11111111 11111111 11111111 11111111

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