1. 字節
2. 位運算
3. 二進制實現加減乘除
4. 講一下四則運算表達式
5. 字符編碼
6. Bas64編解碼
7. URL encoding

字節

0 或 1

1byte = 8位

一個字節的範圍-128~127, 2^8 = 256

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

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

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

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

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

位運算

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

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

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

~ 取反：0變1，1變0

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

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

1. 清零（所有位都和0做與運算）
2. 取一個數的指定位（例如：1010 1110，取低四位的數，和 0000 11111做與運算，得出1110）
3. 判斷奇偶（根據末尾進行判斷，0是偶數，1是奇數，if（x&1 == 0））

<code>if (x & 1 == 0) return TURE;
return FALSE;/<code>

• 或運算

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

• 異或運算

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

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

1. 翻轉指定位（例如：1010 1110，將其低四位進行翻轉，和0000 1111做異或運算，得到1010 0001）
2. 交換兩個數，且無需引用多餘的指針（a=a^b;b=a^b;a=a^b;）

<code>void swap(int &a, int &b)
{
\t\tif (a !=b)
  \t{
  \t\t\ta = a^b;
    \t\tb = a^b;
    \t\ta = a^b; // 注意此時的a=a^b;此時的b=a;
 \t \t}
}/<code>

• 取反運算

總結：對一個二進制數位取反，0變1，1變0

~1 = 0； ~0 = 1；

1. 使一個數的最低位為0（例如：1010 0001 & ~1 = 1010 0000，~運算符的優先級高於其它符號）

• 左/右移運算

1. 左移1位（相當於乘以2，1010 0001 << 2 = 10 1000 0100）
2. 右移1位（相當於除以2，1010 0001 >> 2 = 10 1000 00）
3. 用於進位操作

二進制實現加減乘除

• 加法

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

例如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

證明：兩個數字相加的時候，不考慮進位的值相加，最後再加上進位的值，得出最終的結果；

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

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

1. 首先不考慮進位的情況下

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

2.接著考慮進位的問題

<code>1 + 1 = 1（1 & 1 = 1）
1 + 0 = 0 （1 & 0 = 0）
0 + 1 = 0 （0 & 1 = 0） 

0 + 0 = 0 （0 & 0 = 0）
規律如下：符合與運算/<code>

3.相加 a + b

<code>不進位值相加 = a ^ b
進位的值相加 = a & b << 1
累計相加 = a ^ b + a & b << 1

遞歸循環調用，直至進位的值相加為0，也就是說無需再次進位
a + b = a ^ b + a & b << 1

int add(int a, int b)
{
\tif (b == 0 ) return a;
\treturn add(a ^ b,a & b << 1);
}
/<code>

• 減法

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

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

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

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

2、將反碼加1

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

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

<code>int multiplyAction(int a, int b)

{
\t // 首先取絕對值
  int a1 = a < 0 ? subtraction(0,a) : a;  
  int b1 = b < 0 ? subtraction(0,b) : b;
  int product = a1;

  while(--b1)
  {
  \tproduct = addition(product,a1);
  }
\t// 判斷正負
  if (a < 0 | b < 0)
  {
    // 取反加1，得到負數
  \treturn addition(~product,1);
    // return subtraction(0,product)
  }
  return product;
}/<code>

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

<code>int division(int a, int b)
{
\t// 首先取絕對值
  int a1 = a < 0 ? subtraction(0,a) : a;  
  int b1 = b < 0 ? subtraction(0,b) : b;
  int productCount = 0;
  while(true)
  {
  \t \ta1 = subtraction(a1,b1);
\t\t\t// 判斷餘數，計算四捨五入
    \tif (a1 < b1)
      {
        \tif ((b1 >> 2) > a1){
          \t\tbreak;\t
          }
      }
 \t    productCount = addition(productCount,b1);
  }
  // 判斷正負
  if (a < 0 | b < 0)
  {
    // 取反加1，得到負數
  \treturn addition(~productCount,1);
    // return subtraction(0,product)
  }
 \treturn productCount;
}

// 此方法的效率比較低，如果除數比被除數大很多的時候，就增加了很多次的遍歷，通過算法相減的方法
// 目前是按照1倍被除數相減，當然了也可以按照2倍，3倍甚至多倍的思路來實現 

// 有興趣的同學，可以再此算法上做繼續的優化/<code>

講一下四則運算表達式

計算器的加減乘除是如何實現的（數學表達式的求值方式）

計算規則：先乘除，後加減，從左到右，先括號後括號外

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

1. 首先看一下中綴表達式
2. 中綴表達式如何轉後綴表達式
3. 後綴表示是如何計算結果的

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

• 那麼如何將中綴表達式轉換為後綴表達式呢？

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

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

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

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

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

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

5、第4個字符是*，對比棧頂-，*優先級高於棧頂，入棧，【棧：- *】

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個字符是+，對比棧頂*，優先級低於棧頂，全部出棧，【輸出：3 5 6 3 / * -】【棧：+ 】

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

13、第12個字符是/，對比棧頂+，優先級高於棧頂，所以入棧，【棧：+ /】

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 * / +】

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

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

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

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

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

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

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

5、第5個字符是/，取得棧頂2個元素進行計算（3 和 6 出棧），6 / 3 = 2 ，將2入棧【棧：3 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、字符變量結束，最後一個元素出棧得出結果:-83/12

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

中綴表達式轉化後綴表達式的過程（簡化版）

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 -

四則表達式，其實就運用了棧的思想，實現了後綴表達式

1、將中綴表達式轉化為後綴表達式（按照加減乘除優先級來運算符號，去除了括號）

2、將後綴表達式進行運算得出結果（進行運算數字，注意運算的順序）

編碼

• ASCII碼

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

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

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

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

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

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 ÿ

大小規則的定義：

常見ASCII碼的大小規則：0~9

閱讀更多 小宋之 的文章

關鍵字: 每組 一組 字節