2. 進位制 *Positional notation*

# 2. 進位制 *Positional notation* ###### tags: `DLD-VHDL-kl` `中文` [TOC] --- ## 2.1 進位制 ![](https://upload.wikimedia.org/wikipedia/commons/7/78/Positional_notation_glossary-en.svg =300x) | English | 中文 | |---|---| | number | 數字 | digit | `台` 數位 `中` 數碼 | radix | `台` 數基 `中` 底數 | position | | index | |二進制 binary|八進制 octal|十進制 decimal|十六進制 hexadecimal| |:---:|:---:|:---:|:---:| | $11100_2$ | ${34}_8$ | $28_{10}$ | $1\text{C}_{16}$ |十進制|十六進制| |:-:|:-:| |$10_{10}$|$\text{A}_{16}$| |$11_{10}$|$\text{B}_{16}$| |$12_{10}$|$\text{C}_{16}$| |$13_{10}$|$\text{D}_{16}$| |$14_{10}$|$\text{E}_{16}$| |$15_{10}$|$\text{F}_{16}$| ## 2.2 進位制轉換法 * $n$ 進位無號**整數** * 最右邊位元稱為[最低有效位元](https://zh.wikipedia.org/wiki/%E6%9C%80%E4%BD%8E%E6%9C%89%E6%95%88%E4%BD%8D)（least significant bit，LSB） * 最左邊位元稱為[最高有效位元](https://zh.wikipedia.org/wiki/%E6%9C%80%E9%AB%98%E6%9C%89%E6%95%88%E4%BD%8D)（most significant bit，MSB）， * $n$ 進位無號浮點數 #### 轉換方法 * 轉換成10進位的方法——用權值（weight）來加權下式中，紅色的乘冪就是權值。 * 例1：$110.11_2 = \left(1\times\color{red}{2^2} + 1\times\color{red}{2^1} + 0 \times \color{red}{2^0} + 1\times\color{red}{2^{-1}}+ 1\times \color{red}{2^{-2}}\right)_{10} = 6.75_{10}$ * 例2：$3\text{B}4\text{F}_{16} = \left(3\times\color{red}{{16}^{3}} + 11\times\color{red}{{16}^{2}} + 4\times\color{red}{{16}^{1}} + 15\times\color{red}{{16}^{0}}\right)_{10} = 15183_{10}$ * 由10進位轉換成 $n$ 進位制的方法 > 對於整數部分，重複「除以 $n$，取餘數為數碼，取商」，直到商為零。 > 對於整數部分，重複「乘以 $n$，取整數部分為數碼，取小數部分」，直到小數部分為零。 * 例1：$18.3125_{10} = 10010.01001_2$ ``` -- 整數部分 18 / 2 = 9 ... "0" -- LSB 9 / 2 = 4 ... "1" 4 / 2 = 2 ... "0" 2 / 2 = 1 ... "0" 1 / 2 = 0 ... "1" -- MSB，商為零，結束 -- 小數部分 0.3125 * 2 = 0.6250 -- 整數部分 "0" = 小數點後第1位，取小數部分 "0.6250" 繼續算 0.6250 * 2 = 1.2500 -- 整數部分 "1" = 小數點後第2位，取小數部分 "0.2500" 繼續算 0.2500 * 2 = 0.5000 -- 整數部分 "0" = 小數點後第3位，取小數部分 "0.5000" 繼續算 0.5000 * 2 = 1.0000 -- 整數部分 "1" = 小數點後第4位，小數部分為零，結束 ``` * 例2：$54.171875_{10} = \text{36.2C}_{16}$ ``` -- 整數部分 54 / 16 = 3 ... "6" -- LSB 3 / 16 = 0 ... "3" -- MSB，商為零，結束 -- 小數部分 0.171875 * 16 = 2.75 -- "2" = 小數點後第1位 0.750000 * 16 = 12.00 -- "12" = 小數點後第2位，小數部分為零，結束 ``` ## 2.3 補數（Complements）電腦科學中**補數**（complement）的概念類似代數中的相反數（opposite）或加法反元素（additive inverse），可以細分為兩種。對於 $b$ 進制下的 $n$ 位數 $y$ 而言， * $\boxed{b^n - y}$ * 稱為 ==$y$ 的 **數基補數**（radix complement）==， * 或者稱為 ==$y$ 關於 $b$ 的補數（$b$'s complement）==。 * 這就相當於每一個數位都用 $(b-1)$ 去減，整個數再加 $1$。 * $\boxed{(b^n - 1) - y}$ * 稱為 ==$y$ 的 **縮減數基補數**（diminished radix complement）==， * 或者稱為 ==$y$ 關於 $(b-1)$ 的補數（$(b-1)$'s complement）==。 * 這就相當於每一個數位都用 $(b-1)$ 去減。[^縮減數基補數的證明] 兩種補數的關係為 * 縮減數基補數 $=$ 數基補數 $-\ 1$ * 數基補數 $=$ 縮減基數補數 $+\ 1$ ### 十進制的例子十進位數的縮減數基補數就是 ==關於 $9$ 的補數==（9's complement）。簡單來說，是==每一個數位都用 $9$ 去減==，比如 $9$ 跟 $0$ 互換，$8$ 跟 $1$ 互換，以此類推。 * $9_{10}$ 關於 $9$ 的補數為 $(10 - 9 - 1)_{10} = 0_{10}$ * $5_{10}$ 關於 $9$ 的補數為 $(10 - 5 - 1)_{10} = 4_{10}$ * $873_{10}$ 關於 $9$ 的補數為 $(10^3 - 873 - 1)_{10} = 126_{10}$ 十進位數的數基補數就是 ==關於 $10$ 的補數==（10's complement）。簡單來說，就是它==關於 $9$ 的補數加 $1$==。例如， * $9_{10}$ 關於 $10$ 的補數為 $(10 - 9 )_{10} = 1_{10}$ * $5_{10}$ 關於 $10$ 的補數為 $(10 - 5)_{10} = 5_{10}$ * $873_{10}$ 關於 $10$ 的補數為 $(10^3 - 873 )_{10} = 127_{10}$ ### 二進制的例子二進位數的縮減數基補數就是==關於 $1$ 的補數==（1's complement），中文簡稱==一補數==。簡單來說，就是對每一位進行「[位元反相操作](https://zh.wikipedia.org/wiki/%E4%BD%8D%E6%93%8D%E4%BD%9C#%E5%8F%96%E5%8F%8D%EF%BC%88NOT%EF%BC%89)」（bitwise NOT），或者說==讓 $1$ 跟 $0$ 互換==。例如， * $1010_2$ 的一補數為 $(10000 - 1010 - 1)_2 = 0101_2$ * $0110_2$ 的一補數為 $(10000 - 0110 - 1)_2 = 1001_2$ 二進位數的數基補數就是==關於 $2$ 的補數==（2's complement），中文簡稱==二補數==。簡單來說，就是它的==一補數加 $1$==。例如， * $1010_2$ 的二補數為 $(10000 - 1010)_2 = 0110_2$ * $0110_2$ 的二補數為 $(10000 - 0110)_2 = 1010_2$ ::: spoiler 參考資料 * [維基百科-補數](https://zh.wikipedia.org/wiki/%E8%A1%A5%E6%95%B0) * [一補數與二補數](https://noob.tw/complements/) ::: ## 2.4 有號數的處理前面處理的數值都只限於正數；如果要同時處理負數，就要引入**有[符]號數**（signed numbers）的概念，例如有號整數（signed integer）$-129$、有號浮點數（signed float）$-3.14$。不過電腦只會用二進位數來儲存數值，所以要依靠三種方法來將有號數「編碼」為二進位數。 1. **符號數值表示法**（sign-magnitude representation），又稱原碼（true form），它指定： * ==最高有效位（MSB）為**符號位元**（sign bit）==，用來表示正、負號。 * 符號位元為 $0$ 表示正號（$+$），例如 $\color{red}{0}010_2$ 表示十進位正數 $\color{red}+2_{10}$。 * 符號位元為 $1$ 表示負號（$-$），例如 $\color{red}{1}010_2$ 表示十進位負數 $\color{red}-2_{10}$。 * 其他位表示**大小**（magnitude），例如 $0\color{blue}{010}$ 和 $1\color{blue}{010}$ 代表的大小都是 $\color{blue}{010}_2 = 2_{10}$。 2. **一補數式**（1's complement form）是==把 $y_2$ 的一補數當成 $y_{10}$ 的相反數==。例如， * $0010_2$ 表示十進位正數 $\color{red}+2_{10}$。 * $1101_2$ 表示十進位負數 $\color{red}-2_{10}$。 3. **二補數式**（2's complement form）是==把 $y_2$ 的二補數當成 $y_{10}$ 的相反數==。例如， * $0010$ 表示十進位正數 $\color{red}+2_{10}$。 * $1110_2$ 表示十進位負數 $\color{red}-2_{10}$。下表比較三種表示法的差異，其中第一欄是「一個位元組的二進位整數」（one-byte binary integer），其他欄的都是第一欄所代表的十進位整數，省略用來表示進位制的下標。 | 二進位 | 無號數 | 有號數 符號及大小式 | 有號數 一補數式 | 有號數 二補數式 | |:-:|:-:|:-:|:-:|:-:| | $0000\ 0000$ | $0$ | $+0$ | $+0$ | $0$ | | $0000\ 0001$ | $1$ | $1$ | $1$ | $1$ | | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | | $0111\ 1110$ | $126$ | $126$ | $126$ | $126$ | | $0111\ 1111$ | $127$ | $127$ | $127$ | $127$ | | $1000\ 0000$ | $128$ | $\color{red}{-0}$ | $-127$ | $-128$ | | $1000\ 0001$ | $129$ | $-1$ | $-126$ | $-127$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | | $1111\ 1110$ | $254$ | $-126$ | $-1$ | $-2$ | | $1111\ 1111$ | $255$ | $-127$ | $\color{red}{-0}$ | $-1$ | |表示法|表示的數值範圍（十進位）| |--|--| | 符號及大小式 | $-127,\;-126,\;\ldots,\;-1,\;\color{red}{-0},\;+0,\;1,\;\ldots,\;126,\;127$ | | 一補數式 | $-127,\;-126,\;\ldots,\;-1,\;\color{red}{-0},\;+0,\;1,\;\ldots,\;126,\;127$ | | 二補數式 | $\color{red}{-128},\;-127,\;-126,\;\ldots,\;-1,\;0,\;1,\;\ldots,\;126,\;127$ | 可以看出，二補數式的範圍多了 $-128$，而「符號及大小式」和「一補數式」則是都產生了「兩種零」： * 「正零」（positive zero），記作 $+0$。 * 「負零」（negative zero），記作 $-0$。 ## 2.5 二進制的算數 ### 加法 ``` 基本規則 0 0 1 1 + 0 + 1 + 0 + 1 --- --- --- --- 0 1 1 10 ^進位例 (二進制) (十進制) 10110 22 + 11101 + 29 -------- ---- 110011 51 ``` ### 減法 ``` 基本規則 0 1 10 1 - 0 - 0 - 1 - 1 --- --- ---- --- 0 1 01 0 ^借位例 (二進制) (十進制) 10110 22 - 1101 - 13 -------- ---- 1001 9 ``` ### 減法（二補數） ==被減數 $+$ **減數的二補數** $=$ 差== ==將任何溢出的最高有效位元捨棄== ``` 例1：10110 - 1101 = 1001 （可對照上面「減法」中的例子） 10110 + 10011 (= 1101 在 5 個位元下的二補數) --------- 1 01001 ^溢位，捨棄例2：0101 1010 - 1101 1011 = 0111 1111 0101 1010 + 0010 0101 (= 1101 1011 在 8 個位元下的二補數) ------------- 0111 1111 這相當於十進制中的減法 90 - (-37) = 127 例3：1111 1100 - 1110 0111 = 0101 0101 1111 1100 + 0001 1001 (= 1110 0111 在 8 個位元下的二補數) ------------- 1 0001 0101 ^溢位，捨棄這相當於十進制中的減法 (-4) - (-25) = 21 ``` ### 乘法 ``` 基本規則 0 1 0 1 x 0 x 0 x 1 x 1 --- --- ---- --- 0 0 0 1 例1：11 * 10 = 110 (二進制) (十進制) 11 3 x 10 x 2 -------- ---- 00 6 + 11 -------- 110 例2： 1011 * 1100 = 1000 0100 (二進制) (十進制) 1011 11 x 1100 x 12 ---------------- ------ 0000 22 0 000 + 11 10 11 ------ + 101 1 132 ---------------- 1000 0100 ``` ### 除法 ``` 例1：110 / 11 = 10 (二進制) (十進制) 10 2 ------ ---- 11 ) 110 3 ) 6 - 11 - 6 ------ ---- 00 0 - 00 ------ 00 例2： 1001 1101 / 0110 = 1000 0100 (二進制) (十進制) 0000 1100 12 ------------ ------ 1101 ) 1001 1100 13 ) 156 - 0000 - 13 ------------ ------- 1001 1 26 - 0110 1 26 ------------ ------- 0011 01 0 - 0011 01 ------------ 00 0000 00 0000 ------------ 00 0000 ``` ## 2.6 十六進制的算數 ### 加法 ``` 例：(2BC9 + 50FA)₁₆ = 2BC9₁₆ (十六進制) (十進制) 2BC9₁₆ 11209₁₀ + 50FA₁₆ + 20730₁₀ ---------- --------- 2BC9₁₆ 31939₁₀ (9 + A)₁₆ = (9 + 10)₁₀ = 19₁₀ = 13₁₆，進位 (C + F + 1)₁₆ = (12 + 15 + 1)₁₀ = 28₁₀ = 1C₁₆，進位 (B + 0 + 1)₁₆ = (11 + 0 + 1)₁₀ = 12₁₀ = C₁₆ (2 + 5)₁₆ = (2 + 5)₁₀ = 7₁₀ = 7₁₆ ``` ### 減法 ``` 例：(87 - 3D)₁₆ = 4A₁₆ 87₁₆ 135₁₀ - 3D₁₆ + 61₁₀ --------- --------- 4A₁₆ 74₁₀ (7 - D)₁₆ = (7 - 13)₁₀ ，不夠減，借位 (17 - D)₁₆ = (23 - 13)₁₀ = 10₁₀ = A₁₆ (8 - 3 - 1)₁₆ = (8 - 3 - 1)₁₀ = 4₁₆ ``` 亦可換成二進位數之後，用二補數減法。 ``` 例：(87 - 3D)₁₆ = 4A₁₆ 87₁₆ = 1000 0111₂ 3D₁₆ = 0011 1101₂ (1000 0111 - 0011 1101)₂ = 0100 1010₂ 1000 0111₂ + 1100 0011₂ ------------ 1 0100 1010₂ ^溢位，捨棄 0100 1010₂ = 4A₁₆ ``` [^縮減數基補數的證明]: 證明如下：對於 $b$ 進制下的 $n$ 位自然數 $y = \sum_{k=0}^{n-1}a_kb^k$，其中 $a_k \in \{0,1,\ldots,b-1\}$ 是第 $k$ 個數位，$b^k$ 是第 $k$ 個權數，則 $y$ 的縮減數基補數為 $$\begin{align} \left(b^n - 1\right) - y &= (b-1)\left(b^{n-1} + \cdots + b + 1\right) - y \\ &=(b-1)\left(\sum_{k=0}^{n-1}b^k\right) - \sum_{k=0}^{n-1}a_kb^k \\ &= \sum_{k=0}^{n-1}\left[(b-1)-a_k\right]b^k\end{align}$$ 可見第 $k$ 個數位由 $a_k$ 變成了 $(b-1)-a_k$。