## 進位制、二進位存儲與運算 ### 12/22 社課 --- ## 進位制 ---- $n$ 進位 $=$ 在這個進位制有 $n$ 種數字符號 $=$ 每 $n$ 個數要進位一次 $n$ 被稱為底數（基數） 通常 $n$ 為自然數 ---- $n$ 進位中的 $a_3a_2a_1a_0$ $=a_3\times n^3+a_2\times n^2+a_1\times n^1+a_0\times n^0$ 要說明某個數是 $n$ 進位 會用$(數字)_n$ 如果 $n$ 超過 $10$，通常會接續使用大寫英文字母 ---- $10$ 進位中的 $2373$ 可以表示為 $2373_{10}$ $=2\times 10^3+3\times 10^2+7\times 10^1+3\times 10^0$ $16$ 進位中的 $2C5B$ 可以表示為 $2C5B_{16}$ $=2\times 16^3+12\times 16^2+5\times 16^1+11\times 16^0$ ---- ### 不同進位的數字念法 $1010$ 這個數字在十進位中念作「一千零一十」 但在其他進位中沒有十百千的念法 因此要讀作「一零一零」 ---- ### 各種進位轉十進位 剛剛其實就看過了 $abcd_n$ $=(a\times n^3+b\times n^2+c\times n^1+d\times n^0)_{10}$ ---- ### 十進位轉各種進位 假設我們要把 $2373_{10}$ 轉成 $8$ 進位 可以不斷除以 $8$ 直到商為 $0$ 為止 得到的餘數由後往前排就是答案 ---- $2373\div 8=296\cdots 5$ $296\div 8=37\cdots 0$ $37\div 8=4\cdots 5$ $5\div 8=0\cdots 5$ 因此我們可以得到 $2373_{10}=5505_8$ ---- 我們可以這麼思考 當 $2373$ 除以 $8$ 得到的商可以被 $8$ 整除 也就是之前看到轉十進位時有乘上 $8$ 的部分 而得到的餘數就是最後剩下的 $\times 8^0$ 以此類推 ---- ### 不同進位之間的轉換 先轉成十進位再轉一次就好了 ---- ### 小數部分 一樣的 $n$ 進位中的 $ab.cd_n$ $=a\times n^1+b\times n^0+c\times n^{-1}+d\times n^{-2}$ ---- 小數轉換時可能會出現循環小數 $1.1_3=1\times 3^0+1\times 3^{-1}=1.\overline3_{10}$ $0.3_{10}=0.01\overline{0011}_2$ （可以想想怎麼算） 由此可知，電腦在計算小數時會有誤差 ---- #### 小知識 所有二進分數$\frac{p}{2^a}$，$p, a\in N$ 都可以化為有限二進位小數（或整數） ---- #### 小知識 2 電腦中儲存顏色的方法 最常用RGB三原色各細分為256種色源 利用 $16$ 進位儲存 \#FF00FF 意思就是R:FF、G:00、B:FF --- ## 二進位在電腦中的儲存 ---- 電腦儲存的最小單位稱作「位元（bit）」 每個位元都可以表示為 $0$ 或 $1$ ---- $8$ 個 bit 稱為 $1$ byte（位元組） $1024$ byte 稱為 $1$ KiB $1024$ KiB 稱為 $1$ MiB $1024$ MiB 稱為 $1$ GiB $1024$ GiB 稱為 $1$ TiB ---- C++中 int 為 $4$ byte，即 $32$ bit，故可以存 $2^{32}$ 種數 long long 為 $8$ byte，可存 $2^{64}$ 種數 ---- #### int 儲存大概長這樣 00000000 00000000 00000000 00001010 表示 $9$ 00000000 00101001 10000100 01000100 表示 $2720836$ ---- ## 存負數？ ### 補數與二補數 ---- 假設現在有 $2^k$ 種數可以存（即 $k$ 位元） 相當於我們可以存 $[0, 2^k-1]$ ---- 若想要存負數 我們可以把一半分給非負整數 一半分給負整數 也就是 $[0, 2^{k-1}-1]$ 分給非負整數 剩下的 $[2^{k-1}, 2^k-1]$ 都分給負整數 ---- 我們讓某個 $a\in [2^{k-1}, 2^k-1]$ 表示為一個負數 $a^{\prime}$ 則我們讓 $a^{\prime}=$ 在模 $2^k$ 下與 $a$ 同餘的最大負數 即 $a^{\prime}=a-2^k$ 相當於把 $[2^{k-1}, 2^k-1]$ 映射到 $[-2^{k-1}, -1]$ 這樣我們就可以處理 $[-2^{k-1}, 2^{k-1}-1]$ 的範圍了 ---- #### 補數 對一個數 $b$ 的補數定義為 $2^k-1-b$ 也就是將 $b$ 中的 $0$ 與 $1$ 互換 0001 1110 $\rightarrow$ 1110 0001 1001 0100 $\rightarrow$ 0110 1011 C++ 中可以用 ~b 表示 b 的補數 ---- #### 二補數 對一個數 $b$ 的二補數定義為 $2^k-b$ 即補數加上 $1$ 若進位時超出 $k$ 位元的範圍，則把最高位捨去 0000 0001 $\rightarrow$ 1111 1111 0110 1001 $\rightarrow$ 1001 0111 **0000 0000 $\rightarrow$ 0000 0000** ---- $x$ 的二補數就會是在 $[2^{k-1}, 2^k-1]$ 的 $2^k-x$ 而前面提到這個數代表的就是 在模 $2^k$ 下與其同餘的最大負數 也就是 $(2^k-x)-2^k=-x$ ---- ### 結論 儲存 $x$ 的負數 $-x$ 的方式 就是存它的二補數 ---- ### 至於浮點數儲存？ 那個有點複雜 有興趣可以查查看 --- ## 位元運算 ### （bitwise operation） ---- ### <<、>>（左移、右移） 最開始看到這個符號是 cin、cout 的時候 在符號兩邊都是整數時 ```cpp= a << n; ``` 意思是 $a$ 的位元向右移 $n$ 位 ---- ```cpp= int a=10, n=3, ans; ans=(a<<n); //ans=80 ``` 如果 $a=10, n=3$ $a$ 的二進位儲存是 00000000 00000000 00000000 00001010 經過運算後會變成 00000000 00000000 00000000 01010000 ---- 發現到整體會左移 $n$ 個位元 左邊超出部分會捨棄 右邊新的部分會補 $0$ \>> 右移符號也是相同道理，位元會向右移動 ---- 其實也可以注意到 a << n 代表 $a\times 2^n$ 運算時間比直接做乘法來的快 ---- ### ~、&、|、^ 分別為 \~ bitwise not & bitwise and | bitwise or ^ bitwise xor ---- not 前面講過了，就是算補數 實際運算就是對於每個位元去做 and、or、xor 運算 ---- 7&9 $\rightarrow$ 1 7|9 $\rightarrow$ 15 7^9 $\rightarrow$ 14 可以自己練習看看