計算機組織/概論

有號數字表示法 — 2 的補數、1 的補數 與 符號大小

進制 簡介 一文中,簡單的介紹了 進制 的概念,
進制的轉換、負數與運算,
讓我們能使用熟悉的 十進制 (Decimal) 或 十六進制 (Hex)…,
而不用背長串的 『10010100001111…』,
更有利於我們了解計算機組織、組合語言…,並增進程式效率 😆。
 


 

有號數字 及 無號數字
(Signed and Unsigned Numbers)

 
在數學領域中,整數 (Integer) 包含了:
Zahlen
 
 
正整數 與 0,可直接透過 進制轉換,轉為計算機使用的 二進制。
也就稱為 『無號』數字 (Unsigned Numbers) 啦 !
(因沒有 『+』與『-』符號)
 
例如:
C 語言中,就有以下 Unsigned Integer Types:

_Bool (since C99), unsigned char, unsigned short, 
unsigned int, unsigned long, unsigned long long (since C99)

 
資料庫也常見到如下欄位屬性:

  • UNSIGNED
  • UNSIGNED ZEROFILL

 
在計算計組織中,無號數字 最常用於表示 記憶體位址 [註1] 😉
 
 
然而,負數呢?
 
 
想表示一負數,我們只要加個 『 – 』即可 (ex: -1),
但是:

計算機硬體,使用的是 『 0 』與『 1 』的二進制,
無法理解 負『 – 』的符號

 
我們必須找到一種方式,表達數的正 (+)負(-)
也就是 『有號』數字 (Signed Numbers) 表示法 !
 
[註1]:
為何記憶體位址不應為負? 可參考 陣列 (Array) 簡介
 


 

有號數字 表示法
(Signed Number Representations)

常見的 有號數字 表示法 (Signed Number Representations) 有四種:

  • 符號大小 (Sign and Magnitude)
  • 1 的補數 (Ones’ Complement)
  • 2 的補數 (Two’s Complement)
  • 偏移表示法 (Biased Notation)

 

前三者,大於等於 0 的 正數,與一般二進制沒有不同,
區別在於 『負數』 的表示 !

 
與其說是不同方法,它們之間更像是延伸關係。
 
在逐一介紹他們前,
得先知道 『一般二進制』 與 『計算機二進制』的差異 !
 
就像十進制中,0000000….0087 = 87,
真實的數 是可擁有無限多個位數 (digit) 的。
(當然,一般會省略多餘的 0)
 
但是:

計算機存取的字組大小是固定的

 
意味著:

  1. 「數」的 存取範圍 有限。
  2. 「數」的放置 必須遵守某種格式 (format)。
  3. 與一般二進制的轉換,可能沒意義
    (ex: 1111 可能代表的是 -1,而非 15)
  4. 兩數的運算結果,有可能超出範圍,而發生 滿溢 (overflow)

 
這也是為何,我們在書寫時,可能會這樣寫:

8710 =  10101112

 
也可能

8710 =  0000  0000  0101  01112

 


 

符號大小 (Sign and Magnitude)

符號大小 (Sign and Magnitude),又稱 原碼,是其中最淺顯易懂的,也就是:

用一個位元 (bit) 來表示 正(+)、負(-)

 
(例: 『0』代表正數、『1』代表負數)
這樣的位元,稱之為 符號位元 (sign bit)
且通常為 最高有效位元
 
由前面觀點已知,計算機字組是使用 『固定大小』,
假設以 8位元 表示一數,
除去『符號位元』後,用於表示數值的部分剩下 7位元:
sign-magnitude
 
 
同理,使用 n位元 表示一整數,
除去『符號位元』後,用於表示數值的部分剩下 n-1 位元。

十進制符號大小
+ 2n-1-10111 1111 1111 …. 1111
.
.
.
.
+ 20000 0000 0000 …. 0010
+ 10000 0000 0000 …. 0001
0+ 00000 0000 0000 …. 0000
– 01000 0000 0000 …. 0000
– 11000 0000 0000 …. 0001
– 21000 0000 0000 …. 0010
.
.
.
.
– 2n-1-11111 1111 1111 …. 1111

 

正數表達範圍: 『 + 0  ~  + 2 n-1 – 1 』 ,負數表達範圍: 『 – 0  ~  – 2 n-1 – 1 』

 
值得注意的是:

符號大小 (Sign and Magnitude) 表示法的 +0、-0 是不一樣低!

 
且當執行加法運算時,無法預知結果的正負,
加法器可能需要額外的步驟來設定符號。
 
雖然這些因素,使得 符號大小 (Sign and Magnitude) 不宜表示 整數 與 實作加法器,
卻適合用於 浮點數的表示,將於未來提及。
 


 

1 的補數 (Ones’ Complement)

1 的補數 (Ones’ Complement),又稱 反碼 ,欲計算負值:

藉由 反轉/反向 ( inverse ) 每一個位元,
原本是 『 1 』 就變 『 0 』,『 0 』就變 『 1 』

 

2n  –  x  –  1
(n 為位元數,x 為欲轉換正數)

 
例如 (4位元 1 的補數):
『 3 』,表示為: 0011;
『 -3 』,就是 『 3 』的反向,表示為: 1100。
 
正數的最大值為: 0111 1111 1111 … 1111,
負數的最大值為: 1000 0000 0000 … 0000。

十進制1 的補數
+ 2n-1-10111 1111 1111 …. 1111
.
.
.
.
+ 20000 0000 0000 …. 0010
+ 10000 0000 0000 …. 0001
0+ 00000 0000 0000 …. 0000
– 01111 1111 1111 …. 1111
– 11111 1111 1111 …. 1110
– 21111 1111 1111 …. 1101
.
.
.
.
– 2n-1-11000 0000 0000 …. 0000

 

