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

2 的所有(正)幂都恰好设置了 1 位；并且(2 - 1 的幂)的所有位都设置为小于最高有效位。所以，我们可以通过 找到下一个最大的 2 的幂

• 减去 1
• 设置所有低位
• 加 1

这些位移位操作是通过“涂抹”设置的位来实现此过程的第二步。

所以:

n |= n >>> 1;

会做类似的事情:

  01010000
| 00101000
= 01111000

如果你再次这样做，你会再次“涂抹”数字(仍然只移动 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 次。