二進制到底是什么為什么所有的一切都是二進制

字節(jié)

位運算

二進制實現(xiàn)加減乘除

講一下四則運算表達式

字符編碼

Bas64編解碼

URL encoding

字節(jié)

0 或 1

1byte = 8位

一個字節(jié)的范圍-128~127, 2^8 = 256

在計算機中，一個字節(jié)是由8位二進制組成，例如：1100 1111

字節(jié)通常寫為"B"，位通常寫為"b"，計算機存儲器的大小通常用字節(jié)表示

帶寬及碼率通常是位表示，例如：kbps，mbps，一秒鐘傳輸所需的帶寬大小，這個單位是"位"，對比我們平常所說流量大小需要單位/8

例如：家的網(wǎng)絡帶寬是100mbps=100*1000kbps，為什么我的下載流量沒有達到那么高，這里需要說明的是，下載的流量是存儲單位，在計算機中是用字節(jié)表示的，是位單位的1/8。也就是：100M的帶寬，對應的實際流量是100/8 = 12.5M

帶寬分為上/下行，一般的路由上/下行帶寬分配比例是1:8，也就是說，上行是占總帶寬的1/9，下行是占總帶寬的8/9（可以通過路由器自定義調(diào)整），那么對應的100mbps帶寬，實現(xiàn)下載流量大約是11M左右，上行流量大約是1.5M左右

位運算

& 與運算：兩個位都為1時，結(jié)果才是1

| 或運算：兩個位都為0時，結(jié)果才是0

^ 異或運算：兩個位相同為0，相異為1

~ 取反：0變1，1變0

<< 左移：各個二進位全部移動若干位，低位補零

>> 右移：各個二進位全部移動若干位，高位補零

與運算

清零（所有位都和0做與運算）

取一個數(shù)的指定位（例如：1010 1110，取低四位的數(shù)，和 0000 11111做與運算，得出1110）

判斷奇偶（根據(jù)末尾進行判斷，0是偶數(shù)，1是奇數(shù)，if（x&1 == 0））

if (x & 1 == 0) return TURE;return FALSE;

或運算

用來對一個數(shù)據(jù)某些位置設置為1（例如：1010 1110，低四位設置為1，和0000 1111做或運算，得出1010 1111）

異或運算

總結(jié)：如果兩個相應位相同為0，相異為1

特性：交換（a=a^b;b=a^b;a=a^b;）結(jié)合（(a^b)^c = a^(b^c)）對于任何數(shù)，都符合(a^a = 0, a^0=a)自反（a ^ 1, 末尾取反，0是不變，1是取反）

翻轉(zhuǎn)指定位（例如：1010 1110，將其低四位進行翻轉(zhuǎn)，和0000 1111做異或運算，得到1010 0001）

交換兩個數(shù)，且無需引用多余的指針（a=a^b;b=a^b;a=a^b;）

