本人非科班出身，但由于想從事這一行業(yè)，希望進階到更高的境界乐纸，可是面試了幾次發(fā)現(xiàn)沒有一些基礎(chǔ)確實是有些難以支撐自己常柄，所以在此記錄一下自己學(xué)習(xí)的一些知識和想法鲤氢，文章中如果有錯誤的希望各位能指正。
0. 數(shù)據(jù)在計算機中的表示方式
當(dāng)代設(shè)計的計算機存儲數(shù)據(jù)只能用0和1來表示西潘，所以計算機中都是用二進制來表示各類的數(shù)據(jù)卷玉，也由此說明了一件事，計算機中存儲數(shù)據(jù)的最小單位是比特（bit）喷市。好比如：
0 -> 0000 0000 # 0用二進制表示
1 -> 0000 0001 # 1用二進制表示
2 -> 0000 0010 # 2用二進制表示（由于是二進制相种，所以縫2進位）
上面為什么0需要用到8個0來寫呢？那是因為品姓，Bit這個單位確實是太小了寝并，存儲起來不太方便，所以我們樣規(guī)定腹备，8個比特等于1個字節(jié)（8 Bit = 1 Byte）衬潦，這里的Byte就是字節(jié)的意思，可以簡寫成B植酥，因此存儲容量的基本單位是字節(jié)别渔。而每1024個字節(jié)又可以用KB來表示（具體原因請查看百度百科），所以他們的關(guān)系如下：
8 bit（比特） = 1 Byte（字節(jié)惧互，簡寫 B）
1024 Byte（字節(jié)） = 1 KB（千字節(jié)）
1024 KB （千字節(jié)） = 1 MB （兆字節(jié)哎媚，百萬字節(jié)）
1024 MB （兆字節(jié)，百萬字節(jié)） = 1 GB（吉字節(jié)喊儡，十億字節(jié)）
...
這里一個快速換算的網(wǎng)站：https://www.bejson.com/convert/filesize/
但是拨与，現(xiàn)實生活中，我們除了計算正整數(shù)外艾猜，還會有負整數(shù)买喧，那么，在表示一個二進制的整數(shù)時這樣規(guī)定匆赃，這個數(shù)的第一個數(shù)字用來表示正號或負號淤毛，所以就有下面的表示：
1 -> 0000 0001
-1 -> 1000 0001
可能說到這里有些人會產(chǎn)生疑惑，計算機的數(shù)據(jù)不是連著的嗎算柳？雖然這里的-1的第一位數(shù)是1低淡，但是1再往前的數(shù)，它又怎樣區(qū)分不是它的呢？
可能說得有點繞蔗蹋，這里畫一個圖來表示
像上面的圖所說的何荚，計算機不知道到底要從哪里開始取這個
-1，所以一般下猪杭，在我們定義這個數(shù)的時候餐塘，我們先會告訴計算機，我們需要使用多少比特(bit)皂吮，然后計算機會幫我們在內(nèi)存里開辟這么多的空間給我們存儲數(shù)據(jù)（個人理解）戒傻。但具體計算機是怎樣記錄這塊內(nèi)存空間從哪里到哪里的，個人水平有限蜂筹，如果以后知道另外再寫文章介紹吧稠鼻。所以，大致流程如下
- 剛開始時狂票，內(nèi)存可能是長這個樣子的
- 當(dāng)我們向計算機申請一塊內(nèi)存使用候齿，它可能是這樣子記錄的（紅色框表示已使用的內(nèi)存）
- 當(dāng)我們再次申請內(nèi)存，它可能又是長這個樣子的（紅色框表示已使用的內(nèi)存）
我們程序中所說的int類型闺属，一般都是指int32慌盯，也就是需要用32個bit來存我們這個數(shù)。所以掂器，假如我們需要創(chuàng)建一個int32類型的數(shù)據(jù)亚皂，這時內(nèi)存空間應(yīng)該是這樣子的
所以到這里，我們順便回答了一個問題国瓮，也就是int8灭必，int16，int32乃摹，int64的取值范圍
因為每個數(shù)有一位用于表示符號禁漓，所以范圍取值是該數(shù)使用bit位數(shù)的數(shù)量減1，另外0由于沒有正負之分孵睬，所以正整數(shù)的總數(shù)需要減一
int8 取值范圍： -2^7 ~ 2^7-1
int16 取值范圍：-2^15 ~ 2^15-1
int32 取值范圍：-2^31 ~ 2^31-1
int64 取值范圍：-2^63 ~ 2^63-1
1. 位運算概要
從現(xiàn)代計算機中所有的數(shù)據(jù)二進制的形式存儲在設(shè)備中播歼。即0、1兩種狀態(tài)掰读，計算機對二進制數(shù)據(jù)進行的運算(+秘狞、-、*蹈集、/)都是叫位運算烁试，即將符號位共同參與運算的運算。
下面舉個例子說明一下：
35 + 47
計算兩個數(shù)的和拢肆，因為在計算機中都是以二進制來進行運算减响，所以上面我們所給的int變量會在機器內(nèi)部先轉(zhuǎn)換為二進制在進行相加：
35: 0 0 1 0 0 0 1 1
47: 0 0 1 0 1 1 1 1
————————————————————
82: 0 1 0 1 0 0 1 0
所以靖诗，相比在代碼中直接使用(+、-辩蛋、*呻畸、/)運算符移盆，合理的運用位運算更能顯著提高代碼在機器上的執(zhí)行效率悼院。
2. 位運算符
| 符號 | 描述 | 運算規(guī)則 |
|---|---|---|
| & | 與 | 兩個位都為1時，結(jié)果才為1 |
| | | 或 | 兩個位都為0時咒循，結(jié)果才為0 |
| ^ | 異或 | 兩個位相同為0据途，相異為1 |
| ~ | 取反 | 0變1，1變0 |
| << | 左移 | 各二進位全部左移若干位叙甸，高位丟棄颖医，低位補0 |
| >> | 右移 | 各二進位全部右移若干位，對無符號數(shù)裆蒸，高位補0熔萧，有符號數(shù)，各編譯器處理方法不一樣僚祷，有的補符號位（算術(shù)右移）佛致，有的補0（邏輯右移） |
3. 按位與運算符（&）
- 定義：兩個位都為1時，結(jié)果才為1辙谜，否則結(jié)果為0俺榆。
- 運算規(guī)則：
0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1
例如：
3 & 5 = 1
3: 0 0 0 0 0 0 1 1
5: 0 0 0 0 0 1 0 1
--------------------
1: 0 0 0 0 0 0 0 1
- 注意：負數(shù)按補碼形式參加按位與運算。
- 與運算的用途：
1）清零
如果想將一個單元清零装哆，即使其全部二進制位為0罐脊，只要與一個各位都為零的數(shù)值相與，結(jié)果為零蜕琴。
如：1&0=0萍桌、100&0=0、127&0=0
2）取一個數(shù)的指定位（可以理解為求交集）
比如取數(shù) X=1010 1110 的低4位凌简，只需要另找一個數(shù)Y梗夸，令Y的低4位為1，其余位為0号醉，即Y=0000 1111反症，然后將X與Y進行按位與運算（X&Y=0000 1110）即可得到X的指定位。
3）判斷奇偶
只要根據(jù)最未位是0還是1來決定畔派，為0就是偶數(shù)铅碍，為1就是奇數(shù)。因此可以用if ((a & 1) == 0)代替if (a % 2 == 0)來判斷a是不是偶數(shù)线椰。
PS：%是求余符號
4. 按位或運算符（|）
- 定義：兩個位都為0時胞谈，結(jié)果才為0，否則結(jié)果為1。
- 運算規(guī)則：
0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1
例如：
3 | 5 = 1
3: 0 0 0 0 0 0 1 1
5: 0 0 0 0 0 1 0 1
--------------------
7: 0 0 0 0 0 1 1 1
- 注意：負數(shù)按補碼形式參加按位或運算烦绳。
- 或運算的用途：
1）常用來對一個數(shù)據(jù)的某些位設(shè)置為1（可以理解為求并集）
比如將數(shù) X=1010 1110 的低4位設(shè)置為1卿捎，只需要另找一個數(shù)Y，令Y的低4位為1径密，其余位為0午阵，即Y=0000 1111，然后將X與Y進行按位或運算（X|Y=1010 1111）即可得到享扔。
5. 異或運算符（^）
- 定義：兩個對象的對應(yīng)位置上的數(shù)相同為0底桂，不同為1.
- 運算規(guī)則：
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0
例如：
3 ^ 5 = 6
3: 0 0 0 0 0 0 1 1
5: 0 0 0 0 0 1 0 1
--------------------
6: 0 0 0 0 0 1 1 0
- 異或的幾條性質(zhì)：
1、交換律
2惧眠、結(jié)合律 (a ^ b) ^ c == a ^ (b ^ c)
3籽懦、對于任何數(shù)x，都有 x ^ x = 0氛魁，x ^ 0 = x
4暮顺、自反性: a ^ b ^ b = a ^ 0 = a - 異或運算的用途：
1）翻轉(zhuǎn)指定位（有點類似求差集）
比如將數(shù) X=1010 1110 的低4位進行翻轉(zhuǎn)，只需要另找一個數(shù)Y秀存，令Y的低4位為1捶码，其余位為0，即Y=0000 1111应又，然后將X與Y進行異或運算（X^Y=1010 0001）即可得到宙项。
2）與0相異或值不變
例如：1010 1110 ^ 0000 0000 = 1010 1110
3）交換兩個數(shù)
void Swap(int &a, int &b){
if (a != b){
a ^= b;
b ^= a;
a ^= b;
}
}
6. 取反運算符（~）
- 定義：對數(shù)據(jù)的每個二進制位取反,即把1變?yōu)?,把0變?yōu)?。
- 運算規(guī)則：
~1 = -2
~0 = -1
例如：
5: 0 0 0 0 0 1 0 1
---------------------
-6: 1 1 1 1 1 0 1 0
到這里可能有些人會有疑惑株扛，為什么1111 1010表示的是-6呢尤筐？
其實，取反后洞就，還需要進行取原碼的操作就可以得到-6了盆繁，上面是反碼的表示方式，反碼取原碼的具體步驟如下：
首位不變旬蟋，取反碼油昂，末尾加1。
1. 首位不變倾贰，取反碼
1 1 1 1 1 0 1 0
----------------
1 0 0 0 0 1 0 1
2. 末尾加1
1 0 0 0 0 1 0 1
0 0 0 0 0 0 0 1
----------------
1 0 0 0 0 1 1 0
所以經(jīng)過上面計算后冕碟，最終的結(jié)果就是-6，具體可以查看 位運算 按位取反是怎么算出來的 這篇文章中的介紹
- 異或運算的用途：
1）使一個數(shù)的最低位為零
使a的最低位為0匆浙，可以表示為：a & ~1安寺。~1的值為 1111 1111 1111 1110，再按"與"運算首尼，最低位一定為0挑庶。因為“ ~”運算符的優(yōu)先級比算術(shù)運算符言秸、關(guān)系運算符、邏輯運算符和其他運算符都高迎捺。
7. 左移運算符（<<）
- 定義：將一個運算對象的各二進制位全部左移若干位（左邊的二進制位丟棄举畸，右邊補0）。
- 運算規(guī)則：
5 << 1 = 10
5 << 2 = 20
5 << 3 = 40
例如：
5 << 2 = 20
5: 0 0 0 0 0 1 0 1
-------------------- 向左移兩位后
20: 0 0 0 1 0 1 0 0
- 左移運算符的用途：
1）快速計算某個數(shù)乘以2的幾次方
其實從上面的結(jié)論可以看出凳枝，5的機器碼左移1位抄沮，相當(dāng)于5?2的操作（2^1），左移2位范舀，相當(dāng)于5×4的操作（2^2）合是，所以可以通過這樣的方法快速算出某個數(shù)乘以2的幾次方了罪，這樣的計算是相當(dāng)?shù)目斓摹?/li>
8. 右移運算符（>>）
定義：將一個數(shù)的各二進制位全部右移若干位锭环，正數(shù)左補0，負數(shù)左補1泊藕，右邊丟棄辅辩。
- 運算規(guī)則：
8 >> 2 = 2
6 >> 2 = 1
-10 >> 2 = -3
例如：
8 >> 2 = 2
8: 0 0 0 0 1 0 0 0
-------------------- 向又移兩位后
2: 0 0 0 0 0 0 1 0
6 >> 2 = 1
6: 0 0 0 0 0 1 1 0
-------------------- 向又移兩位后
1: 0 0 0 0 0 0 0 1
然而，負數(shù)的右移位運算比較特別娃圆，需要先對原碼的補碼玫锋，在右移，然后保留符號位讼呢，按位取反撩鹿，然后加1，即為所求數(shù)的原碼悦屏，具體步驟如下：
-10 >> 2 = -3
1. 求原碼的補碼（保證符號位不變节沦，其余位置取反加1）
-10的原碼：1 0 0 0 1 0 1 0
-10的補碼：1 1 1 1 0 1 1 0
2. 右移2位
1 1 1 1 0 1 1 0
----------------
1 1 1 1 1 1 0 1
3. 保留符號位，按位取反
1 1 1 1 1 1 0 1
----------------
1 0 0 0 0 0 1 0
4. 加1求原碼
1 0 0 0 0 0 1 0
----------------
1 0 0 0 0 0 1 1
- 右移運算符的用途：
1）在沒有溢出的情況下础爬，可以看成是求某個數(shù)除以2的n次方
9. 注意：
1）上面的計算都是基于整數(shù)而言甫贯，小數(shù)不在此考察范圍內(nèi)
2）對于左移運算和右移運算，在沒有位溢出的情況下看蚜，都可以看成是某個數(shù)成或除以2的n次方
參考：
https://www.cnblogs.com/yrjns/p/11246163.html
https://blog.51cto.com/sunnybay/1625309
https://blog.csdn.net/king_msky/article/details/17221973
