Java位运算及HashMap的tableSizeFor方法

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
  例子：

  1. -10 >> 1 = -5
  2. 10 >> 1 = 5
  3. -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的整数次幂