整數表示 (Integer Representations)

#csapp #data-representation #twos-complement #concept

Overview Table

主題	核心觀念	關鍵公式 / 事實	書頁
整數資料型別 (Integral Data Types)	C 的整數型別範圍非對稱;`long` 隨 32/64-bit 程式而異	負數範圍比正數多 1	p.96-98
無號編碼 (Unsigned Encoding)	每個 bit 權重 $2^{i}$ ,B2U 是雙射 (bijection)	$B 2 U_{w} (\vec{x}) = \sum_{i = 0}^{w - 1} x_{i} 2^{i}$	p.98-100
二補數編碼 (Two's-Complement)	最高位權重為 $- 2^{w - 1}$ (sign bit),B2T 是雙射	$B 2 T_{w} (\vec{x}) = - x_{w - 1} 2^{w - 1} + \sum_{i = 0}^{w - 2} x_{i} 2^{i}$	p.100-103
重要常數	UMax、TMin、TMax 之間的固定關係	$U M a x = 2 T M a x + 1$ ; $\| T M i n \| = \| T M a x \| + 1$	p.102
有號⇄無號轉換	cast 時位元樣式不變,數值解讀改變	$T 2 U_{w} (x) = x + x_{w - 1} 2^{w}$ ; $U 2 T_{w} (u) = u - u_{w - 1} 2^{w}$	p.106-110
C 的 signed/unsigned	混合運算時 signed 隱式轉為 unsigned	`-1 < 0U` 為假(false)	p.110-112
位元擴展 (Expanding)	無號:zero extension;二補數:sign extension	兩者皆保值	p.112-116
截斷 (Truncating)	丟棄高位 → 相當於 mod $2^{k}$ ,是一種 overflow	$x^{'} = x mod 2^{k}$ (unsigned)	p.117-118
使用建議	隱式轉換是 bug 溫床;多數語言不提供 unsigned	Java 只有 signed + `>>>`	p.119-120

記號約定 (p.95-96, Figure 2.8)

下標 $w$ 表位元寬度。B2U/B2T = binary→unsigned / two's complement;U2B/T2B 為其反函數;T2U/U2T 為兩種數值解讀間的轉換;UMax/TMin/TMax 為三個特殊常數。

2.2.1 整數資料型別 (Integral Data Types) (p.96-98)

C 提供 char、short、int、long 等大小指定,搭配 unsigned(全為非負)或預設有號 (signed)。實際位元組數依 32-bit 或 64-bit 程式而定,其中唯一機器相依的是 long:32-bit 程式用 4 bytes,64-bit 程式用 8 bytes。

範圍不對稱:負數範圍比正數多 1(如 int:−2,147,483,648 ~ 2,147,483,647),原因見二補數編碼。
C 標準只保證最小範圍(Figure 2.11):標準只要求 int 至少 ±32,767(可用 2 bytes 實作,16-bit 機器遺緒)、long 至少 ±2,147,483,647;且保證範圍是對稱的(−127~127 之類),與典型實作不同。
固定大小型別:ISO C99 stdint.h 定義 intN_t / uintN_t(N = 8, 16, 32, 64),範圍精確保證(含不對稱);上下界巨集為 INTN_MIN、INTN_MAX、UINTN_MAX;printf 需搭配 PRId32、PRIu64 等格式巨集(展開成系統相依的格式字串)(p.103)。
Java 只支援 signed;C/C++ 皆支援 signed 與 unsigned (p.98)。

型別 (64-bit 程式典型值)	最小	最大
`[signed] char`	−128	127
`unsigned char`	0	255
`short`	−32,768	32,767
`int` / `int32_t`	−2,147,483,648	2,147,483,647
`unsigned` / `uint32_t`	0	4,294,967,295
`long` / `int64_t`	−9,223,372,036,854,775,808	9,223,372,036,854,775,807
`unsigned long` / `uint64_t`	0	18,446,744,073,709,551,615

可攜性例外

C 標準不要求有號數用二補數表示,也不保證 long 的確切範圍;追求極致可攜的程式只能假設 Figure 2.11 的最小範圍。但幾乎所有現代機器都用二補數,大量程式依此假設仍可廣泛移植 (p.103)。

2.2.2 無號編碼 (Unsigned Encodings) (p.98-100)

把位元向量 $\vec{x} = [x_{w - 1}, x_{w - 2}, \dots, x_{0}]$ 直接視為二進位數,每個為 1 的 bit $i$ 貢獻 $2^{i}$ :

B 2 U_{w} (\vec{x}) ≐ \sum_{i = 0}^{w - 1} x_{i} 2^{i} (2.1)

值域: $0$ ([00...0])到 $U M a x_{w} ≐ 2^{w} - 1$ ([11...1]);例 $U M a x_{4} = 15$ 。
唯一性原理: $B 2 U_{w}$ 是雙射 (bijection)——每個 0~ $2^{w} - 1$ 的數恰有一個 w-bit 編碼;反函數為 U2B $_{w}$ 。
例: $B 2 U_{4} ([1011]) = 8 + 0 + 2 + 1 = 11$ 。

2.2.3 二補數編碼 (Two's-Complement Encodings) (p.100-106)

最常見的有號數表示。定義:最高有效位 (most significant bit) $x_{w - 1}$ 稱 sign bit,權重為 $- 2^{w - 1}$ (無號時該位權重的相反數);其餘位權重不變:

B 2 T_{w} (\vec{x}) ≐ - x_{w - 1} 2^{w - 1} + \sum_{i = 0}^{w - 2} x_{i} 2^{i} (2.3)

sign bit = 1 → 負數;= 0 → 非負。例: $B 2 T_{4} ([1011]) = - 8 + 2 + 1 = - 5$ ; $B 2 T_{4} ([1111]) = - 1$ 。
值域: $T M i n_{w} ≐ - 2^{w - 1}$ ([10...0])到 $T M a x_{w} ≐ 2^{w - 1} - 1$ ([01...1]); $B 2 T_{w}$ 也是雙射,反函數為 T2B $_{w}$ 。
不對稱性: $| T M i n | = | T M a x | + 1$ ,TMin 沒有正的對應值。因為 sign bit = 1 的一半樣式全是負數,sign bit = 0 的一半含 0,所以正數少一個——這是許多微妙 bug 的根源。
$U M a x_{w} = 2 T M a x_{w} + 1$ :二補數中所有負數樣式在無號解讀下都變成大正數。
−1 的位元樣式 = UMax(全 1);0 在兩種表示下都是全 0 (p.103)。
<limits.h> 定義 INT_MAX、INT_MIN、UINT_MAX 等機器相關常數 (p.104)。
Java 標準強制二補數與 64-bit 案例的精確範圍,確保跨平台行為一致;單一 byte 型別叫 byte 而非 char (p.104)。
實例 (p.104-105):short x = 12345 為 0x3039;mx = -x 為 0xCFC7 = [1100111111000111],依式 (2.3) 得 −12,345;同一樣式無號解讀為 53,191。

常數	w=8	w=16	w=32	w=64
$U M a x_{w}$	0xFF (255)	0xFFFF (65,535)	0xFFFFFFFF (4,294,967,295)	0xFFFF...F (≈1.8×10¹⁹)
$T M i n_{w}$	0x80 (−128)	0x8000 (−32,768)	0x80000000 (−2,147,483,648)	0x8000...0
$T M a x_{w}$	0x7F (127)	0x7FFF (32,767)	0x7FFFFFFF (2,147,483,647)	0x7FFF...F
−1	0xFF	0xFFFF	0xFFFFFFFF	0xFFFF...F

替代表示法 (Aside, p.104)

反碼 (Ones' complement):sign bit 權重為 $- (2^{w - 1} - 1)$ ,即 $B 2 O_{w} (\vec{x}) ≐ - x_{w - 1} (2^{w - 1} - 1) + \sum_{i = 0}^{w - 2} x_{i} 2^{i}$ 。
符號-大小 (Sign magnitude): $B 2 S_{w} (\vec{x}) ≐ (- 1)^{x_{w - 1}} \cdot \sum_{i = 0}^{w - 2} x_{i} 2^{i}$ 。
兩者都有 +0 與 −0 兩種零編碼(sign-magnitude 的 −0 是 [10...0];ones' complement 的 −0 是 [11...1]),現代機器幾乎不用;sign magnitude 用於浮點數,見 02-Information-Representation/04-Floating-Point。
名稱由來:two's complement 因 $- x = 2^{w} - x$ (一個 2);ones' complement 因 $- x = [11 \dots 1] - x$ (多個 1)。

2.2.4 有號與無號間的轉換 (Conversions between Signed and Unsigned) (p.106-110)

C 的 cast(如 (unsigned) x、(int) u)在多數實作採位元層觀點而非數值觀點:保持位元樣式不變,只改變解讀方式。例:(unsigned short)(-12345) 得 53,191(同為 0xCFC7);(int) 4294967295u 得 −1(同為 0xFFFFFFFF)。

定義 $T 2 U_{w} (x) ≐ B 2 U_{w} (T 2 B_{w} (x))$ 、 $U 2 T_{w} (u) ≐ B 2 T_{w} (U 2 B_{w} (u))$ 。由式 (2.1)(2.3) 相減可得 $B 2 U_{w} (\vec{x}) - B 2 T_{w} (\vec{x}) = x_{w - 1} 2^{w}$ ,故:

T 2 U_{w} (x) = x + x_{w - 1} 2^{w} = {\begin{cases} x + 2^{w}, & x < 0 \\ x, & x \geq 0 \end{cases} (2.5, 2.6)

U 2 T_{w} (u) = - u_{w - 1} 2^{w} + u = {\begin{cases} u, & u \leq T M a x_{w} \\ u - 2^{w}, & u > T M a x_{w} \end{cases} (2.7, 2.8)

T2U:二補數 → 無號 (Figure 2.17)      U2T:無號 → 二補數 (Figure 2.18)

 二補數                無號              無號                 二補數
 TMax ──不變──▶ TMax                  UMax ──−2^w──▶ −1
   0  ──不變──▶ 0                    2^w−1 │ (>TMax 的大數變負)
  −1  ──+2^w──▶ UMax                TMax+1 ──−2^w──▶ TMin
 TMin ──+2^w──▶ TMax+1 = 2^(w−1)      TMax ──不變──▶ TMax
 (負數變大正數)                          0  ──不變──▶ 0

在 $0 \leq x \leq T M a x_{w}$ 區間,兩種表示完全相同(T2U(x) = x,U2T(x) = x);區間外則相差 $\pm 2^{w}$ 。
極端值: $T 2 U_{w} (- 1) = U M a x_{w}$ (最接近 0 的負數 → 最大無號數); $T 2 U_{w} (T M i n_{w}) = 2^{w - 1} = T M a x_{w} + 1$ 。
對同一位元樣式,兩種解讀值恆滿足:負數解讀 + $2^{w}$ = 無號解讀(如 −12,345 + 65,536 = 53,191)。

2.2.5 C 語言中的 Signed vs. Unsigned (p.110-112)

常數預設為 signed(如 12345、0x1A2B);加後綴 U/u 成為 unsigned(如 12345U)。轉換可經顯式 cast 或隱式賦值(tx = ux;)發生,兩者效果相同(套用 U2T / T2U)。

printf 的 %d(有號十進位)、%u(無號十進位)、%x(十六進位)不檢查型別——可用 %u 印 int,直接以另一種解讀輸出。例:int x = -1 以 %u 印出 4294967295;unsigned u = 2147483648 以 %d 印出 −2147483648。
關鍵規則:當運算中一個運算元為 signed、另一個為 unsigned,C 隱式將 signed 轉為 unsigned 再運算。對算術運算影響不大,但對 <、> 等關係運算子產生違反直覺的結果(Figure 2.19)。

運算式	實際比較型別	結果	說明
`0 == 0U`	unsigned	1
`-1 < 0`	signed	1
`-1 < 0U`	unsigned	0 ⚠	−1 → 4294967295U
`2147483647 > -2147483647-1`	signed	1	TMax > TMin
`2147483647U > -2147483647-1`	unsigned	0 ⚠	TMin → 2³¹ = TMax+1
`2147483647 > (int) 2147483648U`	signed	1 ⚠	2³¹ → TMin
`-1 > -2`	signed	1
`(unsigned) -1 > -2`	unsigned	1	兩邊皆轉無號,UMax > UMax−1

為何 TMin 要寫成 -2147483647-1?(Web Aside DATA:TMIN, p.113)

-2147483648 在 C 中是「對常數 2147483648 取負」,而 2147483648 已超出 int 正數範圍——二補數不對稱性與 C 轉換規則的交互作用使其型別解讀出現詭異行為。因此 limits.h 定義 #define INT_MIN (-INT_MAX - 1)。

2.2.6 位元擴展 (Expanding the Bit Representation) (p.112-116)

小型別 → 大型別的轉換恆可保值,規則依原型別而定:

零擴展 (zero extension):無號數補前導 0。 ${\vec{u}}^{'} = [0, \dots, 0, u_{w - 1}, \dots, u_{0}]$ ,則 $B 2 U_{w^{'}} ({\vec{u}}^{'}) = B 2 U_{w} (\vec{u})$ (由式 2.1 直接可得)。
符號擴展 (sign extension):二補數複製 sign bit 於前。 ${\vec{x}}^{'} = [x_{w - 1}, \dots, x_{w - 1}, x_{w - 1}, \dots, x_{0}]$ ,則 $B 2 T_{w^{'}} ({\vec{x}}^{'}) = B 2 T_{w} (\vec{x})$ 。
證明關鍵(對 k 歸納,每次擴展 1 bit): $- x_{w - 1} 2^{w} + x_{w - 1} 2^{w - 1} = - x_{w - 1} 2^{w - 1}$ ,即利用 $2^{w} - 2^{w - 1} = 2^{w - 1}$ ——新增負權重 bit 與舊 sign bit 轉正的效果相抵,值不變 (p.115)。

sign extension 保值示意 (w=3 → w=4, Figure 2.20):
[101]  = -4 + 1           = -3
[1101] = -8 + 4 + 1       = -3   (新 sign bit 的 -8 與轉正的 +4 合成 -4)
[111]  = -4 + 2 + 1       = -1
[1111] = -8 + 4 + 2 + 1   = -1

實例 (p.113-114):short sx = -12345 → int x = sx 得 0xFFFFCFC7(前補 16 個 1,即 0xFFFF);unsigned short usx = 53191 → unsigned ux = usx 得 0x0000CFC7(前補 16 個 0)。16-bit 時兩者位元相同,擴展到 32-bit 後分道揚鑣。

大小與型別轉換的順序 (p.116)

short sx = -12345; unsigned uy = sx; 結果是 4,294,954,951(0xFFFFCFC7)而非 53,191。C 標準規定先改變大小、再改變型別:(unsigned) sx ≡ (unsigned)(int) sx(先 sign extend 再重新解讀),而非 (unsigned)(unsigned short) sx。

2.2.7 截斷 (Truncating Numbers) (p.117-118)

將 w-bit 數截斷為 k-bit:直接丟棄高位的 w−k 個 bit,保留 ${\vec{x}}^{'} = [x_{k - 1}, \dots, x_{0}]$ 。截斷可能改變數值——是一種 overflow。

無號截斷:被丟棄的 bit 權重 $2^{i}$ ( $i \geq k$ )在 mod $2^{k}$ 下皆為 0,故 $B 2 U_{k} ([x_{k - 1}, \dots, x_{0}]) = B 2 U_{w} ([x_{w - 1}, \dots, x_{0}]) mod 2^{k} (2.9)$
二補數截斷:先當無號取 mod,再把 bit $x_{k - 1}$ 的權重由 $2^{k - 1}$ 改為 $- 2^{k - 1}$ (即套 U2T): $B 2 T_{k} ([x_{k - 1}, \dots, x_{0}]) = U 2 T_{k} (B 2 U_{w} ([x_{w - 1}, \dots, x_{0}]) mod 2^{k}) (2.10)$
實例:int x = 53191; short sx = (short) x; → 53,191 mod 2¹⁶ = 53,191 > TMax₁₆,故 sx = 53,191 − 65,536 = −12,345;再 cast 回 int 會 sign extend,得 y = −12,345(而非原本的 53,191)。

擴展 vs. 截斷 資料流:
              zero ext (unsigned):前補 0
  w-bit ────────────────────────────────▶ w'-bit  (w' > w, 保值)
              sign ext (2's comp):前補 sign bit

              truncate:丟棄高位 w−k bits
  w-bit ────────────────────────────────▶ k-bit   (可能 overflow: mod 2^k)

2.2.8 Signed vs. Unsigned 的使用建議 (p.119-120)

隱式 signed→unsigned 轉換在程式碼中毫無視覺線索,是難以察覺的 bug 來源。經典錯誤模式(源自 Practice Problems 2.25、2.26):

unsigned length 為 0 時,迴圈條件 i <= length-1:length-1 是無號運算,0−1 wrap 成 $U M a x$ ,條件永遠成立 → 越界存取、記憶體錯誤。修正:改用 i < length。
strlen(s) - strlen(t) > 0:size_t 為無號,兩無號數相減結果仍為無號、永不為負——s 較短時差值 wrap 成大正數,誤判為「較長」。修正:直接比較 strlen(s) > strlen(t)。
一勞永逸的辦法之一:完全避免 unsigned。C 以外極少語言支援無號整數;Java 只有 signed 二補數,>> 保證算術移位、>>> 執行邏輯移位。
unsigned 的正當用途:把 word 視為純位元集合(打包 Boolean 旗標 flags)、位址 (address) 天生無號(系統程式常用)、實作模運算 (modular arithmetic) 與多精度算術 (multiprecision arithmetic) 套件。

移位相關備註(本頁範圍起頭的 Asides, p.95)

移位量 $k \geq w$ :C 標準未定義行為;許多機器實際只取移位量的低 $\log_{2} w$ 位(即位移 $k mod w$ ),但不可依賴——移位量應保持小於 word size。Java 則明文規定取模。
運算子優先權:1<<2 + 3<<4 等於 (1 << (2+3)) << 4 = 512,而非直覺的 (1<<2)+(3<<4) = 52——加減法優先權高於移位。不確定就加括號。

Exam/Test Patterns

情境 / 關鍵字	答案
給 hex/bit pattern 求無號值	套 $B 2 U_{w} = \sum x_{i} 2^{i}$ (每個 1-bit 加 $2^{i}$ )
給 hex/bit pattern 求二補數值	套 $B 2 T_{w}$ :最高位算 $- 2^{w - 1}$ ,其餘同無號(如 0xA=[1010] → $- 8 + 2 = - 6$ )
判斷 disassembler 中 32-bit hex 常數正負 (Prob 2.18)	最高 hex digit 為 8~F(最高 bit=1)→ 負;值 = 無號值 − $2^{32}$
求 w-bit 的 UMax / TMin / TMax	$2^{w} - 1$ / $- 2^{w - 1}$ / $2^{w - 1} - 1$ ;hex:全 F / `8` 後全 0 / `7` 後全 F
為何負數範圍比正數多一個?	二補數不對稱:sign bit=1 全為負;sign bit=0 那半包含 0
負數 x cast 成 unsigned 的值	$x + 2^{w}$ (位元不變);T2U(−1)=UMax、T2U(TMin)=TMax+1
大無號數 u cast 成 int	$u - 2^{w}$ (當 $u > T M a x_{w}$ );U2T₃₂( $2^{31}$ ) = TMin₃₂
signed 與 unsigned 混合比較	signed 隱式轉 unsigned 再比;`-1 < 0U` → 0 (false)
`unsigned length`、迴圈 `i <= length-1`、length=0	0−1 wrap 成 UMax,條件永真 → 記憶體錯誤
兩個 `size_t`(無號)相減判大小	差永為非負,判斷失效;改用 `>` 直接比較
short → int(有號)擴展	sign extension:前補 sign bit 複本,值不變
unsigned short → unsigned 擴展	zero extension:前補 0,值不變
`short` 負數直接 cast 成 `unsigned`(同時改大小與型別)	先改大小(sign extend)再改型別:得 $x + 2^{32}$ 而非 $x + 2^{16}$
int → short 截斷後的值	先 $x mod 2^{16}$ ,若結果 > TMax₁₆ 再減 $2^{16}$
`(word << 24) >> 24` 對 unsigned vs int 的差別 (Prob 2.23)	unsigned 邏輯右移(高位補 0);int 算術右移(sign extend)→ 後者可做低 byte 的符號擴展
為何 INT_MIN 定義為 `(-INT_MAX - 1)`	常數 2147483648 超出 `int` 正範圍,直接寫 `-2147483648` 型別解讀有陷阱
`1<<2 + 3<<4` 的值	512(加法優先權高於移位,結合為 `(1<<5)<<4`)
移位量 ≥ w 的行為	C 未定義;許多機器取 $k mod w$ ,不可依賴
反碼 / 符號-大小表示的共同特徵	都有 +0 與 −0 兩種零編碼

02-Information-Representation/01-Information-Storage-and-Bits — 位元組、十六進位、位移運算等前置基礎
02-Information-Representation/03-Integer-Arithmetic — 本節編碼在加法/乘法 overflow 下的行為( $+_{w}^{u}$ 、 $+_{w}^{t}$ 、 $*_{w}^{u}$ 、 $*_{w}^{t}$ )
02-Information-Representation/04-Floating-Point — sign-magnitude 編碼用於 IEEE 754 浮點數
03-Machine-Level-Programs/01-Program-Encodings-and-Data-Formats — x86-64 上各 C 型別的機器層資料格式
03-Machine-Level-Programs/06-Buffer-Overflow-and-Pointer-Safety — unsigned/隱式轉換 bug 引發的安全漏洞

Overview Table

2.2.1 整數資料型別 (Integral Data Types) (p.96-98)

2.2.2 無號編碼 (Unsigned Encodings) (p.98-100)

2.2.3 二補數編碼 (Two's-Complement Encodings) (p.100-106)

2.2.4 有號與無號間的轉換 (Conversions between Signed and Unsigned) (p.106-110)

2.2.5 C 語言中的 Signed vs. Unsigned (p.110-112)

2.2.6 位元擴展 (Expanding the Bit Representation) (p.112-116)

2.2.7 截斷 (Truncating Numbers) (p.117-118)

2.2.8 Signed vs. Unsigned 的使用建議 (p.119-120)

Exam/Test Patterns

Related Notes