一個(gè)算法問題

輸入一個(gè)整型n，求大于等于n的最小的2的冪次結(jié)果？
例1：
輸入：15
輸出：16
原因：16等于2的4次冪
例2:
輸入：8
輸出：8
原因：8等于2的3次冪

問題解法

就是HashMap源碼中的tableSizeFor函數(shù)

static final int tableSizeFor(int cap) {
    //part1
    int n = cap - 1;
    //part2
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    //part3
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

代碼解析

為了方便講解，把代碼拆分成三部分，上面代碼中已經(jīng)標(biāo)注。

先看part2

先看part2的移位操作。移位操作因?yàn)椴环衔覀兪M(jìn)制操作常規(guī)思維，所以是大多數(shù)程序員很少使用。但是在Java編程中確是一個(gè)很高效的推薦使用的操作，位運(yùn)算符合計(jì)算機(jī)的習(xí)慣。
假設(shè)一個(gè)整型的二進(jìn)制為1xxxxxxx，1前面全是0，位操作結(jié)果如下：

因?yàn)镴ava中一個(gè)整型占32位，這樣最大無符號(hào)向右移動(dòng)16位之后可以保證，輸入的整型二進(jìn)制數(shù)第一個(gè)1之后的所有為均為1。

再看part1

int n = cap - 1;

移位操作可以保證輸入的整型第一個(gè)1之后的位都是1，即產(chǎn)生與當(dāng)前輸入整型相同位數(shù)的最大值。接下來結(jié)果加1就是所求的結(jié)果。但是有一個(gè)例外，假如輸入的整型本身就是2的冪次結(jié)果，經(jīng)過移位操作后就會(huì)產(chǎn)生比其大的2的冪次結(jié)果，為了避免這種情況對(duì)輸入的整型減1。減1之后對(duì)于非2的冪次的整型數(shù)沒有影響，而對(duì)于2的冪次的整型數(shù)，其位數(shù)會(huì)減少1位，這樣最后結(jié)果加1就是它本身。

例1: 輸入整型數(shù)十進(jìn)制為10
輸入：1010
減1后：1001
移位后：1111
加1后：10000
例2：輸入整型數(shù)十進(jìn)制為8
輸入：1000
減1后：0111
移位后：0111
加1后：1000

最后看part3

return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

n+1是求出最后的結(jié)果，而條件判斷是要保證哈希表最大不要超過設(shè)置的最大容量MAXIMUM_CAPACITY。