CS:APP 第 2 章：資訊的表示與處理 (Data Representation) Integer Overflow & Casting

1. 資訊存儲 (Information Storage)

電腦最小的可定址單位是 Byte (8 bits)。

U8 = 0x00~0xFF

字組大小 (Word Size)：32-bit 或 64-bit 決定了虛擬位址空間的最大範圍。

位元組順序 (Byte Ordering)：

Big Endian (大端序) 的邏輯最符合人類閱讀習慣

• 0x01234567 在 Little Endian 記憶體中的排列為 67 45 23 01

• Big Endian通常小的在後（尾端）但是大部分cpu 都是使用 Little Endian 

2. 整數表示法 (Integer Representations)

Unsigned (無符號)：直接二進位編碼

0x1 = 1

0x10 =2

0x11 = 1+2 = 3

Two's Complement (二進位補數)：用於表示正負數，最高位元（MSB）權重為負。

S8:

0000 0000 = 0

0100 0000 = 64

1000 0000 = -128

1100 0000 = -128+64 = -64

TMin 與 TMax 的不對稱性：在 8-bit 中，範圍是 -128 到 127。

3. 整數運算與溢位 (Integer Arithmetic)

整數運算的本質是 模運算 (Modular Arithmetic)。

• Unsigned Addition：結果若超過 $2^w - 1$，則會減去 $2^w$（Wrap around）。

• Two's Complement Addition：

  • 正溢位：兩個正數相加得到負數。

  • 負溢位：兩個負數相加得到正數。

• 乘法與位移：編譯器常用 shl (左移) 代替乘以 2 的冪次，用 shr (右移) 代替除法。

• 邏輯右移 (Logical)：補 0（用於 Unsigned）。

• 算術右移 (Arithmetic)：補符號位元（用於 Signed）。

4. 浮點數 (Floating Point)

// 利用 union 觀察同一塊記憶體的位元分佈

typedef union {

float f;

struct {

uint32_t frac : 23; // 尾數 (Fraction)

uint32_t exp : 8; // 階碼 (Exponent)

uint32_t sign : 1; // 正負號 (Sign)

} parts;

uint32_t raw;

} FloatConv;

r@ubuntu-server:~/leaarning$ ./test

--- Analysis: Normalized 1.0 (1.000000) ---

Raw Hex: 0x3F800000

Sign: 0, Exponent (Raw): 127, Fraction: 0x000000

Type: Normalized

Actual Exponent (E): 0

--- Analysis: Normalized -0.15625 (-0.156250) ---

Raw Hex: 0xBE200000

Sign: 1, Exponent (Raw): 124, Fraction: 0x200000

Type: Normalized

Actual Exponent (E): -3

--- Analysis: Denormalized Small (0.000000) ---

Raw Hex: 0x000002CA

Sign: 0, Exponent (Raw): 0, Fraction: 0x0002CA

Type: Denormalized (Subnormal - Very small)

--- Analysis: Infinity (inf) ---

Raw Hex: 0x7F800000

Sign: 0, Exponent (Raw): 255, Fraction: 0x000000

Type: Special Value (Infinity)

--- Analysis: NaN (nan) ---

Raw Hex: 0x7FC00000

Sign: 0, Exponent (Raw): 255, Fraction: 0x400000

Type: Special Value (NaN)

==============================================================

1. 無符號整數溢位 (Unsigned Integer Overflow)

 

unsigned int a = UINT_MAX;

a = a + 1; // 產生溢位

Unsigned Max: 4294967295

After Overflow (a + 1): 0

2. 有符號整數溢位 (Signed Integer Overflow)

int b = INT_MAX;

b = b + 1;

Signed Max: 2147483647

After Overflow: -2147483648

3. 隱式型別轉換與正負號問題 (Implicit Casting & Signedness)

int x = -1;

unsigned int y = 1;

驚訝吧！-1 居然大於 1

原因：x 被轉成 unsigned 的數值是 4294967295

4. 窄化轉換 (Narrowing Conversion)

int big_val = 0x12345678;

char small_val = (char)big_val; // 只保留最後 8 bits

Original: 0x12345678

Truncated: 0x78 (Only 0x78 is kept)

CS:APP -「第 6 章：記憶體階層」 Cache Locality: 「在處理大數據陣列時，Row-major 和 Column-major 的存取順序對效能有什麼影響？」

Q

Cache Locality: 「在處理大數據陣列時，Row-major 和 Column-major 的存取順序對效能有什麼影響？」

A 

• Row-major (連續): 當 CPU 讀取 arr[0][0] 時，會把後面的 arr[0][1], arr[0][2] 一起放進 Cache Line (通常 64 bytes)。下一次迴圈要用時，資料已經在 Cache 裡了（Cache Hit）。

• Column-major (跳躍): 存取 arr[0][0] 後，下一個要拿 arr[1][0]。這兩個元素在記憶體中隔了 $10000 \times 4$ bytes，遠超過 Cache Line 的長度。CPU 必須重新去主記憶體抓資料（Cache Miss），導致速度大幅下降。

什麼順序會有差？

在現代 CPU 架構中，當你從記憶體讀取一個位元組時，硬體並不會只抓那一個位元組，而是抓取一整塊連續的資料，這被稱為 Cache Line（通常是 64 Bytes）。

## 1. Row-major (列優先) 存取：Cache Friendly

C 語言的二維陣列在記憶體中是橫向連續存放的。如果你用 row-major 順序存取（外迴圈是 i, 內迴圈是 j）

## 2. Column-major (行優先) 存取：Performance Killer

如果你把迴圈順序對調（外迴圈是 j, 內迴圈是 i）：

每次存取 array[i][j] 之後，下一個要抓的是 array[i+1][j]。在記憶體中，這兩個位址隔了「一整列」的距離。Cache Line 抓進來的資料還沒用到就被踢出去了。

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#define N 10000 // 10000 x 10000 的矩陣，約佔 400MB 記憶體

// 分配在 Heap 以免 Stack Overflow

int (*arr)[N];

int main() {

arr = malloc(sizeof(int[N][N]));

if (!arr) return 1;

struct timespec start, end;

double cpu_time_used;

// --- 測試 1: Row-major (順著記憶體位址存取) ---

clock_gettime(CLOCK_MONOTONIC, &start);

long long sum = 0;

for (int i = 0; i < N; i++) {

for (int j = 0; j < N; j++) {

sum += arr[i][j];

}

}

clock_gettime(CLOCK_MONOTONIC, &end);

cpu_time_used = (end.tv_sec - start.tv_sec) + (end.tv_nsec - start.tv_nsec) / 1e9;

printf("Row-major (順向) 耗時: %f 秒\n", cpu_time_used);

// --- 測試 2: Column-major (跳躍記憶體位址存取) ---

clock_gettime(CLOCK_MONOTONIC, &start);

sum = 0;

for (int j = 0; j < N; j++) { // 注意：這裡迴圈對調了

for (int i = 0; i < N; i++) {

sum += arr[i][j];

}

}

clock_gettime(CLOCK_MONOTONIC, &end);

cpu_time_used = (end.tv_sec - start.tv_sec) + (end.tv_nsec - start.tv_nsec) / 1e9;

printf("Column-major (跳向) 耗時: %f 秒\n", cpu_time_used);

free(arr);

return 0;

}

r@ubuntu-server:~/leaarning$ gcc -O0 cache_test.c -o cache_test

r@ubuntu-server:~/leaarning$ ./cache_test 

Row-major (順向) 耗時:   0.260539 秒

Column-major (跳向) 耗時: 0.429585 秒