时间戳

首页 > 解决方案 > 理解 Integer.highestOneBit() 方法实现背后的逻辑

java - 理解 Integer.highestOneBit() 方法实现背后的逻辑

问题描述

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

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

在 Integer 类中，它在 Java doc 中有以下实现。

    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);
}

我只想知道以这种方式实现它的逻辑以及使用移位操作背后的逻辑。任何人都可以对此有所了解。

标签： javabit

解决方案

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

0..01XXXXXXX...XXXX

价值

0..011111111...1111

这就是 5 个|=操作员所做的。

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

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。

推荐阅读