C語言程式設計導論-位元運算與資料的儲存

### C語言程式設計導論 ### 位元運算與資料的儲存 ---  <h3 class="text-left"> Table of Contents </h3> - 二進位數字 - 資料的儲存 - 認識位元運算 - 位元運算子 - 程式範例 - 例題練習 ----  ### 為了節省講義空間 ### 從這裡開始會習慣性省略以下幾行程式 ```cpp #include<stdio.h> int main(){ return 0; } ```  ---  ### 二進位數字 ----  **我們一般看到的數字都是十進位的數字** **十進位的數字意旨每十個數字進一位** **因此每位數字只能是$0$~$9$** ----  **那麼二進位就是每二個數字進一位** **數字只能是$0$或者$1$** **這特性剛好與電路通電與不通電的特性合得來** **因此電腦的底層儲存的都是二進位的數字**  ----  <h3 class="text-left"> 不同進位的數字在數學上的表示法 </h3> <p class="text-left"> <b> 基本上就是數字加小括號右下角加小標代表進位制 </b> </p> - **十進位:** $(87)_{10}$ - **二進位:** $(1010111)_{2}$ - **八進位:** $(3254)_{8}$ ----  **換種方式來看十進位** **我們可以把十進位數字$(1782)_{10}$粗略的這樣做拆分** $(1782)_{10}=1\times 10^{3}+7\times 10^{2}+8\times 10^{1}+2\times 10^0$ ----  **想當然二進位數字$(1011)_{2}$大概就會長這樣** $(1\times 2^3+0\times 2^2+1\times 2^1+1\times 2^0)_{10}=(11)_{10}$ ----  **那我們要怎麼從十進位轉成二進位呢** **可以使用短除法**  ----  <p class="text-left"> <b> 以十進位數字87舉例 <br> 可以發現 <br> 每次除一次2的餘數 <br> 都會由小到大 <br> 變成二進位的位數 </b> </p> <img src="https://hackmd.io/_uploads/Sy6-wEqqA.png" style="position: absolute; right: 150px; top: 0px;width: 30%; height: 600%"> ----  **那如何把二進位數字轉成十進位呢** **不用想太多乘完之後直接加就好**  ----  **以數字$(1011)_{2}$為例** $(1\times 2^3+0\times 2^2+1\times 2^1+1\times 2^0)_{10}=(11)_{10}$ ----  <p class="text-left"> <b> <br> <br> <br> 如果要用3bit表示數字的話 <br> 大概會長這樣 <br> <br> <br> <br> <br> </b> </p> <img src="https://hackmd.io/_uploads/HkCkKBqqC.png" style="position: absolute; right: 120px; top: 0px;width: 30%; height: 100%"> ----  **補充要說的是** **十六進位在資訊領域也是蠻常見的** **基本上會把$10$\~$15$寫成$A$\~$F$** **轉換方法跟前面提及的差不多** **很trivial 所以在此不多贅述** ---  ### 資料的儲存 ----  **這邊只是粗淺的題及各資料型態是怎麼儲存** **如果想知道完整的知識可以去學大學的計算機組織與架構、計算機概論與數位邏輯設計** ----  **電腦是通過電壓的大小 high 或是 low 來看要存哪一種資料** **因此只會有兩種狀態: $0$、$1$** ----  **在每一個bit中我們也只會用$0$、$1$表示** **以下就分別來講各種C語言的資料型態如何儲存** ----  <h3 class="text-left"> 整數int </h3> **用$4$bytes也就是$32$bits儲存** **可以用$32$個格子來表示** **第一個格子叫做sign bit 如果是$0$就是正的 $1$就是負的** ![image](https://hackmd.io/_uploads/rJSxErcq0.png) ----  <h3 class="text-left"> 整數int </h3> <p class="text-left"> <b> <br> 以一個3bit的系統來說 <br> 所有能代表的數字 <br> 大概長這樣 <br> <br> 這種表示法叫做二補數 <br> <br> </b> </p> <img src="https://hackmd.io/_uploads/SkFTBSc50.png" style="position: absolute; right: 120px; top: 0px;width: 30%; height: 100%"> ----  <h3 class="text-left"> 整數int </h3> <p class="text-left"> <b> <br> 如果要把正的變成負的 <br> 要把 0 變成 1 <br> 把 1 變成 0 <br> 然後 + 1 <br> <br> 然後你就會發現 <br> 最後的 -4 不適用 </b> </p> <img src="https://hackmd.io/_uploads/SkFTBSc50.png" style="position: absolute; right: 120px; top: 0px;width: 30%; height: 100%"> ----  <h3 class="text-left"> 浮點數float </h3> **用$4$bytes也就是$32$bits儲存** **大致可以分為三個部分** **sign, exponent, mantissa** ![image](https://hackmd.io/_uploads/S1hJoS5cR.png) ----  <h3 class="text-left"> 浮點數float </h3> **sign: 正負號($S$)** **exponent: 位移量($E$)** **mantissa: 尾數($M$)** **一個浮點數寫起來就會是** $S\times M\times 2^E$ ----  <h3 class="text-left"> 浮點數float </h3> **舉例將$7.25$化成浮點數儲存** 1. **判斷正負: 正** 2. **將其化為二進制: $111.01$** 3. **將小數點移到最前面: $1.1101$ 發現位移量為$2$ 並捨去最前面的$1$** 4. **計算$E$加上$2^8-1$其中$8$為格子數量:** $E=(2^8-1)+2=(129)_{10}=(1000 0001)_{2}$ 5. **寫答案:** $01000000111010000000000000000000$ ----  <h3 class="text-left"> 浮點數float </h3> **可以驗算一下** $S=+1$ $E=129-127=2$ $M=(0.1101)_{2}+1=1.8125$ $S\times M\times 2^E=7.25$ ----  **因為格子都是有限的** **所以當紀錄的數字超出格子時就會溢位** **導致數字出現錯誤** ----  **以上看不懂沒關係** **反正是大學的東西** ---  ### 認識位元運算 ----  **電腦處理位元運算是基於電路的邏輯閘** **邏輯閘的基礎是基於布林代數**  **所以先來講講布林代數在幹嘛**  ----  <h3 class="text-left"> 布林代數 </h3> - **布林代數是由[喬治·布爾](https://zh.wikipedia.org/zh-tw/%E4%B9%94%E6%B2%BB%C2%B7%E5%B8%83%E5%B0%94)提出** - **主要是處理邏輯問題將邏輯從哲學轉化成數學** - **只有兩種元素: Ture($1$), False($0$)** - **被信息學之父[克勞德·香農](https://zh.wikipedia.org/zh-tw/%E5%85%8B%E5%8A%B3%E5%BE%B7%C2%B7%E9%A6%99%E5%86%9C)用於處理電路問題** - **現今主要用於數學論證與電路設計上** ----  <h3 class="text-left"> 布林代數 </h3> **主要有四種運算元是寫程式常用到的** - OR $\lor$ 或 - AND $\land$ 且 - NOT $\neg$ 否 - XOR $\oplus$ 異或 ----  <h3 class="text-left"> 布林代數 </h3> **我們可以用真值表來看所有的運算** |$P$|$Q$|$P\lor Q$|$P\land Q$|$P\oplus Q$ |----|----|----|----|----| |0|0|0|0|0| |0|1|1|0|1| |1|0|1|0|1| |1|1|1|1|0|  **左邊是$P$、$Q$分別代入的數字右邊是運算結果**  ----  <h3 class="text-left"> 布林代數 </h3> **這是NOT$\neg$的真值表** |$P$|$\neg P$| |----|----| |0|1| |1|0| ----  **真值表列出的幾乎就是定義了** **而這些也可以幫助我們簡化邏輯的表示**  ----  **設$P$、$Q$敘述為「會下雨」、「地面會溼」** **那這樣的敘述就可以寫成$\neg P\lor Q$**  ----  **可以用真值表來驗證** |敘述|$P$|$Q$|$\neg P\lor Q$|結果| |----|----|----|----|----| |沒下雨地面沒溼|0|0|1|成立| |沒下雨面板溼|0|1|1|成立| |下雨地面沒溼|1|0|0|不成立| |下雨地面溼|1|1|1|成立| ----  **當我們使用布林代數來處理位元問題時** **這就稱為位元運算**  ----  **假如說我寫 $5$ or $6$ 那就會得到 $7$** ![image](https://hackmd.io/_uploads/BJC1tAcqR.png) ----  **假如說我寫 $5$ xor $6$ 那就會得到 $3$** ![image](https://hackmd.io/_uploads/H1S8KRqc0.png) ---  ### 位元運算子 ----  **講了這麼多** **回來說一下C語言之中要怎麼處理位元運算** ----  <h3 class="text-left"> 位元運算子 </h3> **C語言中的位元運算子只適用於整數int** |運算|數學符號|C運算子| |---|---|----| |OR|$\lor$|\|| |AND|$\land$|&| |XOR|$\oplus$|^| |NOT|$\neg$|\~| |左移|$\div 2$|<<| |右移|$\times 2$|>>| ----  <h3 class="text-left"> 位元運算子 </h3> **比較特別的是>>、<<** **在十進位的意思就是$\div 2$、$\times 2$**  **但是在二進位的意思就是左移與右移**  ----  <h3 class="text-left"> 位元運算子 </h3> $5 \times 2 = 5 << 1 = (101)_2 << 1=(1010)_2=10$ $5 \div 2 = 5 >> 1 = (101)_2 >> 1=(10)_2=2$ **左移後最右邊的位置要補$0$**  ----  **這些位元運算子也可以加個=** **變成賦值運算子** ----  **由於位元運算子在C語言優先度非常低** **要使用時記得括號括好** ----  **補充** **有一個好用的函式__builtin_popcount()** **可以帶入數字計算二進位中$1$的數量** ---  ### 程式範例 ----  **二進位轉十進位可以先用字串儲存二進位** ```cpp // bi[]: 輸入的字串, ans: 儲存答案 void binary_to_decimal(char bi[], int &ans){ int len = strlen(bi), ret = 0, ep = 1; // len: 字串長度, ret: 紀錄運算過程, ep: 2的次方數 for(int i = len - 1; i >= 0; i--){ ret += (bi[i] - '0') * ep; ep <<= 1; } ans = ret; } ``` ----  **十進位轉二進位** **答案以字串儲存** ```cpp void decimal_to_binary(int &n, char ans[]){ int idx = 0; // 這就是陣列編號 while(n){ // 這過程相當於短除法 ans[idx++] = (n & 1) + '0'; // (n & 1) 就是 (n % 2) n >>= 1; // 除以 2 } ans[idx] = '\0'; // 字串末尾一定要加上 '\0' int len = strlen(ans); // 字串長度 for(int i = 0; i < len / 2; i++){ // 字串前後reverse過來 char tmp = ans[i]; // 做交換 ans[i] = ans[len - 1 - i]; ans[len - 1 - i] = tmp; } } ``` ---  ### 例題練習 ----  [Zerojudge c461. apcs 邏輯運算子 (Logic Operators)](https://zerojudge.tw/ShowProblem?problemid=c461) [Zerojudge e797. p4. 數位邏輯運算](https://zerojudge.tw/ShowProblem?problemid=e797) [Zerojudge a132. 10931 - Parity](https://zerojudge.tw/ShowProblem?problemid=a132) [Zerojudge b005. 布林矩陣的等價短陣](https://zerojudge.tw/ShowProblem?problemid=b005) [Zerojudge a414. 位元運算之進位篇](https://zerojudge.tw/ShowProblem?problemid=a414) [Zerojudge d632. C and S ??](https://zerojudge.tw/ShowProblem?problemid=d632) [Zerojudge e253. a + b problem](https://zerojudge.tw/ShowProblem?problemid=e253) [Zerojudge e545. 10019 - Funny Encryption Method](https://zerojudge.tw/ShowProblem?problemid=e545) [Zerojudge e799. p6. 資工系的浪漫](https://zerojudge.tw/ShowProblem?problemid=e799) [CSES Range Xor Queries](https://cses.fi/problemset/task/1650/) ---  ### 以上就是本章節的內容