正數表達範圍: 『 + 0  ~  + 2 n-1 – 1 』 ,負數表達範圍: 『 – 0  ~  – 2 n-1 – 1 』

 

0 依然有兩種表示法 +0、-0。

 

1 的補數和 (Ones’ Complement Sum)

使用 1 的補數加法之和,即稱 — — 1 的補數和。
減法 可以透過一個『負數』來完成。
 
例如:
3 – 2 運算,可以透過 3 + (-2) 來完成。
 
『 3 』 表示為: 0011,
『 + 』為 1 的補數加法 (常表示為: {+1s}、+’),
『 -2 』表示為: 1101。
(4 位元)
 
one's-complement-sum
 
如果有『爆掉』的位數,要再將它加回,稱為 — — 端回進位 (end around carry)
也就是將任何溢出的最高有效位元,加回最低有效位元。
這是 1 的補數的重要性質!
 

這樣的性質,讓 1 的補數 (Ones’ Complement)
做到 位元組順序獨立 (Byte Order Independence),
也就是 重新排序的輸出 等價於 重新排序的輸入。

 
例如:
計算 位元組 A, B, C, D, … , Y, Z. 的 1 的補數和,
大頭端: [A,B] +’ [C,D] +’ … +’ [Y,Z]
小頭端: [B,A] +’ [D,C] +’ … +’ [Z,Y]
計算出來的結果,經 swap 後將會相同!
 
由於 位元組順序獨立 的特性,使多位元組的加法,
能以相同的形式,進行跨位元組的進位,
而不用管主機位元組順序
 
1 的補數 (Ones’ Complement)
廣泛應用於 網路通訊協定的檢驗和 (Checksum) 計算,
甚至常作為 反向運算 的代名詞。
 
事實上:

有號數表示、加法器實作…,仍是以 2 的補數為主,
1 的補數,僅作為一種『通用的』計算機制。

 
 

2 的補數 (Two’s Complement)

然而, 1 的補數 仍具有兩個 0 (+0、-0),
加法器在做減法時,常需要一個額外的步驟,做端回進位。
 
2 的補數 (Two’s Complement) 即可避免以上問題,
因此不管是程式語言 的 整數表示加法器的實作… 幾乎皆採用 2 的補數 表示法。
 
2 的補數,或稱 補碼:

同 符號大小、1 的補數,
大於等於 0 的 正數,與一般二進制沒有不同,
區別在於 『負數』 的表示 !

 
而 2 的補數之『負數』,
其實就是 1 的補數 + 1

2n  –  x
(n 為位元數,x 為欲轉換正數)

 
例如:
『 3 』,表示為: 0011;
『 -3 』的 1 的補數 表示為: 1100,
則『 -3 』的 2 的補數 即為: 1101
 
正數的最大值為: 0111 1111 1111 … 1111,
負數的最大值為: 1000 0000 0000 … 0000。

十進制2 的補數
+ 2n-1-10111 1111 1111 …. 1111
.
.
.
.
+ 20000 0000 0000 …. 0010
+ 10000 0000 0000 …. 0001
00000 0000 0000 …. 0000
– 11111 1111 1111 …. 1111
– 21111 1111 1111 …. 1110
– 31111 1111 1111 …. 1101
.
.
.
.
– 2n-11000 0000 0000 …. 0000

 

正數表達範圍: 『 0  ~  + 2 n-1 – 1 』 ,負數表達範圍: 『 – 1  ~  – 2 n-1 』,
有一個沒有對應正值的負數  – 2 n-1

 

0 只有一種表示法 0000 0000 … 0000,
具有所有負數最高有效位元皆為 1 的優勢。

 
減法 一樣可透過 一個『負數』來完成。
 
例如:
3 – 2 運算,可以透過 3 + (-2) 來完成。
 
『 3 』 表示為: 0011,
『 + 』為 2 的補數加法 (常表示為: {+2s}),
『 -2 』表示為: 1110。
(4 位元)
 
two's-complement-sum
 
如果有『爆掉』的位數,不需端回進位 (end around carry)
 


 

偏移表示法 (Biased Notation)

儘管 2 的補數表示法,做為有號數表示、加法器實作…有絕對優勢,
其負數在真實二進位中,像是一個很大的正數,排序上並不直覺。
例:

2's 補數: 1000 = 負數 -8

一般二進位: 1000 = 正數 8

 
偏移表示法 (Biased Notation),又稱 移碼 excess-N
即是透過將原數的 2 的補數,
再加上一個 偏移值 而得。
 
例如:
二進位浮點數算術標準 (IEEE 754) 中,
單精度浮點數的偏移值為 127。
 
『 -1 』的 2’s 補數: 1111 11112
而 偏移值 127 之偏移表示法: -1 + 127 = 126 = 0111 11102
 
『 1 』的 2’s 補數: 0000 00012
而 偏移值 127 之偏移表示法: 1 + 127 = 128 = 1000 00002
 
偏移表示法,廣泛的應用於 浮點數表示法 的 指數欄位
 


 

總結

好的設計需要有好的折衷 ( Good design demands good compromises )

 
這幾種方法,沒有孰優孰劣,只有適不適合 !
 
如:
浮點數表示法標準 — — 符號大小、偏移表示法,
網路通訊協定的檢驗和 — — 1 的補數,
程式語言 的 整數、加法器的實作 — — 2 的補數,
各自運用於不同領域。
 
學習 有號數字 表示法,有助於理解許多計算機、通訊協定的知識 😁
 
 

作者: 鄭中勝

喜愛音樂,但不知為何總在打程式 ?
期許能重新審視、整理自身所學,幫助有需要的人。

發表迴響