CS:APP Ch2 Presentation and Maipulating Information

• 此篇筆記所描述的二補數 (two's-complement) 指的是一種用二進位來表示有號數的方法。
• 此篇筆記所描述的章節編號是根據 CS:APP 第3版。

為什麼需要學習 actual number representation ?

許多程式的安全漏洞就來自於計算機算術運算的微妙細節所引發的，為了讓編寫的程式可以在全部數值範圍內正確工作，而且可以支援跨機器、作業系統和編譯器組合，通過學習 actual number representation ，能夠了解

1. 在計算機上如何表示數字
2. 不同類型的數字的範圍
3. 算術運算在不同類型數字的特性

2.1 Information Storage

2.1.2 Machine word size

每台電腦都有自己的 "word size" ，用來明定指標的標準大小 (nominal size)。

• 以目前主流的 64-bit 電腦，一個指標的大小就是 64-bit (8 bytes) 。

Word size 也決定重要的系統參數 virtual address space 的大小。

• 對於一個 word size 為 w bit 的機器來說，指標所能代表的範圍就是
  $2^w$ 個 bytes ，也就是說，一個 32-bit machine ，他的 virtual address space 就被限制在 4 GB 內 ( 0 ~
  $2^{32}$ bytes)。

系統提供 private address space 給每一個 "process" （ process 就是運行中的 program ），而一個 program 只會在自己的 memory space 上定址。

當我們安裝程式，該程式可能是 32-bit 或是 64-bit ，但大多數的 64-bit machine 都可以運行 32-bit program ，而 64-bit program 只能在 64-bit machine 上執行。 因此，所謂的 32-bit program 或是 64-bit program 指的是 program 如何被編譯，而不是其運行的機器類型。

Word size 除了影響指標大小， long 型態 data 在 32-bit / 64-bit 的機器上大小也不同，為了解決依賴典型資料大小或是因為不同編譯器所帶來的非預期行為， ISO C99 引進新的 data type ，不會隨著編譯器和機器而變化，其中就有 int32_t 和 int64_t ，分別代表 32 bits 和 64 bitss ，這樣精準控制的資料大小有助於減少可移植性的困擾。

2.1.3 Byte Ordering

2.1.7 Bit manipulation in C

以 NOT, AND 和 OR 來完成 XOR 。

x ^ y = (x & ~y) | (~x & y) 

練習題 2.12

對於下面要求的值，寫出變數 x = 0x87654321 的 C 語言表達式。程式碼對任何 bit size >= 8 都要能有效工作。

1. x 的 less significant byte 保留原始值，其他位置均為 0 。
2. 除了 x 的 less significant byte 外，其他全取補數，而 LSB 保持不變。

x ^ ~0xff

3. x 的 less significant byte 設為全 1 ，其他位置不變。

2.1.9 Shift Operations

• 左移: x << y
  • x 左移 y 位元，左移出的位元會被丟棄，右側會補上 0 。
• 右移: x >> y
  • x 右移 y 位元，右移出的位元會被丟棄。
  • 右移又分兩種操作
    • 邏輯位移 (Logical shift) : 左側全補上 0
    • 算術位移 (Arithmetic shift) : 左側空缺處全補上號數 (sign bit)

C 語言並沒有明確定義有號數在右移時，應該採取 logical shift 還是 arithmetic shift 。 然而實際上幾乎所有 compiler / machine 都在有號數右移上使用 arithmetic shift ，對於無號數來說，都會採用 logical shift 。

• undefined behavior
  • x >> y 的操作中， y < 0 或 y >= x bit size

2.2 Integer Representation

Unsigned and Signed

Signed Integer (有號整數) 使用 Most Significant Bit (最高有效位數) 作為 Sign Bit。
0 代表正數， 1 代表負數。

有號整數的二補數表示法

在 C 語言中並沒有要求要用二補數形式 ( two'-complement ) 來表示有號整數，不過幾乎所有的機器都是這麼做的，為了程式碼有良好的移植性，採取二補數形式是最好的選擇。

二補數會將 most significant bit 解讀為負數，如同下方投影片，其餘位數如同一般無號整數表示法。

其中 most significant bit 也稱為 signed bit，因為該 bit 一旦設為 1 ，則結果必為負數，若該 bit 設為 0 ，則結果必為正數。

如何快速找出有號整數對應的二補數表示形式 ?

1. 非負數的有號整數與其無號整數的表示型態一樣。
2. 負數的二補數型態比較麻煩，如果每次都透過計算 most significant bit 來湊出二補數相當累。
   有一個簡單方法是，負數的二補數等於其對應之正數的一補數再加 1。

ex: 如何找出 -4 的二補數表示型態 ？

-4 對應之正數為 +4 ( 1 0 0 )

-> +4 的一補數（bit 0, 1 互換） 為 ( 0 1 1 )

-> 一補數再加一為 1 0 0 ，即為 -4 的二補數表示型態

延伸閱讀：你所不知道的 C 語言：數值系統篇

下圖投影片為各種大小的整數所能表示的取值範圍:

• | TMin | = TMax + 1
  • 有號數的最小值的絕對值等於有號數最大值加 1 ，也就是說 TMin 並沒有對應的正數。
  • 會發生這樣的狀況，由於有一半的 bit model （ most significant bit 為 1）被用來表示負數，而另外一半用來表示非負數，由於 0 屬於非負數，導致能表示的正整數比負數少1個。
  • TMin 的 T 代表 Two's complement

2.2.4 Mapping between Signed (Two's Complement) & Unsigned

不論將有號整數強制轉型為無號整數，或是將無號整數轉為有號整數，以位元表示的結果都不會變（ bit pattern is maintained ），只是以不同規則重新解讀 ( Interpreted ) 而已。

2.2.5 Signed & Unsigned in C

• Constants
  • 預設一般變數都會被當作是 signed integer
  • 只有加上 'U' 或 'u' 為後綴的變數才會被當成 unsigned integer

:Question: 當執行一個運算時，一個運算元為無號整數，另外一個為有號整數，結果會如何呢？

C 會 implicitly 將有號整數轉換為無號，並假設兩數都是非負的，再來執行運算。

• 運算包含 comparison operations <, >, ==, <=, >=
• 詳情可參考 integer promotion

2.2.6 Sign Extension

在不同大小的整數之間轉換，同時又要保持數值不變，其中值得探討的是從較小的類型轉換到一個較大的類型。

一個無號整數轉換為一個較大的 data type 時，只要在開頭的位置全補上 0 即可，這樣運算稱做 Zero Extension 。

一個有號整數轉換為較大的 data type 時，在開頭處全部補上 most significant bit ，這樣運算稱為 Sign Extension 。

原理

short sx = -12345;
unsigned short usx = sx;    // 53191
int x = sx;                 // -12345
unsigned int ux = usx            // 53191

以上4個例子可以用來檢驗 Zero Extension 和 Sign Extension ，若是牽涉到不同大小的 data type ，首先先做擴展，再做 reinterpret 。

下面的例子更能體會，事實上，這樣的規則是 C 語言標準所訂定的。

short sx = -12345;
unsigned int uy = sx;        // 4 294 954 951

short 跟 unsigned 的大小不一樣， data type 也不一樣，首先要做的是改變資料大小，將 short 變為 int , 再做 unsigned/signed 之間的 reinterpret 。 也就是說， (unsigned) uy = (unsigned int) (int) sx ，而不是等於 (unsigned int) (unsigned short) sx 。

2.2.7 Truncation

將一個較多位數的數值截斷為一個較少位數的數值，截斷一個有號數，很容易改變他的值並造成 overflow 。
無號數的截斷則很容易推導出結果。

儘量不要使用 unsigned

有號數和無號數的隱式轉換經常導致程序錯誤，避免錯誤的方法之一就是避免使用無號數，只有在某些狀況下適合使用，可見下方投影片。

只要掌握 sign extension 跟 Keep Bit representations and reinterpret (unsigned/signed 之間轉換的原則) ，就可以掌握 overflow 的發生脈絡。

延伸閱讀：

1. C语言的整型溢出问题
2. Secure Coding Guide - Apple Developer

2.3 Integer Arithmetic

2.3.1 Unsigned Addition

無號整數的加法有可能會發生 overflow ，多出來的 carry bit 會直接被捨棄。
在 C 程式執行時，並不會因為 overflow 而導致任何意外，但我們仍舊必須了解是否發生 overflow 。

:Question: 如何檢測無號整數加法發生 overflow ？

對於兩個無號整數 x 跟 y ，假設 w = x + y ，如果沒有 overflow ，則 w 一定大於 x 或 w 一定大於 y 。

練習題 2.27

:Question: 寫出一個函式，判斷無號數型態參數 x 和 y 相加不會發生溢出的話，這個函數就回傳 1

int uadd_ok (unsigned int x, unigned int y)
{
    unsigned int sum = x+y;
    return sum >= x;
}

2.3.2 Two's Complement Addition

二補數的加法的結果可能太大（ positive overflow ） 或是太小（ negative overflow ）。

兩個均為 w bits 的整數，相加之後的結果可能為 w+1 bits ，因此 most significant bit 會被截斷丟掉，剩下的 bits 將作為加法的結果並以二補數的方式來解讀。

:Question: 如何檢測有號整數加法發生 overflow ？

• 如果 x 和 y 都在有號整數合理範圍內，假設 s = x+y ，若且為若 x>0, y>0 ，但 s <= 0 時，代表計算 w 時發生 positive overflow 。
• 如果 x 和 y 都在有號整數合理範圍內，假設 s = x+y ，若且為若 x<0, y<0 ，但 s >= 0 時，代表計算 w 時發生 negative overflow 。

其實不管是無號數還是二補數，他們執行加法後的行為都是一致的，多出來的 bit 被截斷，再重新 interpret。 事實上，大多數計算機均使用相同的 machine code 執行無號數或有號數的加法。

練習題 2.30

:Question: 寫出一個函式，判斷有號數型態參數 x 和 y 相加不會發生溢出的話，這個函數就回傳 1

int tadd_ok (int x, int y)
{
    int sum = x+y;
    int post_overflow = x>0 && y>0 && sum<=0;
    int neg_overflow = x<0 && y<0 && sum>=0;
    return !post_overflow && !neg_overflow;
}

[作法 2]
透過看 sign bit 做 XOR 後是否等於 0 來判斷兩個數是否都為正或都為負。
接著檢查相加後的值的 sign bit 是否跟任一數的 sign bit 不同即可判斷是否發生 overflow。

int tadd_ok (int x, int y)
{
    int sum = x+y;
    if ((x>>31)^(y>>31) == 0 && (sum>>31) != (x>>31))
        return 0
    else
        return 1;
}

[作法 3]
如果相加後發生 overflow ，那再減掉 x 後，應該不會等於 y ，用這個方式來檢查是否發生 overflow 。

int tadd_ok(int x, int y)
{
    int sum = x+y;
    return (sum-x == y) && (sum-y == x);
}

但其實這個作法是錯的，不管是無號數或有號數加法，都符合 modular addition ， modular addition 形成一種數學結構稱為阿貝爾群，這樣特性使得不管是否發生 overflow ， (x+y)-y 總是得到 x 。

練習題 2.32

:Question: 寫另外一個函數，函數的參數是 x 和 y ，如果計算 x-y 不會產生 overflow ，函數就回傳 1 。假設重複利用練習題 2.30 的程式碼來寫並如下：

int tsub_ok (int x, int y)
{
    return tadd_ok(x, -y);
}

請問這個函數會產生什麼錯誤？

當 y 等於 Tmin （二補數最小值）這個函數會判斷錯誤。 關鍵在於：

對 Tmin 取其對應之負數，再以二補數重新 interpret 後，依舊等於 Tmin ，以 8-bit 長的二補數為例， Tmin 等於 -128 ，求其對應的 negation ，仍然會得到 -128 。（可見此文 2.3.3 節 Two's complement Negation 說明）

當 y 等於 Tmin ， -y 的二補數表示仍然一樣 ，但照理說， -y 應該會變成一個正數，卻因為二補數表示的關係， -y 現在仍然等於 Tmin ，此時若 x 為負數， tadd_ok(x, -y) 就會判斷為 negative overflow 。

但事實上，拋開二補數表示法， 當 x 為正數， tadd_ok(x, -y) 才應該判斷為 overflow 。 這個例子告訴我們，在函數的測試過程中， Tmin 應該作為一種測試狀況。

2.3.3 Two's complement Negation

對於每個二補數求其 negation ，作法為對每一個位數求其 1補數，再對結果加 1 。

• 值得一提的是，對於 Tmin (以 4 bit 來說，二補數最小值為 -8 ) 來說，其 negation 等於原始數字的二補數表示法。 也就是說，當 x = Tmin 時， -x 也等於 Tmin 。

x	~x	(~x)+1
[0101] 5	[1010] -6	[1011] -5
[1000] -8	[0111] 7	[1000] -8

2.3.4 Unsigned & Two's complement Multiplication

對於計算兩個 w-bit numbers x, y ，其乘積絕對會大於 w bit ，最多可到 2w bits ，而其乘積最終會被截斷為 w-bit 的結果。

• 對於 unsinged integer x, y
  • x*y = (x*y) mod
    $2^w$
• 對於 signed integer x, y
  • x*y = U2T ((x*y) mod
    $2^w$)
  • U2T 代表 unsgined to two's complement

2.3.6 Power-of-2 Multiply with Shift

以往在大多數的機器上，整數乘法的指令相當慢，需要多個 clock ticks 來完成，但是加法、減法、 shift 和 bit manipulation 只需要一個 clock tick 即可完成，因此， compiler 會選擇透過 shift 和加法運算的組合來代替乘以常數的動作。

* u << 3  ==  u * 8
* (u << 5) - (u << 3) == u * 24   // 透過 2 個 shift 和 1 個減法代替乘法

請相信你的 Compiler ，每個運算所耗費的 clock tick 和機器高度相關， compiler 會幫你優化。

2.3.7 Power-of-2 Divide with Shift

整數除法指令也是個耗時的動作， Compiler 更傾向於使用 right shift 來代替。 在 Shift Operations 章節有提到，無號數使用的是 logical shift ，而有號數使用的是 arithmetic shift 。

但對於負數執行 right shift 來說，會產生不適當的四捨五入行為：

• -12345 /
  $2^4$ = -49
  但是 right shift 會變為 -48

因此需要加入一個偏移量（ biasing ），來修正這個不合適的捨入。

以 C 語言來總結 right shift 如何搭配 biasing 的表達式：

(x<0 ? x+(1<<k)-1 : x) >> k

練習題 2.44

A. 當 x 為 Tmin 時，此判斷式為 0
B. 正確
C. x 為 0xFFFF ，而 (xx) 為 0xFFFE0001
D. 正確
E. 當 x 為 Tmin ，-x 也會等於 Tmin
F. 正確。 無號數或是有號數執行加法的行為都一樣，都是進行位級的運算。
G. 正確。 ~y 等於對 y 取一補數，而 -y 等於 y 取一補數再加 1 ，因此 ~y 可以視為 (-y-1) 。 此運算式等於 x * (-y-1) + xy ， 結果恆等於 -x 。

2.4 Floating Point 浮點數

2.4.1 二進位小數

理解浮點數的第一步是考慮含有小數的二進位數字。

二進位小數表示法有兩個限制：

1. 只能用來表示 (x *
   $2^y$) 的數字，其他的值只能夠被近似地表示。
   • 像 1/5 在十進位可以表示為 0.2 ，但在二進位這類數字就無法好好表示。
2. 表示的範圍會被限制在 w bits ，若數字過大或過小將無法表示。

2.4.2 IEEE Floating Point

IEEE Standard 754 訂定浮點運算的標準，大大提升不同機器上的移植性。
以 V =

$(-1{)}^s$ x M x

$2^E$ 來表達一個數，以下投影片解釋各個變數。

根據 exp 區段的值可以分為三種狀況:

Normalized Values

當 exp 不全為 0 或不全為 1 時候，屬於這類狀況。

• Exponent 等於 exp - Bias (偏移值)。
• Bias 等於
  $2^{k-1}-1$，在單精度時為 127 ，在雙精度時為 1023 。
• Significand (有效位數) 由 frac 和 1 所構成，frac 部份須以二進位來解讀，由於整個 significand 第一位至少為 1 ，因此在 frac 中並不會將他表示出來，這樣的表示法能夠輕鬆的獲得一個額外的 bit 來表達精度。
  

Denormalized Values

exp 均為 0 ，屬於這類狀況。

• Exponent 為 1 - Bias (這個用途可以補償 denormalized value 的 significand 沒有隱含的 leading 1 ，可參閱 CS:APP 3e 中文版 p80 )。
• Significand 等於 frac ，並不包含隱含的 leading 1 。

Denormalized Value 有兩種用途

1. 用來表示 value = 0 的方法。 由於 Normalized value 的 significand 至少 >= 1 ， Normalized value 是無法用來表示 0 的。
2. 用來表示非常接近於 0.0 的數。

Special Value

exp 全為 1 ，屬於這類狀況。 可以用來表示 INF (infinity) 或 NaN (Not a Number) 。

• 當兩個非常大的數相乘或是除以 0 的時候，就可以用 INF 來表示 overflow 的結果。
• 當運算結果不能是實數或是無窮，例如
  $\sqrt{-1}$ 或是
  $\mathrm{\infty }$-
  $\mathrm{\infty }$ 就可以用 NaN 來表示。
  

練習題 2.49

這題幫助你思考什麼數不能用浮點數正確表示。
A.
1 後面跟著 n 個 0 ，再緊接著 1 個 1 ，得到的值為

$2^{n+1}+1$ 。 這個值總共需要 n+1 位 fraction 大小才能正確描述這個值。

B.

$2^{23+1}+1$

2.4.4 Rounding

因為 IEEE 754 的表示方法限制浮點數的範圍和精度，所以浮點數只能近似地表達實數運算後的結果。 基本的想法是先計算正確的結果，再根據想採用的 rounding mode 調整。

IEEE 定義四種不同的 rounding modes ，預設採取 round-to-even 也稱為 round-to-nearest 。

• round-to-nearest 會先向最接近的數 rounding ，如果該值是兩個可能結果的中間值，朝著最低有效數字是偶數的方向來 rounding （在二進位小數上，通常認定值 1 是奇數，值 0 是偶數）。
  

練習題 2.50

• 最低有效位為二進位小數點右邊第1位

A. 10.010 為 10.0 和 10.1 的中間值，因此傾向往最低有效位為偶數 (即 0) 的方向 rounding ，即為 10.0 。

B. 10.011 向最接近的數 rounding ，因此為 10.1 。

C. 10.110 為 10.1 和 11.0 的中間值，因此傾向往最低有效位為偶數 (即 0) 的方向 rounding ，即為 11.0 。

D. 11.001 向最接近的數 rounding ，因此為 11.0 。

練習題 2.52

好的練習題，可以同時練習浮點數表示法和 rounding 。

2.4.5 FP operations

• 浮點數運算缺乏結合律和分配律是嚴重的問題。

2.4.6 C 語言的浮點數

當在 int, float 和 double 之間進行 casting ，程式會依據下列規則改變數值和 bit rpresentation

• 從 int 轉為 float ，不會發生 overflow ，但可能會 rounding
• 從 int 或 float 轉為 double ，因為後者相對前者有更多的有效位數可以利用，所以能夠保留精確的數值。
• 從 double 轉為 float ，因為可以使用的有效位數變少，可能會發生 overflow 。 由於後者精度，可能會發生 rounding
• 從 float 或 double 轉換成 int ，數值會向 0 做 rounding 。
  C 語言標準並沒有清楚定義這樣的 case 的結果，對於 Intel-compatiable 的處理器來說，其定義 [100..000] ( Tmin for word size w ) 為 integer indefinite value ，任何從 fixed-point value 轉為 integer 的結果若是無法找到合理的近似值，就會給予 integer indefinite value ， 例如 expression (int)+1e10 會得到 Tmin ，從一個正值 overflow 為一個負值。

練習題 2.54

A. True

​​​​double type 比 int 具有更大的精度跟範圍

B. False

float 不能準確表達的最小正整數為

$2^{24}+1$ 。 一旦 x 大於

$2^{24}+1$ ，此等式將不成立。（可參考練習題 2.49 ）

C. True

​​​​當 d 為 1e40 ，會發生 overflow 變為 +$\infty$

E. True

​​​​浮點數要取 negation ，只要更動 sign bit 就好

F. True

​​​​執行運算之前，分子分母都會被轉為 double 

G. True

永遠為正數，但可能會 overflow 到 +

$\mathrm{\infty }$

H. False

​​​​當 f 為 1.0e20 而 d 是 1.0 時， expression (f+d) 會因為 rounding 變為 1.0e20 ，因此等號左邊將變為 0.0

延伸閱讀：

1. 浮點數運算和定點數操作

思考題：

#include <stdio.h>

int main(void)
{
    float a = 1000000.0f;
    for (int i=0; i<1000000; i++)
    {
        a += 0.01f;
        printf ("%f\n", a);
    }

    return 0;
}

print 出來的結果會是什麼呢？

tags: CS:APP

參考資料

1. CS:APP 第 2 章重點提示和練習
2. 15-213/18-213/14-513/15-513/18-613: Intro to Computer Systems, Fall 2020 課程網頁
3. CS:APP 第 2 章重點提示和練習
4. 你所不知道的 C 語言: 浮點數運算
5. 浮點數運算和定點數操作

上課影片