void swap(int &a, int &b){if (a !=b) { a = a^b; b = a^b; a = a^b; // 注意此時的a=a^b;此時的b=a; }}

取反運算

總結(jié)：對一個二進制數(shù)位取反，0變1，1變0

~1 = 0； ~0 = 1；

使一個數(shù)的最低位為0（例如：1010 0001 & ~1 = 1010 0000，~運算符的優(yōu)先級高于其它符號）

左/右移運算

左移1位（相當于乘以2，1010 0001 << 2 = 10 1000 0100）

右移1位（相當于除以2，1010 0001 >> 2 = 10 1000 00）

用于進位操作

二進制實現(xiàn)加減乘除

加法

首先來說一下，十進制的相加方法：

例如1：14 + 7 = 21 ， 首先不考慮進位等于11，由于4+7需要進位10，那么11 + 10 = 21；

例如2：136 + 967 = 1103，首先不考慮進位等于093，需要進位1010，那么093 + 1010 = 1103；

136 + 967 進位說明：

個位 6 + 7 進位 10

十位 3 + 9 不進位 0

百位 9 + 1 進位 100

需要進位的值10+1000 = 1010

例如3：9176 + 967 = 10143，不考慮進位等于9033，需要進位1110，那么9033 + 1110 = 10143；

9176 + 967 進位說明：

個位 6 + 7 進位 10

十位 7 + 6 進位 100

百位 1 + 9 進位 1000

千位 9 + 0不進位 0

需要進位的值10+100+1000 = 1110

證明：兩個數(shù)字相加的時候，不考慮進位的值相加，最后再加上進位的值，得出最終的結(jié)果；

二進制，每位相加，逢二進一；例如：01 + 01 = 10

同理二進制，亦是如此，符合不考慮進位相加，再加上進位的值，但是二進制需要做一下邏輯運算的轉(zhuǎn)換；

首先不考慮進位的情況下

1 + 1 = 0 （1 ^ 1 = 0） 1 + 0 = 1 （1 ^ 0 = 1） 0 + 1 = 1 （0 ^ 1 = 1） 0 + 0 = 0 （0 ^ 0 = 0） 規(guī)律如下：位值相同，相加為0；位值相異，相加為1再不考慮進位的情況下，符合"異或運算"； a ^ b

2.接著考慮進位的問題

1 + 1 = 1（1 & 1 = 1）1 + 0 = 0 （1 & 0 = 0）0 + 1 = 0 （0 & 1 = 0）0 + 0 = 0 （0 & 0 = 0）規(guī)律如下：符合與運算

3.相加 a + b

不進位值相加 = a ^ b進位的值相加 = a & b << 1累計相加 = a ^ b + a & b << 1遞歸循環(huán)調(diào)用，直至進位的值相加為0，也就是說無需再次進位a + b = a ^ b + a & b << 1int add(int a, int b){if (b == 0 ) return a;return add(a ^ b,a & b << 1);}

減法

減法思考，將減法做成加法，例如：9176 + 967 = 9176 +（-967）

那么，在二進制中，如何將一個值表達為負數(shù)，例如：0000 1000 = 8，那么-8 = 1000 1000

通過2的補碼，它是一種用二進制表示有號數(shù)的方法，也是一種將數(shù)字的正負號變號的方式，其實現(xiàn)的步驟如下：

1、每一個二進制位取反值，0變1，1變0（即反碼）

2、將反碼加1

對于負值的表示方法，其實就是取反加一// a 是減數(shù) // b 是被減數(shù)int subtraction(int a, int b){int negative = addition(~b,1); //取反加1，得到的負數(shù) return add(a,negative);}

乘法

乘法思考，將乘法做成加法，例如：16 * 15 , 就相當于16個15相加，或是15個16相加

int multiplyAction(int a, int b){ // 首先取絕對值 int a1 = a < 0 ? subtraction(0,a) : a; int b1 = b < 0 ? subtraction(0,b) : b; int product = a1; while(--b1) { product = addition(product,a1); }// 判斷正負 if (a < 0 | b < 0) { // 取反加1，得到負數(shù) return addition(~product,1); // return subtraction(0,product) } return product;}

除法

除法思考，將除法做成減法，例如：120 / 23 = 5.217 (四舍五入 = 5) ，就當于減去了5次23，剩下的值是余數(shù)，判斷余數(shù)是否大于23的一半，進而判斷是否是需要四舍五入

int division(int a, int b){// 首先取絕對值 int a1 = a < 0 ? subtraction(0,a) : a; int b1 = b < 0 ? subtraction(0,b) : b; int productCount = 0; while(true) { a1 = subtraction(a1,b1);// 判斷余數(shù)，計算四舍五入 if (a1 < b1) { if ((b1 >> 2) > a1){ break; } } productCount = addition(productCount,b1); } // 判斷正負 if (a < 0 | b < 0) { // 取反加1，得到負數(shù) return addition(~productCount,1); // return subtraction(0,product) } return productCount;}// 此方法的效率比較低，如果除數(shù)比被除數(shù)大很多的時候，就增加了很多次的遍歷，通過算法相減的方法// 目前是按照1倍被除數(shù)相減，當然了也可以按照2倍，3倍甚至多倍的思路來實現(xiàn)// 有興趣的同學，可以再此算法上做繼續(xù)的優(yōu)化

講一下四則運算表達式

計算器的加減乘除是如何實現(xiàn)的（數(shù)學表達式的求值方式）

計算規(guī)則：先乘除，后加減，從左到右，先括號后括號外

20世紀50年代，波蘭邏輯學家提出"一種不需要括號的后綴表達式"，稱值為逆波蘭（Reverse Polish Notaiton， RPN）

首先看一下中綴表達式

中綴表達式如何轉(zhuǎn)后綴表達式

后綴表示是如何計算結(jié)果的

我們平常使用的表達式就中綴表達式，例如：3-5*(6/3)+2/(3*8)

那么如何將中綴表達式轉(zhuǎn)換為后綴表達式呢？

規(guī)則：從左到右遍歷數(shù)字和符號，如是數(shù)子輸出；如是符號，則判斷與棧頂符號的優(yōu)先級，右括號或優(yōu)先級低于棧頂符號（乘除優(yōu)先加減）則棧頂元素依次輸出，并將當前符號進棧，直至全部輸出。

例如：3-5*(6/3)+2/(3*8)

1、初始化一個空棧，用來對符號進行出棧使用

2、第1個字符是3，直接輸出；【輸出：3】

3、第2個字符是-，棧頂為空，入棧 【棧：- 】

4、第3個字符是5，直接輸出，【棧：- 】【輸出：3 5】

5、第4個字符是*，對比棧頂-，*優(yōu)先級高于棧頂，入棧，【棧：- *】

6、第5個字符是(，直接入棧，【棧：- * (】

7、第6個字符是6，直接輸出，【輸出：3 5 6】

8、第7個字符是/，因為還沒有找到)，所以入棧，【棧：- * ( / 】

9、第8個字符是3，直接輸出，【輸出：3 5 6 3】

10、第9個字符是），匹配棧里面的（，【輸出：3 5 6 3 /】 【棧：- * 】

11、第10個字符是+，對比棧頂*，優(yōu)先級低于棧頂，全部出棧，【輸出：3 5 6 3 / * -】【棧：+ 】

12、第11個字符是2，直接輸出，【輸出：3 5 6 3 / * - 2】

13、第12個字符是/，對比棧頂+，優(yōu)先級高于棧頂，所以入棧，【棧：+ /】

14、第13個字符是(，直接入棧，【棧：+ / （】

15、第14個字符是3，直接輸出，【輸出：3 5 6 3 / * - 2 3】

16、第15個字符是*，對比棧頂元素（，直接入棧，【棧：+ / （ *】

17、第16個字符是8，直接輸出，【輸出：3 5 6 3 / * - 2 3 8】

18、第17個字符是），匹配（， 左括號和右括號中間依次出棧，【輸出：3 5 6 3 / * - 2 3 8 *】 【棧：+ / 】

19、剩余棧中元素，依次出棧 【輸出：3 5 6 3 / * - 2 3 8 * / +】

后綴表達式是如何進行計算的

規(guī)則：從左到右邊依次遍歷表達式，遇到數(shù)字就進棧，遇到符號，就將處于棧頂兩數(shù)字出棧，進行運算（注意：棧頂2 計算符號 棧頂1元素，注意順序），運算結(jié)果進棧，一直最終獲得結(jié)果

例如：3 5 6 3 / * - 2 3 8 * / +

1、第1個字符是3，入棧【棧：3】

2、第2個字符是5，入棧【棧：3 5】

3、第3個字符是6，入?！緱＃? 5 6】

4、第4個字符是3，入棧【棧：3 5 6 3】

5、第5個字符是/，取得棧頂2個元素進行計算（3 和 6 出棧），6 / 3 = 2 ，將2入?！緱＃? 5 2】

6、第6個字符是*，取得棧頂2個元素進行計算（2 和 5 出棧），5 * 2 = 10 ，將10入棧【棧：3 10】

7、第7個字符是-，取得棧頂2個元素進行計算（3 和 10 出棧），3 - 12 = -7 ，將-7入?！緱＃?7】

8、第8-10個字符是2 3 8，依次入棧【棧：-7 2 3 8】

9、第11個字符是*，取得棧頂2個元素進行計算（3 和 8 出棧），8 * 3 = 24，，將24入棧【棧：-7 2 24】

10、第12個字符是/，取得棧頂2個元素進行計算（2 和 24 出棧），2 * 24 = 1/12，，將1/12入?！緱＃?7 1/12】

11、第13個字符是+，取得棧頂2個元素進行計算（1/12 和 -7 出棧），-7 * 1/12 = -83/12，入棧

12、字符變量結(jié)束，最后一個元素出棧得出結(jié)果:-83/12

再舉一個復雜的表達式：5 + [ ( 3 - 7 ) / ( 9 * 3 + 2 ) ] * 4 - 6

中綴表達式轉(zhuǎn)化后綴表達式的過程（簡化版）

1、5 【棧：+ [ (】

2、5 3【棧：+ [ ( -】

3、5 3 7【棧：+ [ ( - )】 再次輸出5 3 7 -【棧：+ [ 】

4、5 3 7 - 9【棧：+ [ / ( *】

5、5 3 7 - 9 3【棧：+ [ / ( *】 再次輸出5 3 7 9 3 * 【棧：+ [ / ( +】

6、5 3 7 - 9 3 * 2 + 【棧：+ [ / ( + ）】，【棧：+ [ / ] 】

7、5 3 7 - 9 3 * 2 + /【棧：+ 】

8、5 3 7 - 9 3 * 2 + / 4【棧：+ *】

9、5 3 7 - 9 3 * 2 + / 4 * + 【棧：-】

10、5 3 7 - 9 3 * 2 + / 4 * + 6【棧：-】

11、5 3 7 - 9 3 * 2 + / 4 * + 6 -

最終得到后綴表達式：5 3 7 - 9 3 * 2 + / 4 * + 6 -

總結(jié)

四則表達式，其實就運用了棧的思想，實現(xiàn)了后綴表達式

1、將中綴表達式轉(zhuǎn)化為后綴表達式（按照加減乘除優(yōu)先級來運算符號，去除了括號）

2、將后綴表達式進行運算得出結(jié)果（進行運算數(shù)字，注意運算的順序）

編碼

ASCII碼

在計算機中，所有的數(shù)據(jù)在存儲和運算時都要使用二進制表示，就像a,c,d26個字母以及0-9數(shù)字及一些常用的符號，在計算機中存儲也要使用二進制來表示；

而具體的要那些二進制來表示那些符號，那么就提出了ASCII編碼，是由美國標準信息交換代碼制定的，用于文本數(shù)據(jù)

ASCII碼用指定的7位或8位二進制組合來表示128或256種的可能字符；使用7位表示二進制（剩下一位二進制為0），也就是一個字節(jié)大小的存儲來表示。

0～31及127(共33個)是控制字符或通信專用字符（不可顯示的字符），例如：換行，回車，刪除等。

32～126(共95個)是字符(32是空格），其中48～57為0到9十個阿拉伯數(shù)字。

65～90為26個大寫英文字母，97～122號為26個小寫英文字母，其余為一些標點符號、運算符號等。

例如：一串字符"abc123$&"，通過ASCII編碼存儲后的樣子是

十進制：97 98 99 49 50 51 44 46

二進制：01100001 01100010 01100011 00110001 00110010 00110011 00100100 00100110

在計算機中存儲的樣式就是，上面的二進制信息

ASCII碼擴展問題

加上一些特殊的字符，127個肯定是無法滿足的，ASCII碼擴展到255個字符

注意這8個位，最高位是1開頭的，取值范圍128~255

例如：

128 10000000 € 歐盟符號

131 10000011 ? 拉丁小寫字母f

255 11111111 ?

大小規(guī)則的定義：

常見ASCII碼的大小規(guī)則：0~9

1）數(shù)字比字母要小。如 “7”<“F”；

2）數(shù)字0比數(shù)字9要小，并按0到9順序遞增。如 “3”<“8” ；

3）字母A比字母Z要小，并按A到Z順序遞增。如“A”<“Z” ；

4）同個字母的大寫字母比小寫字母要小32。如“A”<“a” 。

幾個常見字母的ASCII碼大小： “A”為65；“a”為97；“0”為 48

Unicode碼

雖然ASCII碼做了擴展，但是最多也就是256個字符，如果考慮到漢字，一個字節(jié)來表示字符肯定是不夠的，這樣就必須引入2個字節(jié)來表示一個漢字；

那么有沒有一種編碼，可以容納所有的字符類型？

Unicode就是一個很大的集合，目前規(guī)?？扇菁{100多萬個符號；

Unicode（統(tǒng)一碼、萬國碼、單一碼）是計算機科學領域里的一項業(yè)界標準，包括字符集、編碼方案

Unicode本身是一個符號集，它只規(guī)定了符號的二進制代碼，但是沒有規(guī)定二進制代碼如何存儲，這樣的話就導致了一個問題，一些字符是一個字節(jié)，兩個字節(jié)，三個字節(jié)，甚至更多。

這樣就帶來了2個問題

1、如何區(qū)分Unicode和AscII編碼，計算機是如何知道三個字節(jié)表示一個符號，而不是表示三個符號呢？

2、存儲空間的浪費，Ascll編碼一個字符占8位也就是一個字節(jié)，Unicode每個符號用4個，5個字節(jié)表示，對于每個英文字符前面必然有4個，5個字節(jié)，甚至更多個字節(jié)，這樣給存儲帶來極大的浪費

UTF-8

UTF-8是一個非常好的編碼方式，完美的對接了AscII碼，同時也解決了Unicode的問題，需要說明的是UTF-8是Unicode編碼方式的一種

可以用1-4個字符來表示一個字符，根據(jù)字符的不同變化不同的長度

編碼規(guī)則如下：

1、對于單個字節(jié)的字符，第一位設為0，后面7位對應Unicode的碼點，也就是0-127號符號，與ASCII完全相同，這也就是用UTF-8可以完美打開ASCII的編碼。

2、對于N個字節(jié)來表示的字符（N>1），第一個字節(jié)的前N位都設為1，第N+1位設為0，剩余的N-1個字節(jié)的前兩位都設位10，剩下的二進制位則使用這個字符的Unicode的碼點填充。

針對第二條編碼規(guī)則進一步做說明：

如果第一個字節(jié)的第一位是0，就說明這個字節(jié)對應一個字符

如果第一個字節(jié)的第一位是1，那么連續(xù)有多少個1（假設有N個1），就表示該字符占用了多少個字符，第N+1位是0，剩余的N-1個字節(jié)前兩位都是10開頭，剩下的二進制對應Unicode的碼點填充（依次從后向前填充，多出來的位補零）

Unicode 二進制碼點范圍 UTF-8 二進制

1個字節(jié)范圍

2個字節(jié)范圍 110xx xxxx 10xx xxxx

3個字節(jié)范圍 1110x xxxx 10xx xxxx 10xx xxxx

4個字節(jié)范圍 1111 0xxx 10xx xxxx 10xx xxxx 10xx xxxx

例如："計"的 Unicode 碼點是 0x8ba1（1000 1011 1010 0001）

對應的UTF-8編碼模式是： 1110x xxxx 10xx xxxx 10xx xxxx ， 然后將0x8ba1依次從后向前填充

得到最終的UTF-8編碼是： 1110 1000 1010 1110 1010 0001

例如："漢"的 Unicode 碼點是 0x6c49（110 1100 0100 1001）

對應的UTF-8編碼模式是： 1110x xxxx 10xx xxxx 10xx xxxx ， 然后將0x8ba1依次從后向前填充

得到最終的UTF-8編碼是： 1110 0110 1011 0001 1000 1001

UTF-16

是UTF-16也是Unicode編碼方式的一種，Unicode本身一個大的字典集合包含所有的字符集。

這么多的字符是分區(qū)定義的，每個區(qū)可以存放65536個字符（2個字節(jié)大?。┓Q為一個"平面"，目前有17個平面，也就是說整個Unicode字符集的大小是2^21個

最前面的65536（0-2^16 -1）個字符，稱為基本平面，剩余的字符都放到輔助平面

UTF-16編碼介于UTF-32與UTF-8之間，同時結(jié)合了定長和變長兩種編碼方法的特征；

UTF-16的編碼規(guī)則比較簡單：基本平面的字符占2個字節(jié)，輔助平面字符占用4個字節(jié)，UTF-16編碼長度要么是2個字節(jié)，要么是4個字節(jié)；

這樣就帶來了1個問題：

當遇到兩個字節(jié)如何如何區(qū)分是一個字符還是與后面的兩個字節(jié)當成一個字符？

這里用了一個很巧妙的地方，在基本平面內(nèi)，1101 1000 0000 0000（55296）到 1101 1111 1111 1111（57343）是一個空段，用十六進制來表示（0xD800 到 0xDFFF），這些碼點不對應任何的字符，這個空段用來映射輔助平面的字符

這段的空位，前半部分映射輔助平面的高位，后半部分映射輔助平面的地位，具體范圍如下：

高位：1101 1000 0000 0000（55296 0xD800） 到 1101 1011 1111 1111（56319 0xDBFF）

低位：1101 1100 0000 0000（56320 0xDC00）到 1101 1111 1111 1111（57343 0xDFFF）

這就說明，一個輔助平面的字符，被拆分兩個基本平面的字符表示

當遇到兩個字節(jié)，發(fā)現(xiàn)他的碼點在0xD800 到 0xDBFF 之間，就可以斷定，緊跟在后面的兩個字節(jié)碼點應該在0xDC00 到 0xDFFF之間，這四個字節(jié)就必須放在一起解碼

例如："宋" Unicode 0x5b8b（01011011 10001011），這個范圍沒有超過了基本平面的范圍（2個字節(jié)的長度）

漢字"宋'的UTF-16的編碼是：0x5b8b

例如："吉" Unicode 0x20BB7（101 1011 10001111），這個范圍沒有超過了基本平面的范圍（2個字節(jié)的長度）

首先將0x20BB7 - 0x10000（去掉前2個字節(jié)），然后將其用20個二進制表示（不足前面補0）

得到0001000010 1110110111 20位二進制

前10位映射到0xD800-0xDBFF：填充到11011000 00000000得到11011000 01000010（0xD842）

后10位映射到0xDC00-0xDFFF：填充到11011100 00000000得到11011111 10110111（0xDFB7）

因此得到的漢字"宋'的UTF-16的編碼是：0xD842 0xDFB7

UTF-16 輔助平面字符轉(zhuǎn)換公式：// Math.floor 即對浮點數(shù)向下取整// c 是對應的Unicode碼位// 0x400 1024 2^10次方H = Math.floor((c-0x10000) / 0x400) + 0xD800L = (c - 0x10000) % 0x400 + 0xDC00

Base64編解碼

在進行Http傳輸?shù)臅r候，為什么需要把Byte數(shù)組進行base64編碼呢？

答案：Http協(xié)議是文本協(xié)議，不同于二進制協(xié)議，無法直接傳輸二進制

在數(shù)據(jù)或參數(shù)的參數(shù)過程中，經(jīng)常遇到一些情況：使用全英文沒有問題，一旦涉及到中文就亂碼，還有一些網(wǎng)絡上傳輸?shù)淖址⒉皇侨纱蛴〉模热纾憾M制文件，圖片等等，Base64就是解決了此問題，是基于可打印的字符來表示二進制的數(shù)據(jù)的一種方法

早期的一些傳輸協(xié)議，例如傳輸郵件的SMTP協(xié)議，只能傳輸可打印的ASCII字符，ASCII的范圍是0-127，比如：當郵件傳輸圖片資源的時候，某一個Byte的值是10111011（187）不屬于ASCII碼的范圍，因此不支持傳輸，這個時候，Base64編碼就應運而生了，他是用6位表示原來的8位，稍等下面會仔細說明。

Base64是一種用64個字符表示任意二進制數(shù)據(jù)的方法

Base64的原理很簡單，其實就是64個字符["A","B","C","...Z","a","b","c","...z","0","...9","+","/"]

26個大小寫字符，加上10個數(shù)字，以及"+"和"/"，一共64個字符

Base64編碼1、3個字節(jié)一組，形成24位2、將24位分為4組，每組6位，每組前面增加003、形成4個字節(jié)，來表示3個字節(jié)Base64解碼c：3個字節(jié)是一組，每個字節(jié)8位，也就是24位第一個字符：c << 16 & 0xFF （取得第一個8位）（取得第一個8位）第二個字符：c << 8 & 0xFF第三個字符：c & 0xFF

URL encoding

URL編碼，也成為“百分號編碼”，是將字符串以URL編碼

編碼原理：將需要轉(zhuǎn)碼的字符串轉(zhuǎn)為16進制，從右到左，取4位（不足4位直接處理），每2位做一位，前面加上%