时间戳

首页 > 解决方案 > HashMap.tableSizeFor(...)。这段代码如何四舍五入到 2 的下一个幂？

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

问题描述

请描述一下这n| = n >>> x5 行的作用？

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

/**
 * 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;
}

标签： javahashmapbit-manipulationbit-shift

解决方案

2 的所有（正）幂都恰好设置了 1 位；和（2 - 1 的幂）的所有位都设置为小于最高有效位。所以，我们可以找到下一个最大的二的幂

  • 减 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 次。

推荐阅读