Learning Objectives
- 說出 n 位元無號整數與二補數有號整數能表示的範圍
- 用「最高位的權重是負的」讀出二補數的值，用「每一位反轉再加 1」求一個數的負數
- 說明同一組位元在無號與有號解讀下代表不同的值
- 判斷一個加法有沒有溢位：無號看最高位有沒有進位出去，有號看兩正得負、兩負得正
觀看次數為什麼會有上限
2014 年，PSY 的《江南 Style》在 YouTube 的觀看次數逼近 2,147,483,647。YouTube 公開表示：原本以為不會有影片的觀看次數超過「32 位元整數」的上限，所以已經把計數器改成 64 位元。
2,147,483,647 這個數字看起來很隨機，其實是 2³¹ - 1。為什麼是它？為什麼不是 2³² - 1？上一課學到 8 個位元可以表示 0～255，那 -5 這種負數要怎麼存？
這一課要回答：
- 電腦怎麼用位元表示負數？
- 為什麼 127 再加 1，在 8 位元的世界裡會變成 -128？
- 怎麼判斷一個加法的結果「已經錯了」？
無號整數
只表示 0 與正數的整數叫無號整數（unsigned integer）。n 個位元有 2ⁿ 種組合，從 0 開始用，範圍是 0 到 2ⁿ - 1：
| 位元數 | 無號範圍 |
|---|---|
| 8 | 0～255 |
| 16 | 0～65,535 |
| 32 | 0～4,294,967,295 |
負數怎麼存：二補數
直覺的做法是拿最高位當正負號（0 是正、1 是負），其餘 7 位表示大小，這叫符號與大小（sign-magnitude）表示法。它有兩個麻煩：
- 0 有兩種寫法：0000 0000 是 +0，1000 0000 是 -0
- 加法要先看正負號再決定做加法還是減法，電路比較複雜
現代電腦幾乎都用二補數（two's complement）。規則只有一條：最高位的權重是負的。8 位元時，各位的權重是：
位元 b7 b6 b5 b4 b3 b2 b1 b0
權重 -128 64 32 16 8 4 2 1
例如 1111 1011 = -128 + 64 + 32 + 16 + 8 + 2 + 1 = -5。
| 位元 | 無號解讀 | 二補數解讀 |
|---|---|---|
| 0111 1111 | 127 | 127（最大的正數） |
| 0000 0001 | 1 | 1 |
| 0000 0000 | 0 | 0 |
| 1111 1111 | 255 | -1 |
| 1111 1110 | 254 | -2 |
| 1000 0001 | 129 | -127 |
| 1000 0000 | 128 | -128（最小的負數） |
觀察這張表：
- 最高位是 1 就是負數，所以最高位也叫符號位元（sign bit）
- 正數的寫法和無號整數完全一樣
- 0 只有一種寫法
- 範圍是 -128 到 127：負數比正數多一個，因為 0 佔掉了「正的那一半」的一個位置。n 位元的範圍是 -2ⁿ⁻¹ 到 2ⁿ⁻¹ - 1
位元本身不帶「有沒有正負號」的資訊。同一組 1111 1111，當成無號是 255，當成二補數是 -1；怎麼解讀，是程式（變數的型別）決定的。
同一組位元，兩種讀法
兩種解讀用同一套方法：是 1 的位就加上它的權重。唯一的差別在第一格：無號的權重是 128，二補數是 -128。看兩個總和在第一格就分道揚鑣，之後每一格加的都一樣。
取負數：每一位反轉，再加 1
要求一個數的負數，二補數有個固定的步驟：每一位反轉（0 變 1、1 變 0），再加 1。
4 = 0000 0100
反轉 = 1111 1011
加 1 = 1111 1100 = -128 + 64 + 32 + 16 + 8 + 4 = -4
為什麼可行？一個數和它的反轉相加，每一位都是 1：0000 0100 + 1111 1011 = 1111 1111，也就是 -1。所以「反轉」等於「-x - 1」，再加 1 就是 -x。
反過來也一樣：-4 反轉再加 1，就回到 4。
取負數的過程：4 變成 -4
先看「反轉」那一列一格一格長出來；接著從最右邊加 1。最右邊兩位都是 1，1 + 1 = 2，留下 0、往左進位；進位一路傳到遇見 0 的那一位才停。
為什麼電腦選二補數
二補數最大的好處是：加法電路不必管正負號。
- 正數加負數、負數加負數，都直接用同一個「逐位相加」的電路，算出來就是對的（只要不超出範圍）
- 減法 a - b 可以變成 a + (-b)，而 -b 就是 b 反轉加 1；所以 CPU 只需要加法器和反轉電路，就能做加減法
- 0 只有一種寫法，比較兩個數是否相等也簡單
第 09 課會用邏輯閘做出真正的加法器，那時就會看到這套電路怎麼同時處理正數與負數。
溢位：結果超出能表示的範圍
位元數固定，能表示的範圍就固定。計算結果超出範圍，存下來的值就不對了，這叫溢位（overflow）。很像汽車的里程表：六位數的里程表跑到 999999 再多一公里，就變回 000000。
無號溢位：最高位相加後還有進位，這個進位沒有地方放，就被丟掉了。
1111 1111 (255)
+ 0000 0001 (1)
───────────
1 0000 0000 第 9 位的 1 被丟掉，只剩 0000 0000 = 0
有號溢位：結果超出 -128～127。判斷方法很簡單：
| 情況 | 會不會溢位 |
|---|---|
| 正數 + 負數 | 不會（結果一定介於兩者之間） |
| 正數 + 正數 | 結果變成負數，就是溢位。例如 127 + 1 = -128 |
| 負數 + 負數 | 結果變成正數（或 0），就是溢位。例如 -100 + -50 = 106 |
CPU 做完加法會同時設定兩個旗標：進位旗標（無號溢位）與溢位旗標（有號溢位）。CPU 不知道你把位元當成有號還是無號，所以兩個都算好，由程式決定要看哪一個。
模擬 8 位元的加法
Python 的整數會自動變大，不會溢位；這裡用 % 256 只留下最低 8 個位元，模擬 8 位元的電腦。raw 是那 8 個位元當成無號的值，大於等於 128 表示最高位是 1，就減 256 變成負數。看四個加法裡哪幾個的答案錯了。
常見的整數大小與真實世界的溢位
程式語言裡的整數型別通常有固定的位元數：
| 位元數 | 二補數有號範圍 | 無號範圍 |
|---|---|---|
| 8 | -128～127 | 0～255 |
| 16 | -32,768～32,767 | 0～65,535 |
| 32 | -2,147,483,648～2,147,483,647 | 0～4,294,967,295 |
| 64 | 約 ±9.22 × 10¹⁸ | 0～約 1.84 × 10¹⁹ |
開頭的 YouTube 計數器用的是 32 位元有號整數，上限正是 2³¹ - 1 = 2,147,483,647。
溢位不只是數字顯示錯誤。1996 年，歐洲太空總署的亞利安 5 號（Ariane 5）火箭首次發射，升空後不到一分鐘就偏離航道並自毀。調查報告指出，導航軟體把一個 64 位元浮點數轉成 16 位元有號整數時，數值太大放不下（16 位元最大只到 32,767），引發了一連串錯誤。這段程式沿用自前一代火箭，在舊火箭上這個數值從來不會那麼大。
所以寫程式時要先想：這個數最大可能到多少？選的型別裝得下嗎？
- Python 的整數會依需要自動加大，不會溢位（代價是比固定大小的整數慢一些）
- C、C++、Java、資料庫欄位的整數是固定大小，超出範圍時有的會悄悄繞回、有的會報錯，依語言而定
想一想：二補數
8 位元二補數 1111 1110 代表多少？
8 位元二補數能表示的範圍是？
-6 的 8 位元二補數是哪一個？
想一想：溢位
下面的程式模擬 8 位元有號整數的加法，會印出什麼？
raw = (100 + 50) % 256
if raw >= 128:
raw = raw - 256
print(raw)
8 位元有號整數相加，哪一種情況一定不會溢位？
位元 1111 1111 當成無號整數與二補數有號整數，分別是多少？
重點整理
- n 位元無號整數的範圍是 0～2ⁿ - 1；8 位元是 0～255。
- 二補數：最高位的權重是負的（8 位元時是 -128）；最高位是 1 就是負數，0 只有一種寫法。n 位元範圍是 -2ⁿ⁻¹～2ⁿ⁻¹ - 1，8 位元是 -128～127。
- 取負數＝每一位反轉，再加 1。二補數讓加減法共用同一套加法電路。
- 位元本身不帶正負號資訊；同一組 1111 1111，無號是 255、二補數是 -1。
- 溢位是結果超出範圍：無號看最高位有沒有進位出去；有號看「兩正得負、兩負得正」，正數加負數不會溢位。
- 32 位元有號整數的上限是 2,147,483,647；選型別前要先想資料最大可能到多少。
下一課：整數處理完了，那 3.14、0.1 這種有小數的數呢？為什麼在很多程式語言裡 0.1 + 0.2 不等於 0.3？第 05 課看浮點數。