JAVA 位运算基础
首先在进行位运算之前先讲一下JAVA 的基础知识点(可跳过)：
- 首先java中的一个int 是四个字节，一个字节八位，那么一个int 是32位数（第一位为符号位不计算）
- java 的负数存储是以补码的形式存储的（补码=反码+1 ，以10的二进制来1010来说，反码0101，补码0110），高位以1存储。所以-10在java中的存储是：1.忽略26个.110110, 那么10就是：0忽略26个01010
在Java中有两种的位移操作，就是：>> ,<< , >>>
-
有符号又移位 >>
将二进制整体向右位移一定的位数，负数的高位使用1补齐，正数高位使用0补齐。
n >> 1 等同于除以2 ，但是无论位移多少位数最小的数值都是 ±1
例子：- -10 >> 1 = -5
- 10 >> 1 = 5
- -10 >>10 = -1
有符号左位移<<
整体位数向左移动一定的位数，低位以0补齐。
例子：无符号的位移 >>>
整数向右位移，无论正负数，高位都以0补齐。
例子：-10的二进制 11...110110
-10>>>1 的操作实际上结果为：01111..1011 = Integer.MAX_VALUE -4 = 2147483643
JAVA HashMap.tableSizeFor(int cap) 详解
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;}
以上的代码 的意思是对于任何一个输入 cap 都将返回最近的2的整数次幂的数。
如： 假设入参cap 的二进制为 100111010..(省略)
操作1：n|=n>>>1
n = 100111010..(省略) | 010011101..(省略)
n 为 110011101..(省略)
操作2：n|=n>>>2
n =110011101..(省略) | 001100111..(省略)
ps:在操作2前，n的前两位已经为1了，所以操作2之后的n 为 111100111..(省略)
操作3：n|=n>>>4
n = 111100111..(省略) | 000011110..(省略)
ps:以同样的方式，将前八位都都置1 ，最终n 为 111111110..(省略)
在这几步的位运算之后，入参 cap 的二进制最高位1后也都全部置为1了
return前将 n +1，得到的就是 最近的 2的整数次幂
