資訊儲存與位元運算 (Information Storage & Bit Operations)

Overview Table

2.1 資訊儲存:記憶體即位元組陣列 (p.70)

多數電腦不以個別 bit 為單位存取記憶體,而以 8-bit 的 byte 作為最小可定址單位 (smallest addressable unit)。機器層級程式將記憶體視為一個巨大的位元組陣列,稱為 virtual memory;每個 byte 由唯一編號 address 識別,所有可能位址的集合構成 virtual address space。

• Virtual address space 只是呈現給程式的概念性影像;實際由 DRAM、flash、磁碟、特殊硬體與 OS 軟體共同實作(詳見 09-Virtual-Memory/01-Address-Spaces-and-VM-Caching 對應章節)。
• C 的 pointer 值 = 某儲存區塊第一個 byte 的 virtual address;compiler 為 pointer 維護型別資訊以產生不同機器碼。
• 但編譯後的機器碼沒有任何型別資訊——程式物件只是一塊 bytes,程式本身也只是一串 bytes。

Virtual Memory(概念圖:巨大位元組陣列)
address:  0x000  0x001  0x002  0x003  ...   0x100  0x101  ...  2^w - 1
         +------+------+------+------+     +------+------+
         | byte | byte | byte | byte | ... | byte | byte | ...
         +------+------+------+------+     +------+------+
              程式資料 / 指令 / 控制資訊 全部存於此陣列中

2.1.1 Hexadecimal Notation (p.72)

一個 byte 為 8 bits,二進位範圍 ${00000000}_2\sim {11111111}_2$,十進位 $0\sim 255$,十六進位 ${\mathtt{00}}_{16}\sim {\mathtt{FF}}_{16}$。二進位太冗長、十進位轉換麻煩,故以 hexadecimal(基底 16,數字 0-9 + A-F)描述 bit pattern。C 中以 0x 或 0X 開頭,大小寫皆可(0xFA1D37B = 0xfa1d37b)。

轉換方法(常考手算):

• hex → binary:每個 hex digit 直接展開成 4 bits。
• binary → hex:從右邊開始每 4 bits 一組;若總位數非 4 的倍數,最左組位數不足(等效補前導 0)。
• 2 的冪 → hex:$x=2^n$,令 $n=i+4j$($0\le i\le 3$),則 hex 表示為前導數字 $2^i$(即 1、2、4、8)後接 $j$ 個 0。例:$2^{11}=2048$,$11=3+4\cdot 2$ → 0x800。
• decimal → hex:反覆除以 16,$x=q\cdot 16+r$,餘數 $r$ 由低位往高位排。例:$314156\to$ 0x4CB2C。
• hex → decimal:各 digit 乘上 16 的冪加總。例:0x7AF $=7\cdot {16}^2+10\cdot 16+15=1967$。

2.1.2 Data Sizes (p.75)

每台電腦有一個 word size,表示 pointer 資料的標稱大小。因 virtual address 以一個 word 編碼,word size 決定最重要的系統參數——virtual address space 的最大值:w-bit 機器的位址範圍為 $0\sim 2^w-1$,程式最多可存取 $2^w$ bytes。

• 32-bit word size → 上限 4 GB(約 $4\times {10}^9$ bytes);64-bit → 16 EB(約 $1.84\times {10}^{19}$ bytes)。
• gcc -m32 編譯出的程式可在 32/64-bit 機器執行;gcc -m64 只能在 64-bit 機器執行——「32-bit 程式 / 64-bit 程式」是編譯方式的區別,不是機器的區別。
• ISO C99 引入固定大小型別 int32_t / int64_t(恰好 4 / 8 bytes),是精確控制資料表示的最佳方式。
• C 標準只規定各型別數值範圍的下限(除固定大小型別外無上限);可攜式程式不應假設確切大小。

2.1.3 Addressing and Byte Ordering (p.78)

跨多 byte 的物件需要兩個慣例:(1) 物件的位址 = 所占 bytes 中最小的位址,且多 byte 物件幾乎都存為連續位元組;(2) bytes 在記憶體中的排列順序。設 w-bit 整數 bit 表示為 $[x_{w-1},x_{w-2},\dots ,x_1,x_0]$,most significant byte 為 $[x_{w-1},\dots ,x_{w-8}]$、least significant byte 為 $[x_7,\dots ,x_0]$:

