iT邦幫忙

2021 iThome 鐵人賽

DAY 1
0
Software Development

微自幹的作業系統輕旅行系列 第 3

數值系統與補數

本文目標

  • 了解計算機如何儲存資料
  • 了解計算機如何處理負數以及減法
  • 練習進制間的轉換

進制系統

進位制是一種記數方式,利用這種記數方式,人類可以使用有限種數字符號來表示所有的數值。
一種進位制中可以使用的數字符號的數目稱為這種進位制的基數或底數,若一個進位制的基數為 n,即可稱之為 n 進位制 (即 n 進位)。
現今最常用的進位制是十進位,這種進位制通常使用 10 個阿拉伯數字(即 0-9)進行記數。
-- 修改自維基百科

有了進位制系統,我們可以用不同的基數來表示同一個數值,十進位數字 28 為例:

10 進制 2 進位 8 進位 16 進位
28 11100 34 1C

2 進制

遇到 2 就進位:

10 進制 2 進制
0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111

8 進制

遇到 8 就進位

10 進制 8 進制
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 10
9 11
10 12

16 進制

在 16 進制系統中,可以使用 0 - 15 來表達數值,不過其中的 10 - 15 本身就已經是進位過後的結果了,所以我們會使用英文字母取代 10 - 15 :

10 進制 16 進制
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 A
11 B
12 C
13 D
14 E
15 F
16 10

進制轉換

8 進制轉 2 進制

在 8 進制系統中,1 個位元可以表示 8 種狀態,若以二進制系統我們則需要 3 個位元才能夠表示 8 種狀態。
要將 8 進制轉為 2 進制系統也非常簡單,只要將 8 進制系統的單一位元轉為 2 進制的 3 個位元即可:

34 (8) -> 011 100 -> 11100 (2) -> 28 (10)

16 進制轉 2 進制

在 16 進制系統中,1 個位元可以表示 16 種狀態,若以二進制系統我們則需要 4 個位元才能夠表示 16 種狀態。
要將 16 進制轉為 2 進制系統也非常簡單,只要將 16 進制系統的單一位元轉為 2 進制的 4 個位元即可:

1C (16) -> 0001 1100 -> 11100 (2) -> 28 (10)

n 進制與 10 進制的相互轉換

以下範例皆以 n = 2 作為示範。

現在考慮小數點的情況,將二進制數 10011.011B 轉換成十進制數字:

了解二進制如何轉為十進制之後,再來學習十進制轉為二進制的技巧:

  • 整數部份採用以 n 為除數的連除法,直到商小於除數為止,則答案取其所有餘數
  • 小數部份採用以 n 為乘數的連乘法,直到積等於零為止,則答案取其所有「進位」。若積數無法至 0,則須取到所指定的位數 (位數越多,轉換值越精確)

補數系統

1's 補數

將二進位數按位元逐個反轉,就可以得到的其 1's 補數(ones' complement)。

舉例

0001 (+1) 的一補數為 1110 (-1)
按照上面的範例,我們一次列舉出更多的數字出來:

2 進制 無號數 有號數 一補數
0000 0 0 0
0001 1 1 1
0010 2 2 2
0011 3 3 3
0100 4 4 4
0101 5 5 5
0110 6 6 6
0111 7 7 7
1000 8 -0 -7
1001 9 -1 -6
1010 10 -2 -5
1011 11 -3 -4
1100 12 -4 -3
1101 13 -5 -2
1110 14 -6 -1
1111 15 -7 -0

1's 補數加法

一補數的特性可使加法電路同時可以運算減法,像是:

0001 (1) + 1100 (-3) = 1101 (-2)

2's 補數

不管事一補數或是有號數的儲存方式都會產生 -0 這個結果,為了避免這個問題,電腦科學家又進一步發展出二補數,二補數的計算方式非常簡單:

  • MSB 最高位元為負數
  • 其餘皆為正數
  • 任何數字的二補數都等於其一的補數 + 1

舉例

-7 為例,我們先將其轉為一補數:

1000

接著將一補數 +1 得到二補數:

1001

至於剛剛提到的 MSB 最高位元為負數,其餘皆為正數 這兩條規則,我們可以用來進行驗算:

-8 (MSB) 4 2 1 (LSB)
1 0 0 1

(-8)x1 + 4x0 + 2x0 + 1x1 = -7

總結

在學習編寫系統程式時,進制間轉換與補數系統是必備的基本技能之一,現今的電腦多採用二進制系統 + 二補數系統來儲存資料,所以在學習進階技巧之前才會特別規劃一篇文章供讀者複習,希望能夠幫助到大家。

Reference


上一篇
一次搞懂 ISA、CISC 與 RISC
下一篇
關於計算機,你必須知道的事: CPU 快取
系列文
微自幹的作業系統輕旅行38

尚未有邦友留言

立即登入留言