一个算法问题

输入一个整型n，求大于等于n的最小的2的幂次结果？
例1：
输入：15
输出：16
原因：16等于2的4次幂
例2:
输入：8
输出：8
原因：8等于2的3次幂

问题解法

就是HashMap源码中的tableSizeFor函数

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

代码解析

为了方便讲解，把代码拆分成三部分，上面代码中已经标注。

先看part2

先看part2的移位操作。移位操作因为不符合我们十进制操作常规思维，所以是大多数程序员很少使用。但是在Java编程中确是一个很高效的推荐使用的操作，位运算符合计算机的习惯。
假设一个整型的二进制为1xxxxxxx，1前面全是0，位操作结果如下：

因为Java中一个整型占32位，这样最大无符号向右移动16位之后可以保证，输入的整型二进制数第一个1之后的所有为均为1。

再看part1

int n = cap - 1;

移位操作可以保证输入的整型第一个1之后的位都是1，即产生与当前输入整型相同位数的最大值。接下来结果加1就是所求的结果。但是有一个例外，假如输入的整型本身就是2的幂次结果，经过移位操作后就会产生比其大的2的幂次结果，为了避免这种情况对输入的整型减1。减1之后对于非2的幂次的整型数没有影响，而对于2的幂次的整型数，其位数会减少1位，这样最后结果加1就是它本身。

例1: 输入整型数十进制为10
输入：1010
减1后：1001
移位后：1111
加1后：10000
例2：输入整型数十进制为8
输入：1000
减1后：0111
移位后：0111
加1后：1000

最后看part3

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

n+1是求出最后的结果，而条件判断是要保证哈希表最大不要超过设置的最大容量MAXIMUM_CAPACITY。