共计 2064 个字符，预计需要花费 6 分钟才能阅读完成。
在看 HashMap 源码时，留神到一个问题，容量必须是 2 的整数幂，为了保障这一点，专门给出了一个奇妙而高效的办法 tableSizeFor。无妨想一下，如果是本人解决这个问题，该怎么解决？
给定一个 int 类型的整数 n，如何求出不小于它的最靠近的 2 的整数幂 m，比方给定 10 得出 16，给定 25 得出 32？
普通人的简略粗犷形式
普通人的想法可能比较简单，间接对 n 求以 2 为底的对数，后果 m 是 double 类型，若小数局部为 0，则 m 就是咱们要求的指数；小数局部不为 0，则对 m 向上取整，最初间接求 2 的 m 次幂。
首先遇到的问题是 jdk 没有提供对 2 求对数的数学公式，只有对自然对数 e 求对数的公式Math.log(double a)。
好在咱们能够用对数的换底公式
示例代码
public static int fun(int n) {double m = Math.log(n) / Math.log(2);
int m2 = (int) Math.ceil(m);
return (int) Math.pow(2, m2);
}不思考是否有精度损失，上述代码很简洁，只有三步，求对数 + 取整 + 求指数。
问题
回顾 HashMap 中的需要咱们晓得，这个办法属于很根底的办法，将在初始化或者增加时被大量执行，这就要求办法自身肯定要高效。
这里尽管代码简洁，但调用的办法细看的话代码还是很多的，而且波及到的运算，比方对数，指数，除运算，取整，强制类型转换，都是比拟高级的，必然依附大量的底层简略操作实现。
一个程序运行的工夫除了和环境比方时钟周期的长度和每条指令的均匀时钟周期数无关外，还和 指令数 无关。理性的意识也能通知咱们，上述代码的理论执行的最终指令肯定不会少。
咱们之所有要用这个办法转换为 2 的幂，是为了缩小哈希抵触，进步存取效率，后果这个办法自身重大影响了效率，岂不是拣了芝麻丢了西瓜？
大神的实现
咱们无妨看看 HashMap 的作者是如何实现的。
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;
}第一行很简略，为什么要 - 1 放在最初说，最初一行是两个三目运算符，其中之一操作是 n +1，都很容易了解。要害是两头五步移位加上或运算。
移位的思维
说一下我了解的作者的思维：
2 的整数幂用二进制示意都是最高无效位为 1，其余全是 0，比方十进制 8 和 32，下图只用了一个字节示意。
对任意十进制数转换为 2 的整数幂，后果是这个数自身的 最高无效位的前一位变成 1，最高无效位以及其后的位都变为 0 。
核心思想是，先 将最高无效位以及其后的位都变为 1 ，最初再 +1，就进位到前一位变成 1，其后所有的满 2 变 0。所以要害是 如何将最高无效位前面都变为 1 。
还是用图来示意。这里将十进制的 25 转换为 32。
作者的做法是先移位，再或运算。
右移一位，再或运算，就有两位变为 1；
右移两位，再或运算，就有四位变为 1，，，
最初右移 16 位再或运算，保障 32 位的 int 类型整数最高无效位之后的位都能变为 1.
全过程示意图
本人感觉了解了，然而感觉文章写进去很绕，预计看到这里的你也有这种感觉。这里对整个过程画图示意。
初始值
选取任意 int 类型数字，下图 x 示意不确定 0 或者 1.
咱们目标是将所有的 x 变为 1，如下图
最初 +1，就能进位失去 2 的整数幂。
咱们要做的就是一直通过右移 + 或运算来达到目标。
右移一位 + 或运算
能够看出，右移一位再或运算，有两位变成了 1。
右移二位 + 或运算
右移两位再或运算，有四位变成了 1。
右移四位 + 或运算
右移四位再或运算，有八位变成了 1。
右移八位 + 或运算
右移八位再或运算，有十六位变成了 1。
右移十六位 + 或运算
右移十六位再或运算，留神这里不是三十二位全变，而是最高位前面的全变 1。
后果 +1
能够看出，不论 x 是多少，咱们都能将其转换为 1。而且别离通过 1,2,4,8,16 次转换，不论这个 int 类型值多大，咱们都会将其转换，只是值较小时，可能多做几次无意义操作。
初始容量 -1
之所以在开始移位前先将容量 -1，是为了防止给定容量曾经是 8,16 这样 2 的幂时，不减一间接移位会导致失去的后果比预期大。比方预期 16 失去应该是 16，间接移位的话会失去 32。在上图中就是所有 x 自身曾经是 0 的状况下，不减 1 失去的后果变大了。
总结
回到一开始的问题，这个办法之所以高效，是因为移位运算和或运算都属于比拟底层的操作，代码的数量不会比最终的指令数多，也就是通过几个简略操作实现了咱们的目标。
为啥要专门写一篇文章来解释这个办法，是因为在看这个办法的时候，意识到了一些本来不太在意的问题。通过这个办法，就了解了为啥学计算机要学一些根底的常识，比方二进制的操作，逻辑运算等等，以及为啥一些高级的算法看起来都在解决简略的问题。如果单纯学习可能感觉干燥，但实际上它们都是有大用处的。平时可能看不出来，在一些要害的细节就看出普通人和大神的区别了。
要学的还有很多！