• Little endian:least significant byte 放在最低位址(最前)。Intel 相容機器、Android/iOS 上的 ARM 皆是。
• Big endian:most significant byte 放在最前。多數 IBM、Oracle(Sun SPARC)機器。
• Bi-endian 硬體(如 ARM)兩者皆可,但實務上 OS 選定後即固定;兩種順序沒有技術優劣,純屬慣例(名稱出自 Gulliver's Travels)。

int x = 0x01234567,位址 &x = 0x100(int 為 4 bytes)

Big endian:     0x100  0x101  0x102  0x103
             ... | 01 | | 23 | | 45 | | 67 | ...   高位 byte 在前

Little endian:  0x100  0x101  0x102  0x103
             ... | 67 | | 45 | | 23 | | 01 | ...   低位 byte 在前

位元組順序通常對程式設計師不可見,但三種情境會浮現 (p.79-80):

1. 網路傳輸:little-endian 與 big-endian 機器互傳二進位資料會反序,故網路程式必須依循 network standard 進行 byte order 轉換(見 11-Network-Programming/01-Client-Server-Model-and-Networks 對應章節)。
2. 閱讀 disassembler 輸出:如 x86-64 指令 bytes 01 05 43 0b 20 00 中,後 4 bytes 43 0b 20 00 反序讀為 0x200b43——little-endian 機器上機器碼中的數值需反序解讀。
3. 繞過型別系統:用 cast 或 union 以不同型別檢視同一物件(系統程式設計常用,一般應用不建議)。

檢視位元組表示的工具程式 (p.80-82):typedef unsigned char *byte_pointer;,show_bytes(byte_pointer start, size_t len) 以 printf(" %.2x", start[i]) 逐 byte 印出十六進位;size_t 是表達資料結構大小的首選型別。show_int / show_float / show_pointer 均以 (byte_pointer) &x cast 後傳入,長度用 sizeof(T) 取得——cast 不改變 pointer 的值,只改變編譯器解讀資料的方式;sizeof(T) 回傳型別 T 所需 bytes 數,是可攜性的關鍵。

實測 12345(hex 0x00003039)的結果 (p.82):

• int 與 float 各機器內容相同、僅 byte order 不同;pointer 值則完全機器相依(儲存配置慣例不同)。
• 同值 12345 的 int(0x00003039)與 float(0x4640E400)編碼完全不同,但展開成二進位並適當位移後有 13 個連續相符 bits——伏筆見 02-Information-Representation/04-Floating-Point。

2.1.4 Representing Strings (p.85)

C 字串 = 以 null 字元(值 0)結尾的字元陣列,每個字元以標準編碼表示,最常見為 ASCII。

• show_bytes("12345", 6) 輸出 31 32 33 34 35 00:十進位數字字元 x 的 ASCII 碼恰為 0x3x,結尾 byte 為 0x00。
• 任何使用 ASCII 的系統結果都相同,與 byte ordering、word size 無關 → 文字資料比二進位資料更平台無關 (platform independent)。
• 小寫字母 a~z 的 ASCII 碼為 0x61~0x7A;可用 man ascii 查表 (p.84)。

2.1.5 Representing Code (p.85)

同一個 C 函式 int sum(int x, int y) { return x + y; } 在不同平台編譯出完全不同的機器碼位元組序列(Linux 32 / Windows / Sun / Linux 64 各異)。

• 不同機器型別使用不同且不相容的指令與編碼;甚至相同處理器 + 不同 OS 的編碼慣例也不同,不具 binary compatibility。
• 二進位程式碼幾乎不可跨「機器 + OS」組合移植。
• 核心觀念:對機器而言,程式就只是一串 bytes;機器不保有原始碼的任何資訊(頂多除錯輔助表)。詳見 03-Machine-Level-Programs/01-Program-Encodings-and-Data-Formats。

2.1.6 Introduction to Boolean Algebra (p.86)

Boolean algebra(George Boole, ~1850)將邏輯值 true/false 編碼為 1/0;Claude Shannon 1937 年碩士論文首次將布林代數連結到數位邏輯(電機繼電器網路)的設計與分析。最簡單的布林代數定義於二元素集合 $\{0,1\}$:

Bit vector 擴充:對長度 w 的位元向量 $a=[a_{w-1},\dots ,a_0]$、$b=[b_{w-1},\dots ,b_0]$,定義 $(a\mathrm{\&}b{)}_i=a_i\mathrm{\&}{b}_i$($0\le i<w$),|、^、~ 同理逐位擴充。例(w=4):0110 & 1100 = 0100、0110 | 1100 = 1110、0110 ^ 1100 = 1010、~1100 = 0011。

重要代數性質(p.88 Web Aside DATA:BOOL):

• & 對 | 分配:$a\mathrm{\&}(b\mid c)=(a\mathrm{\&}b)\mid (a\mathrm{\&}c)$;且 | 也對 & 分配:$a\mid (b\mathrm{\&}c)=(a\mid b)\mathrm{\&}(a\mid c)$(整數加法/乘法沒有後者的對應性質)。
• ^、&、~ 構成 Boolean ring:每個元素是自己的加法反元素——$a\oplus a=0$,且 $(a\oplus b)\oplus a=b$(這是 XOR swap 技巧的理論基礎)。

Bit vector 編碼有限集合 (p.88):子集 $A\subseteq \{0,1,\dots ,w-1\}$ 編碼為 bit vector,$a_i=1⟺i\in A$。此時 | = 聯集 ∪、& = 交集 ∩、~ = 補集。例:[01101001] 編碼 $A=\{0,3,5,6\}$。實際應用如 signal mask(以 bit i 表示 signal i 是否 enabled,見 08-Exceptional-Control-Flow/05-Signals 對應章節)、RGB 三 bits 表示 8 色 (Practice 2.9)。

2.1.7 Bit-Level Operations in C (p.90)

C 直接支援位元運算 | & ~ ^(符號與布林代數一致),可套用於任何整數型別("integral" data type)。求值訣竅:hex 展開成 binary → 逐位運算 → 轉回 hex。

Masking(最常見用途,p.91):mask 是標示「選取哪些 bits」的 bit pattern。

• x & 0xFF 取出 x 的最低位 byte,其餘清 0。例:0x89ABCDEF & 0xFF = 0x000000EF。
• ~0 產生全 1 的 mask,且與 word size 無關——比寫死 0xFFFFFFFF 更可攜。

XOR swap(inplace_swap, p.90;利用 a^a = 0、(a^b)^a = b):
          *x           *y
init:      a            b
step1:     a           a^b     (*y = *x ^ *y)
step2: a^(a^b) = b     a^b     (*x = *x ^ *y)
step3:     b       (a^b)^b = a (*y = *x ^ *y)

2.1.8 Logical Operations in C (p.92)

C 的邏輯運算子 && || ! 對應邏輯上的 or、and、not,與位元運算行為截然不同,極易混淆:

範例 (p.93):!0x41 = 0x00、!0x00 = 0x01、!!0x41 = 0x01、0x69 && 0x55 = 0x01、0x69 || 0x55 = 0x01。

• 只有當引數限定為 0 或 1 時,位元運算行為才與邏輯運算一致。
• Short-circuit 的實用性:a && 5/a 永不除以 0;p && *p++ 永不解參考 null pointer。
• 判斷相等的位元技巧 (Practice 2.15):x == y 等價於 !(x ^ y)。

2.1.9 Shift Operations in C (p.93)

設 x 的 bit 表示為 $[x_{w-1},x_{w-2},\dots ,x_0]$:

• 左移 x << k:得 $[x_{w-k-1},\dots ,x_0,\underset{k}{\underbrace{0,\dots ,0}}]$——丟棄最高 k bits,右端補 k 個 0。
• 右移 x >> k 有兩種形式:
  • Logical(邏輯右移):左端補 k 個 0,得 $[0,\dots ,0,x_{w-1},\dots ,x_k]$。
  • Arithmetic(算術右移):左端補 k 個最高位 bit $x_{w-1}$,得 $[x_{w-1},\dots ,x_{w-1},x_{w-1},\dots ,x_k]$——對 signed 資料有用(保持符號)。
• 移位運算左結合:x << j << k = (x << j) << k;移位量應介於 $0\sim w-1$。

8-bit 範例 (p.94):
x = [01100011]                  x = [10010101]
x << 4            = [00110000]        [01010000]   右端補 0
x >> 4 (logical)  = [00000110]        [00001001]   左端補 0
x >> 4 (arith.)   = [00000110]        [11111001]   左端補 MSB
                    (MSB=0,兩種相同)   (MSB=1,結果不同!)

Exam/Test Patterns

Related Notes

• 02-Information-Representation/02-Integer-Representations — unsigned 與 two's-complement 編碼,承接本節的 bit pattern 基礎
• 02-Information-Representation/03-Integer-Arithmetic — 移位實作乘除法、overflow 行為
• 02-Information-Representation/04-Floating-Point — 12345 的 int/float 編碼中 13 個相符 bits 的解答
• 01-Computer-Systems-Tour/01-Information-and-Program-Translation — 「資訊 = bits + context」的總覽視角
• 03-Machine-Level-Programs/01-Program-Encodings-and-Data-Formats — 機器碼位元組表示與 disassembler
• 11-Network-Programming/01-Client-Server-Model-and-Networks — network byte order 與 endianness 轉換的實務場景