資訊的表示與處理練習題 (Practice - Information Representation)

Key Patterns (click to expand)

關鍵字	答案
$2^{n}$ 的 hex 表示	$n = i + 4 j$ → 前導 digit $2^{i}$ (1/2/4/8)後接 $j$ 個 0
little endian	least significant byte 放在最低位址
`!x` vs `~x`	`!` 回傳 0/1(邏輯);`~` 逐位反相(位元)
signed 的 `>>`	C 未定義;實務上幾乎都是 arithmetic shift(補 sign bit)
UMax / TMin / TMax	$2^{w} - 1$ / $- 2^{w - 1}$ / $2^{w - 1} - 1$ ; $U M a x = 2 T M a x + 1$
signed → 大型別擴展	sign extension(複製 sign bit);unsigned 用 zero extension
signed 與 unsigned 混合運算	signed 隱式轉 unsigned;`-1 < 0U` 為 false
signed 加法溢位	正溢位:`x>0 && y>0 && s<=0`;負溢位:`x<0 && y<0 && s>=0`
`-TMin`	仍是 TMin(自己的加法反元素);一般 `-x == ~x + 1`
乘以常數 K	連續 1 的 run 用 Form B:`(x<<(n+1)) - (x<<m)`
IEEE 754 分類	exp 全 0 → denormalized;全 1 → ±∞ / NaN;其餘 normalized
Bias / E / M	$B i a s = 2^{k - 1} - 1$ ;norm: $E = e - B i a s$ , $M = 1 + f$ ;denorm: $E = 1 - B i a s$ , $M = f$
浮點結合律	不成立:大數相加時小數被捨入吃掉

Question 1 - 2 的冪轉十六進位 [recall]

不經過完整二進位展開,請直接寫出 $2^{11}$ 與 $2^{19}$ 的十六進位表示,並說明所用的規則。

查看答案

$2^{11}$ = 0x800; $2^{19}$ = 0x80000。
規則:令 $n = i + 4 j$ ( $0 \leq i \leq 3$ ),則 $2^{n}$ 的 hex 表示為前導數字 $2^{i}$ (即 1、2、4、8)後接 $j$ 個 0。
$11 = 3 + 4 \cdot 2$ → 前導 $2^{3} = 8$ 接 2 個 0; $19 = 3 + 4 \cdot 4$ → 8 接 4 個 0。

Question 2 - Little Endian 位元組排列 [recall]

在 little-endian 機器上宣告 int x = 0x01234567;,且 &x = 0x100。
請寫出位址 0x100 至 0x103 各儲存的 byte 值。

查看答案

0x100: 67、0x101: 45、0x102: 23、0x103: 01。
Little endian 把 least significant byte 放在最低位址(低位在前);Intel 相容機器與 Android/iOS 上的 ARM 皆採此順序。
Big endian 則相反:01 23 45 67。

Question 3 - 邏輯運算 vs 位元運算 [recall]

請分別求出 !0x41、~0x41、0x69 && 0x55、0x69 & 0x55 的值(以 1 byte 表示),並說明兩類運算子的本質差異。

查看答案

!0x41 = 0x00;~0x41 = 0xBE;0x69 && 0x55 = 0x01;0x69 & 0x55 = 0x41。
邏輯運算(&& || !)把整個值視為 true(非 0)/false(0),只回傳 0x00 或 0x01,且有 short-circuit 短路求值;
位元運算(& | ~ ^)則對 bit vector 逐位運算,回傳任意 bit pattern。

Question 4 - 兩種右移 [recall]

8-bit 值 x = [10010101]。請寫出 x >> 4 在 logical shift 與 arithmetic shift 下的結果,並說明 C 標準對 signed 與 unsigned 資料的右移各如何規定。

查看答案

Logical:[00001001](左端補 0);Arithmetic:[11111001](左端補 sign bit 1)。
unsigned 資料必須用 logical shift;signed 資料的右移形式 C 標準未定義,但實務上幾乎所有 compiler/machine 組合採 arithmetic shift。
兩種右移分別對應 unsigned 與 signed 的「除以 2 的冪」需求。

Question 5 - 三大常數 [recall]

對 w-bit 的 two's-complement 與 unsigned 表示,請寫出 UMax、TMin、TMax 的公式與彼此的關係式,並說明範圍為何不對稱。

查看答案

$U M a x_{w} = 2^{w} - 1$ 、 $T M i n_{w} = - 2^{w - 1}$ 、 $T M a x_{w} = 2^{w - 1} - 1$ ;關係: $U M a x = 2 T M a x + 1$ 、 $| T M i n | = | T M a x | + 1$ 。
不對稱原因:sign bit = 1 的一半 bit pattern 全是負數,而 sign bit = 0 的那一半還要包含 0,所以正數比負數少一個——TMin 沒有正的對應值。

Question 6 - 位元擴展規則 [recall]

short sx = -12345;(bit pattern 0xCFC7)與 unsigned short usx = 53191;(同為 0xCFC7)。
兩者分別轉成 int 與 unsigned 後,32-bit 的 bit pattern 各是什麼?各用哪種擴展?

