（1）簡(jiǎn)介
從現(xiàn)代計(jì)算機(jī)中所有的數(shù)據(jù)二進(jìn)制的形式存儲(chǔ)在設(shè)備中撕贞。即0测垛、1兩種狀態(tài)，
計(jì)算機(jī)對(duì)二進(jìn)制數(shù)據(jù)進(jìn)行的運(yùn)算(+脊奋、-疙描、*、/)都是叫位運(yùn)算久又，即將符號(hào)位共同參與運(yùn)算的運(yùn)算。
我們每一種語(yǔ)言最終都會(huì)通過(guò)編譯器轉(zhuǎn)換成機(jī)器語(yǔ)言來(lái)執(zhí)行地消，
所以直接使用底層的語(yǔ)言就不需要便編譯器的轉(zhuǎn)換工作從而得到更高的執(zhí)行效率脉执，當(dāng)然可讀性可能會(huì)降低，
這也是為什么匯編在大部分情況下有更快的速度婆廊。項(xiàng)目中合理的運(yùn)用位運(yùn)算能提高我們代碼的執(zhí)行效率
位運(yùn)算符
（1）取反（NOT）
取反是一元運(yùn)算符巫橄，對(duì)一個(gè)二進(jìn)制數(shù)的每一位執(zhí)行邏輯反操作湘换。使數(shù)字1成為0，0成為1彩倚。例如：
NOT 0111（十進(jìn)制7）
= 1000（十進(jìn)制8）
許多程序設(shè)計(jì)語(yǔ)言（包括C程序設(shè)計(jì)語(yǔ)言family）帆离，取反操作符用波浪線"~"表示。
值得注意的是此操作符與"邏輯非（!）"操作符不同。在C++中概而，
邏輯非將數(shù)字整體看做一個(gè)布爾類型--將真值轉(zhuǎn)化為假，將假值轉(zhuǎn)化為真赎瑰；而C語(yǔ)言將0轉(zhuǎn)化為1，
將非零值轉(zhuǎn)化為0压储。"邏輯非"并不是一個(gè)位操作源譬。
（2）按位或（OR）
按位或處理兩個(gè)長(zhǎng)度相同的二進(jìn)制數(shù)踩娘，兩個(gè)相應(yīng)的二進(jìn)位中只要有一個(gè)為1，該位的結(jié)果值為1雷绢。例如
0101（十進(jìn)制5）
OR 0011（十進(jìn)制3）
= 0111（十進(jìn)制7）
在C類程序設(shè)計(jì)語(yǔ)言中翘紊，按位或操作符是"|"。這一操作符需要與邏輯或運(yùn)算符（||）區(qū)別開(kāi)來(lái)鹉究。
按位或能夠?qū)⒚恳晃豢醋銎鞄醚炱ィ辉诙M(jìn)制數(shù)中的每一位可以表示不同的布爾變量。
應(yīng)用按位或操作可以將二進(jìn)制數(shù)的某一位設(shè)為1匿级。例如
0010（十進(jìn)制2）
能夠看做包含4個(gè)旗幟的組合痘绎。第1孤页，2涩馆，4旗幟為0；第3個(gè)旗幟為1蛾号。
利用按位或可以將第1個(gè)旗幟設(shè)置為1鲜结，而其他旗幟不變精刷。
0010（十進(jìn)制2）
OR 1000（十進(jìn)制8）
= 1010（十進(jìn)制10）
這一技巧通常用來(lái)保存程序中的大量布爾變量蔗候。
（3）按位異或（XOR）
按位異或運(yùn)算锈遥，對(duì)等長(zhǎng)二進(jìn)制模式或二進(jìn)制數(shù)的每一位執(zhí)行邏輯異或操作仰美。操作的結(jié)果是如果某位不同則該位為1咖杂，否則該位為0诉字。例如
0101
XOR 0011
= 0110
在類C語(yǔ)言中壤圃，按位異或運(yùn)算符是"^"琅轧。
匯編語(yǔ)言的程序員們有時(shí)使用按位異或運(yùn)算作為將寄存器的值設(shè)為0的捷徑。
用值的自身對(duì)其執(zhí)行按位異或運(yùn)算將得到0冲杀。并且在許多架構(gòu)中权谁，與直接加載0值并將它保存到寄存器相比旺芽，
按位異或運(yùn)算需要較少的中央處理單元時(shí)鐘周期辐啄。
按位異或也可以用于在比特集合中切換旗幟壶辜。給出一個(gè)比特模式，
0010
第一和第三位能夠通過(guò)按位異或運(yùn)算使用同時(shí)切換。
0010
XOR 1010
= 1000
這一技巧可用于操作表示布爾變量的比特模式翩活。
（4）按位與（AND）
按位與處理兩個(gè)長(zhǎng)度相同的二進(jìn)制數(shù)菠镇，兩個(gè)相應(yīng)的二進(jìn)位都為1，該位的結(jié)果值才為1蚌本，否則為0。例如：
0101
AND 0011
= 0001
在類C語(yǔ)言中程癌，按位與用'&'表示
（5）移位
移位是一個(gè)二元運(yùn)算符，用來(lái)將一個(gè)二進(jìn)制數(shù)中的每一位全部都向一個(gè)方向移動(dòng)指定位进萄，
溢出的部分將被舍棄中鼠，而空缺的部分填入一定的值沿癞。
在類C語(yǔ)言中，左移使用兩個(gè)小于符號(hào)"<<"表示惫搏，右移使用兩個(gè)大于符號(hào)">>"表示晶府。
無(wú)符號(hào)右移>>>運(yùn)算符钻趋，高位都補(bǔ)0
（2）位運(yùn)算技巧
下面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位運(yùn)算
Java位運(yùn)算是針對(duì)于整型數(shù)據(jù)類型的二進(jìn)制進(jìn)行的移位操作蛮位。主要包括位與、位或尸曼、位非萄焦，有符號(hào)左移拂封、有符號(hào)右移，無(wú)符號(hào)右移等等在抛。不存在無(wú)符號(hào)左移<<<運(yùn)算符萧恕。Java整型數(shù)據(jù)類型有：byte、char朴读、short磨德、int、long酥宴。它們的字節(jié)占用數(shù)如下：
數(shù)據(jù)類型 所占位數(shù)
byte 8
boolean 8
short 16
int 32
long 64
float 32
double 64
char 16
計(jì)算機(jī)表示數(shù)字正負(fù)不是用+ -加減號(hào)來(lái)表示拙寡，而是用最高位數(shù)字來(lái)表示肆糕，0表示正在孝，1表示負(fù)
所以比如-4
4二進(jìn)制：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次冪的整數(shù)
假如cap==65始赎，執(zhí)行過(guò)程如下
cap - 1;// n=1000000(二進(jìn)制)
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造垛、擴(kuò)展：為啥哈希桶數(shù)組table的長(zhǎng)度length大小必須為2的n次方（tableSizeFor（）方法）
假如指定了容量且不是2的冪五辽，實(shí)際容量會(huì)是最接近(大于)指定容量的2的冪杆逗，
比如 new HashMap<>(19)鳞疲，比19大且最接近的2的冪是32建丧，實(shí)際容量就是32波势。
HashMap采用這種非常規(guī)設(shè)計(jì)橄维，主要是為了在取模和擴(kuò)容時(shí)做優(yōu)化争舞，同時(shí)為了減少?zèng)_突澈灼，
HashMap定位哈希桶索引位置時(shí)，也加入了高位參與運(yùn)算的過(guò)程委乌。
1.1.1荣回、取模優(yōu)化的具體原理：
//java8中hashMap散列值函數(shù)
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沒(méi)有這個(gè)方法删铃，但是實(shí)現(xiàn)原理一樣的
return h & (length-1); // 取模運(yùn)算
}
1.1.1.1、取模運(yùn)算
key.hashCode()函數(shù)調(diào)用的是key鍵值類型自帶的哈希函數(shù)咒劲，返回int型散列值缎患。
散列值是一個(gè)int型挤渔，如果直接拿散列值作為下標(biāo)訪問(wèn)HashMap主數(shù)組的話风题，而2進(jìn)制32位帶符號(hào)的int表值范圍從-2147483648到2147483648沛硅。
前后加起來(lái)大概2的32次方>40億的映射空間摇肌。只要哈希函數(shù)映射得比較均勻松散，一般應(yīng)用是很難出現(xiàn)碰撞的昵骤。
但是一個(gè)超過(guò)40億長(zhǎng)度的數(shù)組，內(nèi)存是放不下的成榜，所以用之前還要先做對(duì)數(shù)組的長(zhǎng)度取模運(yùn)算赎婚，得到的余數(shù)才能用來(lái)訪問(wèn)數(shù)組下標(biāo)樱溉。
模運(yùn)算如下：
int index =hash% length;
但是hashmap不這樣做福贞，而是采用&
h & (length-1);
這樣做的原理是啥？
由于計(jì)算機(jī)是底層的運(yùn)算是基于2進(jìn)制的绢馍，&比%具有更高的效率,h& (length-1)運(yùn)算等價(jià)h%length
HashMap的數(shù)組長(zhǎng)度取2的整次冪舰涌。所以（數(shù)組長(zhǎng)度-1）正好相當(dāng)于一個(gè)“低位掩碼”你稚。“與”操作的結(jié)果就是散列值的高位全部歸零搁痛，只保留低位值鸡典，用來(lái)做數(shù)組下標(biāo)訪問(wèn)彻况。以初始長(zhǎng)度16為例纽甘，16-1=15悍赢。2進(jìn)制表示是00000000 00000000 00001111左权。和某散列值做“與”操作如下，結(jié)果就是截取了最低的四位值。
10100101 11000100 00100101
& 00000000 00000000 00001111
----------------------------------
00000000 00000000 00000101 //高位全部歸零瀑梗，只保留末四位抛丽，最后下標(biāo)為5
所以這就是HashMap的數(shù)組長(zhǎng)度取2的整次冪的原因
1.1.1.2饰豺、java8中hashMap散列值函數(shù)
上面提到獲取key的哈希值冤吨，直接通過(guò)key.hashCode()不行嗎垒探，為啥還要：
(h = key.hashCode()) ^ (h >>> 16);
原理
下圖：n為table的長(zhǎng)度怠李。
由于 h>>>16夷蚊，高16bit 補(bǔ)0髓介，一個(gè)數(shù)和0異或不變惕鼓，所以 hash 函數(shù)大概的作用就是：高16bit不變，低16bit和高16bit做了一個(gè)異或唐础，就是為了混合原始哈希碼的高位和低位呜笑，以此來(lái)加大低位的隨機(jī)性。而且混合后的低位摻雜了高位的部分特征彻犁，這樣高位的信息也被變相保留下來(lái)叫胁。這是設(shè)計(jì)者從速度、功效汞幢、質(zhì)量來(lái)考慮的驼鹅。經(jīng)過(guò)’擾亂‘后可以大大的減少碰撞
1.1.2擴(kuò)容優(yōu)化
e.hash & oldCap
resize()用來(lái)第一次初始化，或者 put 之后數(shù)據(jù)超過(guò)了threshold后擴(kuò)容
數(shù)組下標(biāo)計(jì)算： index = (table.length - 1) & hash ，由于 table.length 也就是capacity 肯定是2的N次方输钩，使用 & 位運(yùn)算意味著只是多了最高位，這樣就不用重新計(jì)算 index肴焊，元素要么在原位置，要么在原位置+ oldCapacity届宠。
如果增加的高位為0，resize 后 index 不變幌羞，如圖所示：
如果增加的高位為1，resize 后 index 增加 oldCap，如圖所示：
例子：
初始容量為16亡资，那么15轉(zhuǎn)換為二進(jìn)制數(shù)位1111，現(xiàn)在進(jìn)行一次擴(kuò)容之后容量變?yōu)?2，那么31轉(zhuǎn)換為2進(jìn)制是為11111⌒页猓現(xiàn)有兩個(gè)key来惧，一個(gè)hashcode為107轉(zhuǎn)換為二進(jìn)制數(shù)后為1101011隅居，另一個(gè)的hashcode是379轉(zhuǎn)換為二進(jìn)制數(shù)后為101111011。在容量為16的時(shí)候涕蚤，這兩個(gè)key西疤，具體計(jì)算索引過(guò)程為：
0001111 & 1101011 = 1011
000001111 & 101111011 = 1011 轉(zhuǎn)換為10進(jìn)制數(shù)后都為11扰她。
現(xiàn)在來(lái)看一下擴(kuò)容之后兩個(gè)key的索引：
0011111 & 1101011 = 1011
000011111 & 101111011 = 11011 一個(gè)對(duì)應(yīng)的索引仍然是11，而另一個(gè)卻變?yōu)?7（27 = 11+16）
因此廉涕，HashMap數(shù)組的擴(kuò)容的整體思想就是創(chuàng)建一個(gè)長(zhǎng)度為原先2倍的數(shù)組宠纯。然后對(duì)原數(shù)組進(jìn)行遍歷和復(fù)制贡羔。只不過(guò)jdk1.8對(duì)擴(kuò)容進(jìn)行優(yōu)化猴蹂，使得擴(kuò)容不再需要進(jìn)行鏈表的反轉(zhuǎn)，只需要知道hashcode新增的bit位為0還是1。如果是0就在原索引位置撮躁，新增索引是1的話索引變成“原索引+oldCap”漓穿，可以看看下圖為16擴(kuò)充為32的resize示意圖：
這個(gè)設(shè)計(jì)確實(shí)非常的巧妙，既省去了重新計(jì)算hash值的時(shí)間纠俭，而且同時(shí)权纤，由于新增的1bit是0還是1可以認(rèn)為是隨機(jī)的撤蚊，因此resize的過(guò)程，均勻的把之前的沖突的節(jié)點(diǎn)分散到新的bucket了光涂。這一塊就是JDK1.8新增的優(yōu)化點(diǎn)恋博。
2践付、byte & 0xff
java中byte轉(zhuǎn)換int時(shí)為何與0xff進(jìn)行與運(yùn)算隧土？
舉個(gè)簡(jiǎn)單的例子:
byte[] b = new byte[5];
b[0] = -12;
-12 的絕對(duì)值原碼是：0000 1100 取反： 1111 0011 加1： 1111 0100
byte --> int 就是由8位變 32 位
高24位全部補(bǔ)1： 1111 1111 1111 1111 1111 1111 1111 0100 ;
0xFF 是計(jì)算機(jī)十六進(jìn)制的表示： 0x就是代表十六進(jìn)制饲宛，A B C D E F 分別代表10 11 12 13 14 15 F就是15 一個(gè)F 代表4位二進(jìn)制幕庐。則0xFF的二進(jìn)制表示就是：1111 1111冤寿。
高24位補(bǔ)0：0000 0000 0000 0000 0000 0000 1111 1111;
-12的補(bǔ)碼與0xFF 進(jìn)行與（&）操作 最后就是0000 0000 0000 0000 0000 0000 1111 0100
轉(zhuǎn)換為十進(jìn)制就是 244。
byte類型的數(shù)字要&0xff再賦值給int類型痴施，其本質(zhì)原因就是想保持二進(jìn)制補(bǔ)碼的一致性神得。
當(dāng)byte要轉(zhuǎn)化為int的時(shí)候酝静，高的24位必然會(huì)補(bǔ)1宗苍，這樣丽啡，其二進(jìn)制補(bǔ)碼其實(shí)已經(jīng)不一致了，&0xff可以將高的24位置為0坑雅，低8位保持原樣冕香。這樣做的目的就是為了保證二進(jìn)制數(shù)據(jù)的一致性。
3、獲取
public void getBit() {
int num = 12;
int i = 3;
System.out.println((num & (1 << i))!=0);
}
該方法把1向左移動(dòng)i位早龟，為01000猜丹，num&01000，從而將除i位以外都清0蝌麸，如果num的i位為1来吩，則返回true碾褂。常用的用法是：利用位運(yùn)算來(lái)判斷數(shù)據(jù)是否重復(fù)乓诽，如果num數(shù)組該位為1帐姻，說(shuō)明位數(shù)組已經(jīng)存儲(chǔ)了該元素，重復(fù)了
4渔肩、置位
public void setBit() {
int num = 12;
int i = 3;
System.out.println(num | (1 << i));
}
該方法把1向左移動(dòng)i位蛉艾，為01000兵钮，num | 01000葱轩，將num的i位置位1缭嫡，只會(huì)改變i位妇蛀，其他位沒(méi)變化登刺。常用的用法：存儲(chǔ)數(shù)據(jù)
例如：
//判斷是否有重復(fù)的字符
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，只會(huì)清零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結(jié)合。
1<<i：00001000
~(1 << i)：11111111111111111111111111110111
num & mask：00001100 &11111111111111111111111111110111==100
v<<i：10000凳怨，將v（0010）左移i位瑰艘，得到一個(gè)i位為v，其余位為0
(num & mask) | (v<<i)：100|10000==10100
v為1則num的i位更新為1肤舞，否則為0
7紫新、1 << 30
1無(wú)符號(hào)左移30位，也就是二進(jìn)制1后面跟著30個(gè)0李剖，int類型最大值芒率，正數(shù)高位補(bǔ)零
0100 0000 0000 0000 0000 0000 0000 0000
8、9>>> 1
大于9 的一半篙顺，結(jié)果為4
