HashMap.tableSizeFor(...).这段代码如何围绕下一个2的幂？

Question

请描述这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;
}

Answer 1

两个的所有(正)幂正好设置为1位; 和(2的幂)将所有位设置为小于最高有效位.所以,我们可以找到下一个最大的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

因此,我们采取了5次,而不是采取30次操作来设置所有不太重要的位.