C語言位圖算法實作：高效位操作技巧

位圖（Bitmap）是一種極其節省記憶體的資料結構，利用位元級操作來標記資料的狀態（如存在與否、真假值等）。在 C 語言中，透過位運算實作位圖不僅效能極高，更能展現底層程式設計的精髓。本文將詳細解析位圖的核心操作——設定位、清除位，並提供完整可執行的程式碼範例。

核心原理：位元運算與索引計算

位圖本質上是一個無符號長整數（unsigned long）陣列。每個 unsigned long 通常佔用 64 位元（視平台而定），可儲存 64 個布林狀態。關鍵在於如何將任意位元索引 n 映射到陣列的具體元素與位元位置：

• 陣列索引：n / (sizeof(unsigned long) * 8) —— 確定屬於哪一個 unsigned long 元素。
• 位元偏移：n % (sizeof(unsigned long) * 8) —— 確定在該元素內的具體位元位置（0-63）。

關鍵函數實作

1. 設定位 set_bit

使用位元 OR (|) 操作配合左移，將目標位元設為 1：

void set_bit(void *base, unsigned long n) {
    unsigned long *m = (unsigned long*) base;
    unsigned long size = sizeof(unsigned long) * 8; // 通常為 64
    m[n / size] |= 1UL << (n % size);
}

2. 清除位 clear_bit

使用位元 AND (&) 操作配合取反（~），將目標位元設為 0：

void clear_bit(void *base, unsigned long n) {
    unsigned long *m = (unsigned long*) base;
    unsigned long size = sizeof(unsigned long) * 8;
    m[n / size] &= ~(1UL << (n % size));
}

完整範例程式

以下程式示範對陣列 value[2]（共 128 位元）進行位元 0 與 63 的設定與清除，並以十六進位格式輸出結果驗證：

#include <stdio.h>

void set_bit(void *base, unsigned long n) {
    unsigned long *m = (unsigned long*) base;
    unsigned long size = sizeof(unsigned long) * 8;
    m[n / size] |= 1UL << (n % size);
}

void clear_bit(void *base, unsigned long n) {
    unsigned long *m = (unsigned long*) base;
    unsigned long size = sizeof(unsigned long) * 8;
    m[n / size] &= ~(1UL << (n % size));
}

int main() {
    unsigned long value[2] = {0}; // 128 bits, 全部初始為 0

    // 設定第 0 位 (value[0] 的最低位) 與第 63 位 (value[0] 的最高位)
    set_bit(value, 0);
    set_bit(value, 63);

    printf("Set:\n");
    printf("0x%016lx, 0x%016lx\n", value[0], value[1]);
    // 預期輸出: 0x8000000000000001, 0x0000000000000000

    // 清除剛才設定的兩個位元
    clear_bit(value, 0);
    clear_bit(value, 63);

    printf("Clear:\n");
    printf("0x%016lx, 0x%016lx\n", value[0], value[1]);
    // 預期輸出: 0x0000000000000000, 0x0000000000000000

    return 0;
}

實務應用與注意事項

• 型別安全：使用 void* 參數使函數能接受任意記憶體區塊，呼叫端需確保記憶體對齊且足夠大。
• 跨平台相容：sizeof(unsigned long) * 8 自動適應 32/64 位元系統，避免硬編碼 32 或 64。
• 擴充功能：同理可實作 test_bit（檢測位元）、flip_bit（翻轉位元）等操作。
• 效能優勢：位圖操作僅需極少 CPU 指令，適用於高效能快取標記、記憶體分配器、布隆過濾器等場景。

掌握位圖算法，不僅能優化記憶體使用，更能深入理解計算機系統中位元級操作的威力。嘗試將此模組封裝為通用的標頭檔（bitmap.h），即可在專案中輕鬆複用。