HashMap.tableSizeFor(...)。这段代码如何舍入到下一个 2 的幂？

Question

请描述这 n| = n >>> x 5 行的作用？

我对 | 或 >>> 操作员的工作不感兴趣。我对复杂逻辑在数学语言中的作用很感兴趣。

/**
 * Returns a power of two size for the given target capacity.
 */
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

Answer 1

为了理解这个过程，我们假设传递的 cap 值为 10。

所以n = capacity - 1 = 9; 0000 1001

n |= n >>> 1   = 0000 1101
n |= n >>> 2   = 0000 1111
n |= n >>> 4   = 0000 1111
n |= n >>> 8   = 0000 1111
n |= n >>> 16  = 0000 1111 = 15

最后方法returnsn + 1 = 16

对于大数字

cap           = 0000 1000 0000 0000 0000 0000 0000 0001
n = cap - 1   = 0000 1000 0000 0000 0000 0000 0000 0000
n |= n >>> 1  = 0000 1100 0000 0000 0000 0000 0000 0000
n |= n >>> 2  = 0000 1111 0000 0000 0000 0000 0000 0000
n |= n >>> 4  = 0000 1111 1111 0000 0000 0000 0000 0000
n |= n >>> 8  = 0000 1111 1111 1111 1111 0000 0000 0000
n |= n >>> 16 = 0000 1111 1111 1111 1111 1111 1111 1111
return n + 1  = 0001 0000 0000 0000 0000 0000 0000 0000

Answer 2

2 的所有（正）幂正好设置了 1 位；并且（2 - 1 的幂）的所有位都设置为小于最高有效位。所以，我们可以通过

找到下一个最大的2次方

减 1
设置所有低位
加 1 回来

这些位移位操作是通过 "smearing" 设置的位来实现此过程的第二步。

所以：

n |= n >>> 1;

会做类似的事情：

  01010000
| 00101000
= 01111000

如果你再次这样做，你 "smear" 数字再次下降（仍然只移动 1）：

  01111000
| 00111100
= 01111100

继续这样做，您最终会得到一个设置了所有低位的数字：

01111111

在最坏的情况下，当最高有效位是第 31 位时，您必须执行此操作 30 次（对于带符号的 32 位正整数）：

   01xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
=> 011xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
=> 0111xxxxxxxxxxxxxxxxxxxxxxxxxxxx
=> 01111xxxxxxxxxxxxxxxxxxxxxxxxxxx
=> 011111xxxxxxxxxxxxxxxxxxxxxxxxxx
...
=> 01111111111111111111111111111111

(x 只是表示它可以是零或一)

但是您可能会注意到一些有趣的事情：在第一次涂抹之后，当移位 1 时，我们设置了两个最高有效位。因此，我们可以通过移动 2 来跳过操作，而不是移动 1：

   01xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
=> 011xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
=> 01111xxxxxxxxxxxxxxxxxxxxxxxxxxx

继续此模式，下一个移动 4：

=> 011111111xxxxxxxxxxxxxxxxxxxxxxx

平移 8：

=> 01111111111111111xxxxxxxxxxxxxxx

移位 16：

=> 01111111111111111111111111111111

所以，我们没有用 30 次操作来设置所有低位，而是用了 5 次。

HashMap.tableSizeFor(...)。这段代码如何舍入到下一个 2 的幂？

HashMap.tableSizeFor(...). How does this code round up to the next power of 2?

java

bit-manipulation

hashmap

bit-shift