（1）简介
从现代计算机中所有的数据二进制的形式存储在设备中。即0、1两种状态，
计算机对二进制数据进行的运算(+、-、*、/)都是叫位运算，即将符号位共同参与运算的运算。
我们每一种语言最终都会通过编译器转换成机器语言来执行，
所以直接使用底层的语言就不需要便编译器的转换工作从而得到更高的执行效率，当然可读性可能会降低，
这也是为什么汇编在大部分情况下有更快的速度。项目中合理的运用位运算能提高我们代码的执行效率
位运算符
（1）取反（NOT）
取反是一元运算符，对一个二进制数的每一位执行逻辑反操作。使数字1成为0，0成为1。例如：
NOT 0111（十进制7）
= 1000（十进制8）
许多程序设计语言（包括C程序设计语言family），取反操作符用波浪线"~"表示。
值得注意的是此操作符与"逻辑非（!）"操作符不同。在C++中，
逻辑非将数字整体看做一个布尔类型--将真值转化为假，将假值转化为真；而C语言将0转化为1，
将非零值转化为0。"逻辑非"并不是一个位操作。
（2）按位或（OR）
按位或处理两个长度相同的二进制数，两个相应的二进位中只要有一个为1，该位的结果值为1。例如
0101（十进制5）
OR 0011（十进制3）
= 0111（十进制7）
在C类程序设计语言中，按位或操作符是"|"。这一操作符需要与逻辑或运算符（||）区别开来。
按位或能够将每一位看做旗帜；在二进制数中的每一位可以表示不同的布尔变量。
应用按位或操作可以将二进制数的某一位设为1。例如
0010（十进制2）
能够看做包含4个旗帜的组合。第1，2，4旗帜为0；第3个旗帜为1。
利用按位或可以将第1个旗帜设置为1，而其他旗帜不变。
0010（十进制2）
OR 1000（十进制8）
= 1010（十进制10）
这一技巧通常用来保存程序中的大量布尔变量。
（3）按位异或（XOR）
按位异或运算，对等长二进制模式或二进制数的每一位执行逻辑异或操作。操作的结果是如果某位不同则该位为1，否则该位为0。例如
0101
XOR 0011
= 0110
在类C语言中，按位异或运算符是"^"。
汇编语言的程序员们有时使用按位异或运算作为将寄存器的值设为0的捷径。
用值的自身对其执行按位异或运算将得到0。并且在许多架构中，与直接加载0值并将它保存到寄存器相比，
按位异或运算需要较少的中央处理单元时钟周期。
按位异或也可以用于在比特集合中切换旗帜。给出一个比特模式，
0010
第一和第三位能够通过按位异或运算使用同时切换。
0010
XOR 1010
= 1000
这一技巧可用于操作表示布尔变量的比特模式。
（4）按位与（AND）
按位与处理两个长度相同的二进制数，两个相应的二进位都为1，该位的结果值才为1，否则为0。例如：
0101
AND 0011
= 0001
在类C语言中，按位与用'&'表示
（5）移位
移位是一个二元运算符，用来将一个二进制数中的每一位全部都向一个方向移动指定位，
溢出的部分将被舍弃，而空缺的部分填入一定的值。
在类C语言中，左移使用两个小于符号"<<"表示，右移使用两个大于符号">>"表示。
无符号右移>>>运算符，高位都补0
（2）位运算技巧
下面1s和0s代表一连串1和0
x ^ 1s = ~x; x & 1s = 1; x | 1s = 1;
x ^ 0s = x; x & 0s = 0; x | 0s = x;
x ^ x = 0; x & x = x; x | x = x;
（3）java位运算
Java位运算是针对于整型数据类型的二进制进行的移位操作。主要包括位与、位或、位非，有符号左移、有符号右移，无符号右移等等。不存在无符号左移<<<运算符。Java整型数据类型有：byte、char、short、int、long。它们的字节占用数如下：
数据类型 所占位数
byte 8
boolean 8
short 16
int 32
long 64
float 32
double 64
char 16
计算机表示数字正负不是用+ -加减号来表示，而是用最高位数字来表示，0表示正，1表示负
所以比如-4
4二进制：0100
反码：1111 1111 1111 1111 1111 1111 1111 1011
原码表示就是1011+1==1111 1111 1111 1111 1111 1111 1111 1100
（4）用途
1、java8 HashMap
/**
* Returns a power of two size for the given target capacity.
*/
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==65，执行过程如下
cap - 1;// n=1000000(二进制)
n|=n>>>1;//n=n|(n>>>1)=1000000|100000=1100000
n|=n>>>2;//n=n|(n>>>2)=1100000|11000=1111000
n|=n>>>4;//n=n|(n>>>4)=1111000|11110=1111111
n|=n>>>8;//n=n|(n>>>8)=1111111|111=1111111
n|=n>>>16;//n=n|(n>>>16)=1111111|0=1111111
n+1:1111111+000001=1000000==64,是2的6次方
1.1、扩展：为啥哈希桶数组table的长度length大小必须为2的n次方（tableSizeFor（）方法）
假如指定了容量且不是2的幂，实际容量会是最接近(大于)指定容量的2的幂，
比如 new HashMap<>(19)，比19大且最接近的2的幂是32，实际容量就是32。
HashMap采用这种非常规设计，主要是为了在取模和扩容时做优化，同时为了减少冲突，
HashMap定位哈希桶索引位置时，也加入了高位参与运算的过程。
1.1.1、取模优化的具体原理：
//java8中hashMap散列值函数
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
static int indexFor(int h, int length) { //jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的
return h & (length-1); // 取模运算
}
1.1.1.1、取模运算
key.hashCode()函数调用的是key键值类型自带的哈希函数，返回int型散列值。
散列值是一个int型，如果直接拿散列值作为下标访问HashMap主数组的话，而2进制32位带符号的int表值范围从-2147483648到2147483648。
前后加起来大概2的32次方>40亿的映射空间。只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。
但是一个超过40亿长度的数组，内存是放不下的，所以用之前还要先做对数组的长度取模运算，得到的余数才能用来访问数组下标。
模运算如下：
int index =hash% length;
但是hashmap不这样做，而是采用&
h & (length-1);
这样做的原理是啥？
由于计算机是底层的运算是基于2进制的，&比%具有更高的效率,h& (length-1)运算等价h%length
HashMap的数组长度取2的整次幂。所以（数组长度-1）正好相当于一个“低位掩码”。“与”操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。以初始长度16为例，16-1=15。2进制表示是00000000 00000000 00001111。和某散列值做“与”操作如下，结果就是截取了最低的四位值。
10100101 11000100 00100101
& 00000000 00000000 00001111
----------------------------------
00000000 00000000 00000101 //高位全部归零，只保留末四位，最后下标为5
所以这就是HashMap的数组长度取2的整次幂的原因
1.1.1.2、java8中hashMap散列值函数
上面提到获取key的哈希值，直接通过key.hashCode()不行吗，为啥还要：
(h = key.hashCode()) ^ (h >>> 16);
原理
下图：n为table的长度。
由于 h>>>16，高16bit 补0，一个数和0异或不变，所以 hash 函数大概的作用就是：高16bit不变，低16bit和高16bit做了一个异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。这是设计者从速度、功效、质量来考虑的。经过’扰乱‘后可以大大的减少碰撞
1.1.2扩容优化
e.hash & oldCap
resize()用来第一次初始化，或者 put 之后数据超过了threshold后扩容
数组下标计算： index = (table.length - 1) & hash ，由于 table.length 也就是capacity 肯定是2的N次方，使用 & 位运算意味着只是多了最高位，这样就不用重新计算 index，元素要么在原位置，要么在原位置+ oldCapacity。
如果增加的高位为0，resize 后 index 不变，如图所示：
如果增加的高位为1，resize 后 index 增加 oldCap，如图所示：
例子：
初始容量为16，那么15转换为二进制数位1111，现在进行一次扩容之后容量变为32，那么31转换为2进制是为11111。现有两个key，一个hashcode为107转换为二进制数后为1101011，另一个的hashcode是379转换为二进制数后为101111011。在容量为16的时候，这两个key，具体计算索引过程为：
0001111 & 1101011 = 1011
000001111 & 101111011 = 1011 转换为10进制数后都为11。
现在来看一下扩容之后两个key的索引：
0011111 & 1101011 = 1011
000011111 & 101111011 = 11011 一个对应的索引仍然是11，而另一个却变为27（27 = 11+16）
因此，HashMap数组的扩容的整体思想就是创建一个长度为原先2倍的数组。然后对原数组进行遍历和复制。只不过jdk1.8对扩容进行优化，使得扩容不再需要进行链表的反转，只需要知道hashcode新增的bit位为0还是1。如果是0就在原索引位置，新增索引是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图：
这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。
2、byte & 0xff
java中byte转换int时为何与0xff进行与运算？
举个简单的例子:
byte[] b = new byte[5];
b[0] = -12;
-12 的绝对值原码是：0000 1100 取反： 1111 0011 加1： 1111 0100
byte --> int 就是由8位变 32 位
高24位全部补1： 1111 1111 1111 1111 1111 1111 1111 0100 ;
0xFF 是计算机十六进制的表示： 0x就是代表十六进制，A B C D E F 分别代表10 11 12 13 14 15 F就是15 一个F 代表4位二进制。则0xFF的二进制表示就是：1111 1111。
高24位补0：0000 0000 0000 0000 0000 0000 1111 1111;
-12的补码与0xFF 进行与（&）操作 最后就是0000 0000 0000 0000 0000 0000 1111 0100
转换为十进制就是 244。
byte类型的数字要&0xff再赋值给int类型，其本质原因就是想保持二进制补码的一致性。
当byte要转化为int的时候，高的24位必然会补1，这样，其二进制补码其实已经不一致了，&0xff可以将高的24位置为0，低8位保持原样。这样做的目的就是为了保证二进制数据的一致性。
3、获取
public void getBit() {
int num = 12;
int i = 3;
System.out.println((num & (1 << i))!=0);
}
该方法把1向左移动i位，为01000，num&01000，从而将除i位以外都清0，如果num的i位为1，则返回true。常用的用法是：利用位运算来判断数据是否重复，如果num数组该位为1，说明位数组已经存储了该元素，重复了
4、置位
public void setBit() {
int num = 12;
int i = 3;
System.out.println(num | (1 << i));
}
该方法把1向左移动i位，为01000，num | 01000，将num的i位置位1，只会改变i位，其他位没变化。常用的用法：存储数据
例如：
//判断是否有重复的字符
public boolean isUniqueChar() {
String str = "dddsdssd";
int charer = 0;
for (int i = 0; i < str.length(); i++) {
int val = str.charAt(i) - 'a';
if ((charer & (1 << val)) != 0) {
return false;
}
charer |= 1 << val;
}
return true;
}
5、清零
5.1、只清零i位
public void clearBit() {
//将i位清零
int num = 12;
int i = 3;
int mask = ~(1 << i);
System.out.println(num & mask);
}
该方法先将1 << i==01000取反为：10111，num&10111，只会清零i位，其他位不变
5.1、将最高至i位（含）清零
public void clearBit1() {
//将高位到i位(含)清零
int num = 12;
int i = 3;
int mask = (1 << i)-1;
System.out.println(num & mask);
}
1 << i==00001000（8），-1后变成00000111（7），
num&mask == 00001100& 00000111：00000100
也就是把num（00001100）的00001清零
5.1、将i位到0（含）清零
public void clearBit2() {
//将i位到0位（含）清零
int num = 12;
int i = 3;
int mask = ~((1 << (i+1))-1);
System.out.println(num&mask);
}
1 << (i+1) ：00010000（16），(1 << (i+1))-1：00001111（15），
~((1 << (i+1))-1)：11111111111111111111111111110000
num&mask：00001100 & 11111111111111111111111111110000：0
也就是把00001100的1100清零
6、更新
public void updateBit() {
//将i位到0位（含）清零
int num = 12;
int i = 3;
int v = 2;
int mask = ~(1 << i);
System.out.println((num & mask) | (v<<i));
}
该方法是clearBit和setBit结合。
1<<i：00001000
~(1 << i)：11111111111111111111111111110111
num & mask：00001100 &11111111111111111111111111110111==100
v<<i：10000，将v（0010）左移i位，得到一个i位为v，其余位为0
(num & mask) | (v<<i)：100|10000==10100
v为1则num的i位更新为1，否则为0
7、1 << 30
1无符号左移30位，也就是二进制1后面跟着30个0，int类型最大值，正数高位补零
0100 0000 0000 0000 0000 0000 0000 0000
8、9>>> 1
大于9 的一半，结果为4
