C 語言效能優化：減少運算量的兩大核心策略

編輯：關於C語言

前言

程式優化的第二大方向 (第一是減少記憶體存取) 是**減少 CPU 運算指令數**。本文歸納兩大核心思路：演算法層面降低複雜度與實作層面消除冗餘運算。

策略一：演算法層面 — 降低時間複雜度

場景	朴素做法	優化演算法	複雜度提升
查找	線性掃描	雜湊表 / 二分搜尋 / Trie	O(n) → O(1) / O(log n)
排序	氣泡/插入	快速排序 / 合併排序 / 基數排序	O(n²) → O(n log n)
字串匹配	暴力比對	KMP / Boyer-Moore / AC 自動機	O(nm) → O(n+m)
圖最短路徑	Floyd-Warshall	Dijkstra / A* / SPFA	O(V³) → O(E log V)
動態規劃	遞迴重複計算	備忘錄 / 底向上 DP / 狀態壓縮	指數 → 多項式

鐵律：**演算法優化永遠優於微優化**。選對資料結構與演算法，效能常提升數量級。

策略二：實作層面 — 消除冗餘運算

1. 將不變量移出迴圈 (Loop-Invariant Code Motion)


/* 朴素 */
for (int i = 0; i < n; ++i) {
    double r = sqrt(a * a + b * b);  // a,b 不變，每次都算
    result[i] = r * data[i];
}

/* 優化 */
double r = sqrt(a * a + b * b);      // 提到迴圈外
for (int i = 0; i < n; ++i) {
    result[i] = r * data[i];
}

現代編譯器 `-O2` 會自動完成，但複雜表達式 (函數呼叫、全域變數) 常漏優化，**手動提取更保險**。

2. 強度削減

昂貴運算	替代方案	適用場景
乘法/除法	移位/加法/查表	乘以 2 的冪、除以常數
取模 `% n`	`& (n-1)` (n 為 2 的冪)	環狀緩衝區索引
浮點數 `sqrt`	查表 / 快速倒數平方根	圖形/物理模擬
三角函數	查表 / 多項式逼近	音訊/訊號處理


/* 環狀緩衝區索引優化 */
#define MASK (BUFFER_SIZE - 1)  // BUFFER_SIZE 必須是 2 的冪
index = (index + 1) & MASK;     // 替代 index = (index + 1) % BUFFER_SIZE

3. 避免重複計算子表達式 (Common Subexpression Elimination)


/* 朴素 */
x = a * b + c;
y = a * b - d;

/* 優化 */
tmp = a * b;
x = tmp + c;
y = tmp - d;

編譯器 `-O1` 以上通常自動處理，但跨基本區塊或含函數呼叫時常失效。

4. 預計算與查表


/* 編譯期/啟動期建立查表 */
static const uint8_t popcount[256] = {
    0,1,1,2,1,2,2,3, ...  // 0~255 各數字的 1-bit 個數
};

/* 執行期 O(1) 計算 32-bit 整數 population count */
int popcnt32(uint32_t x) {
    return popcount[x & 0xFF] +
           popcount[(x >> 8) & 0xFF] +
           popcount[(x >> 16) & 0xFF] +
           popcount[x >> 24];
}