在看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失去的后果变大了。
总结
回到一开始的问题，这个办法之所以高效，是因为移位运算和或运算都属于比拟底层的操作，代码的数量不会比最终的指令数多，也就是通过几个简略操作实现了咱们的目标。
为啥要专门写一篇文章来解释这个办法，是因为在看这个办法的时候，意识到了一些本来不太在意的问题。通过这个办法，就了解了为啥学计算机要学一些根底的常识，比方二进制的操作，逻辑运算等等，以及为啥一些高级的算法看起来都在解决简略的问题。如果单纯学习可能感觉干燥，但实际上它们都是有大用处的。平时可能看不出来，在一些要害的细节就看出普通人和大神的区别了。
要学的还有很多！