一段神奇的算法

閱讀hashmap源碼時(shí)，看到了一段神奇的代碼，如下所示：

static final int tableSizeFor(int cap) {
    int n = cap - 1; // step 1
    n |= n >>> 1; // step 2
    n |= n >>> 2; // step 3
    n |= n >>> 4; // step 4
    n |= n >>> 8; // step 5
    n |= n >>> 16; // step 6
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; // step 7
}

這段代碼啥意思呢？這段代碼是初始化容量時(shí)會調(diào)用的，用于計(jì)算擴(kuò)容閾值。
這段代碼的目的是為了計(jì)算大于等于cap的最小2的冪，如cap=2，輸出2；cap=3，輸出4；cap=17，輸出32。

科普：

n >>> 1：是無符號右位移運(yùn)算，向右位移1位，左邊補(bǔ)0；
n |= n：位或運(yùn)算，0 | 0 = 0；0 | 1 = 1；1 | 1 = 1；1 | 0 = 1。即只要有1則為1。

以下以cap=121為例：
step 1：n = 120
step 2：
120的二進(jìn)制形式為：0111 1000
n >>> 1：0011 1100
n |= n：
0111 1000
0011 1100
——————————————————
0111 1100
輸出：n = 124
step 3：
124的二進(jìn)制形式為：0111 1100
n >>> 2：0001 1111
n |= n：
0111 1100
0001 1111
——————————————————
0111 1111
輸出：n = 127
step 4：
124的二進(jìn)制形式為：0111 1111
n >>> 4：0000 0111
n |= n：
0111 1111
0000 0111
——————————————————
0111 1111
輸出：n = 127
step 5：
124的二進(jìn)制形式為：0111 1111
n >>> 8：0000 0000
n |= n：
0111 1111
0000 0000
——————————————————
0111 1111
輸出：n = 127
step 6：
124的二進(jìn)制形式為：0111 1111
n >>> 16：0000 0000
n |= n：
0111 1111
0000 0000
——————————————————
0111 1111
輸出：n = 127
step 7：127 > && 127 < MAXIMUM_CAPACITY，輸出最終結(jié)果：128

此算法巧妙的地方在于，cap的最高位肯定是1，第一次向右位移1位后，再與原值進(jìn)行位或操作，結(jié)果是最高的兩位是1。接著向右位移2位再位或，得到最高的四位是1。同理，將得到一連串的1，即為結(jié)果。

至于step 1為何要先減去1，目的在于保證結(jié)果是大于等于cap的最小2的n次冪。如cap為8，預(yù)期的輸出也應(yīng)該為8。若不先減去1，則將輸出16，與預(yù)期不符。