查看答案

int x = sx → 0xFFFFCFC7(sign extension:前補 16 個 sign bit 複本);
unsigned ux = usx → 0x0000CFC7(zero extension:前補 16 個 0)。
擴展規則由「原型別」決定,兩者皆保值;sign extension 保值的關鍵是 $2^{w} - 2^{w - 1} = 2^{w - 1}$ ,新增負權重與舊 sign bit 轉正相抵。

Question 7 - Signed/Unsigned 混合比較 [recall]

在 32-bit 環境下,-1 < 0U 與 2147483647U > -2147483647-1 的結果各是什麼?為什麼?

查看答案

兩者皆為 0(false)。
C 規定:運算中一邊 signed、一邊 unsigned 時,signed 隱式轉為 unsigned 再運算。
-1 → $4294967295$ (UMax),故不小於 0U;-2147483647-1(TMin)→ $2^{31} = T M a x + 1$ ,反而比 TMax 大。

Question 8 - Signed 加法溢位偵測 [recall]

令 s = x + y(w-bit two's-complement)。請寫出偵測 positive overflow 與 negative overflow 的條件,並說明一正一負相加為何絕不溢位。

查看答案

Positive overflow ⟺ x > 0 && y > 0 && s <= 0;Negative overflow ⟺ x < 0 && y < 0 && s >= 0。
一正一負時,真實和必落在 $T M i n \leq x + y \leq T M a x$ 內(絕對值不會超過任一運算元),故必為 Normal 情況。
對照:unsigned 加法的溢位判斷是 s < x(等價 s < y)。

Question 9 - IEEE 754 分類與 Bias [recall]

依 exp 欄位(k bits)與 frac 欄位的內容,IEEE 754 的 bit pattern 分成哪幾類?各類的 E 與 M 如何計算?Bias 的公式是什麼?

查看答案

exp 非全 0 非全 1 → normalized: $E = e - B i a s$ 、 $M = 1 + f$ (implied leading 1);
exp 全 0 → denormalized: $E = 1 - B i a s$ (非 $- B i a s$ )、 $M = f$ ,表示 ±0.0 與 gradual underflow;
exp 全 1:frac = 0 → ±∞;frac ≠ 0 → NaN。
$B i a s = 2^{k - 1} - 1$ (single 127、double 1023)。

Question 10 - TMin 的取負 [recall]

對 two's-complement 值 x,-x 的位元算法是什麼?-TMin 等於多少?為什麼?

查看答案

-x == ~x + 1(逐位取反再加 1),對所有值成立。
-TMin == TMin: $T M i n + T M i n = - 2^{w}$ 發生 negative overflow,截斷(+ $2^{w}$ )後為 0,故 TMin 是自己的加法反元素。
這使 tsub_ok(x,y) 寫成 tadd_ok(x,-y) 在 y == TMin 時出錯。

Question 11 - 同一 Bit Pattern 的兩種解讀 [application]

8-bit 的 bit pattern 為 0xA7。請分別計算其 unsigned 解讀 $B 2 U_{8}$ 與 two's-complement 解讀 $B 2 T_{8}$ 的十進位值,並驗證兩者的關係。

查看答案

0xA7 = [10100111]。
$B 2 U_{8} = 128 + 32 + 4 + 2 + 1 = 167$ ; $B 2 T_{8} = - 128 + 32 + 4 + 2 + 1 = - 89$ (sign bit 權重為 $- 2^{7}$ )。
驗證:負數解讀 $+ 2^{w}$ = 無號解讀,即 $- 89 + 256 = 167$ ,符合 $T 2 U_{8} (x) = x + 2^{8}$ 。

Question 12 - 4-bit 加法溢位計算 [application]

以 4-bit two's-complement 計算 5 + 5 與 -8 + (-5) 的結果(截斷為 4 bits 後的值),並指出各屬於哪種溢位情況。

查看答案

5 + 5 = 10,超過 $T M a x_{4} = 7$ → positive overflow,結果 $10 - 16 = - 6$ ([1010])。
-8 + (-5) = -13,低於 $T M i n_{4} = - 8$ → negative overflow,結果 $- 13 + 16 = 3$ ([0011])。
公式: $x +_{w}^{t} y$ 為真實和依情況減或加 $2^{w}$ ;位元層級與 unsigned 加法完全相同。

Question 13 - 乘以常數的移位改寫 [application]

編譯器要把 x * 14 改寫成 shift 與 add/sub 的組合。

int mul14(int x) {
    return x * 14;
}

請分別寫出 Form A 與 Form B 的展開式,並指出哪個較划算。

查看答案

$14 = [1110]_{2} = 2^{3} + 2^{2} + 2^{1}$ 。
Form A:(x<<3) + (x<<2) + (x<<1)(3 shifts + 2 adds);
Form B:利用 $14 = 2^{4} - 2^{1}$ ,得 (x<<4) - (x<<1)(2 shifts + 1 sub),較划算。
兩種寫法即使溢位,結果仍與乘法逐位相同;run 長度 ≥ 2 時 Form B 較佳。

Question 14 - 8-bit 浮點解碼 [application]

某 8-bit 浮點格式:1 sign bit、k = 4 exp bits、n = 3 frac bits(Bias = 7)。
請解碼 bit pattern 0 0101 110:寫出 E、M 與十進位值 V。

查看答案

exp = [0101] = 5,非全 0 非全 1 → normalized。
$E = e - B i a s = 5 - 7 = - 2$ ; $f = 6 / 8$ , $M = 1 + f = 14 / 8$ 。
$V = (+ 1) \times \frac{14}{8} \times 2^{- 2} = \frac{14}{32} = \frac{7}{16} = 0.4375$ 。

Question 15 - 用減法驗證加法溢位? [analysis]

有人提出以下函式偵測 signed 加法溢位:

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

請分析此函式對哪些輸入回傳錯誤結果,並解釋根本原因。乘法溢位能否用類似手法(除法)驗證?

查看答案

此函式對「任何輸入」都回傳 1,完全無法偵測溢位。
根本原因:two's-complement 加法構成 abelian group,(x+y)-x 恆等於 y——溢位時多加或少掉的 $2^{w}$ 在減回時被完全抵銷。正確做法是檢查符號模式(見 Question 8)。
乘法則可以用除法驗證(!x || p/x == y):除法無截斷、結果唯一,溢位時 $p / x \neq y$ 。

Question 16 - Unsigned 迴圈邊界 Bug [analysis]

以下函式在 length = 0 時會發生嚴重錯誤:

float sum_elements(float a[], unsigned length) {
    float result = 0;
    for (int i = 0; i <= length - 1; i++)
        result += a[i];
    return result;
}

請分析錯誤發生的機制,說明為何編譯器不會警告,並給出修正方式。

查看答案

length 是 unsigned,length - 1 是無號運算:0 - 1 wrap 成 $U M a x = 2^{32} - 1$ ,迴圈條件 i <= UMax 幾乎永遠成立 → 大量越界讀取,造成記憶體錯誤。
隱式 signed/unsigned 轉換與無號 wrap-around 是 C 定義良好的行為(modular arithmetic),不是未定義行為,故編譯器不報錯——這正是此類 bug 難以察覺的原因。
修正:條件改為 i < length(或將 length 宣告為 signed)。同類陷阱:strlen(s) - strlen(t) > 0 因差值永為非負而失效,應直接寫 strlen(s) > strlen(t)。

Pattern Summary (click to expand)

題型	答題模式
binary ↔ hex / $2^{n}$ 轉換	4 bits 對 1 hex digit; $n = i + 4 j$ → 前導 $2^{i}$ 接 $j$ 個 0
endianness 排列	little endian 低位 byte 在低位址;disassembly 常數需反序重組
求 bit pattern 的值	$B 2 U = \sum x_{i} 2^{i}$ ; $B 2 T$ 最高位權重改 $- 2^{w - 1}$ ;兩解讀相差 $2^{w}$
cast / 混合運算	位元不變、解讀改變;signed 遇 unsigned 隱式轉 unsigned
擴展與截斷	signed 用 sign extension、unsigned 用 zero extension(皆保值);截斷 = mod $2^{k}$
溢位偵測	unsigned:`s < x`;signed:同號相加後符號反轉;加法不可用減法驗證、乘法可用除法
乘除以 2 的冪	乘 = 左移;unsigned 除 = logical 右移;signed 除需加 bias $2^{k} - 1$ 向零捨入
IEEE 754 解碼	先看 exp:全 0 denorm、全 1 特殊值、其餘 norm; $B i a s = 2^{k - 1} - 1$
浮點性質	可交換、不可結合、乘不分配於加;大小數相加小數可能被捨入吃掉
unsigned bug 分析	找出 0−1 wrap、負數轉 size_t、乘積 mod $2^{w}$ 變小等 modular arithmetic 陷阱

Related Concepts

Question 1 - 2 的冪轉十六進位 [recall]

Question 2 - Little Endian 位元組排列 [recall]

Question 3 - 邏輯運算 vs 位元運算 [recall]

Question 4 - 兩種右移 [recall]

Question 5 - 三大常數 [recall]

Question 6 - 位元擴展規則 [recall]

Question 7 - Signed/Unsigned 混合比較 [recall]

Question 8 - Signed 加法溢位偵測 [recall]

Question 9 - IEEE 754 分類與 Bias [recall]

Question 10 - TMin 的取負 [recall]

Question 11 - 同一 Bit Pattern 的兩種解讀 [application]

Question 12 - 4-bit 加法溢位計算 [application]

Question 13 - 乘以常數的移位改寫 [application]

Question 14 - 8-bit 浮點解碼 [application]

Question 15 - 用減法驗證加法溢位? [analysis]

Question 16 - Unsigned 迴圈邊界 Bug [analysis]