位圖演算法完全指南：原理、應用場景與C語言高效實作

編輯：關於C語言

什麼是位圖？

位圖使用**單個比特**表示一個元素的狀態（存在/不存在、真/假、0/1）。一個 32 位整數可表示 32 個元素，空間效率極高，適用於：

大規模數據去重、存在性查詢
整數集合的快速交/並/差運算
記憶體受限環境下的排序、標記

核心資料結構與基本操作

#define BITSPERWORD 32
#define SHIFT 5              // 除以 32：i >> 5
#define MASK 0x1F            // 模 32：i & 31

int bitmap[1 + N/BITSPERWORD];

void set(int i)    { bitmap[i >> SHIFT] |=  (1 << (i & MASK)); }
void clr(int i)    { bitmap[i >> SHIFT] &= ~(1 << (i & MASK)); }
int  test(int i)   { return bitmap[i >> SHIFT] &   (1 << (i & MASK)); }

四大經典應用場景完整實作

場景一：40 億整數存在性查詢（512MB 記憶體）

// N = 4,000,000,000
// 位圖大小 = 4e9 / 32 = 125,000,000 int = 500MB
// 讀入 40 億數，set 對應位
// 查詢時 test 對應位，O(1) 判斷存在性

場景二：判斷整數陣列是否有重複

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

bool has_duplicate(int *arr, int len) {
    if(len == 0) return false;
    
    int max = arr[0];
    for(int i = 1; i < len; i++)
        if(arr[i] > max) max = arr[i];
    
    // 位圖大小 = max + 1 位
    int *bitmap = (int*)calloc((max >> 5) + 1, sizeof(int));
    if(!bitmap) return false;  // 記憶體不足視為無重複
    
    bool dup = false;
    for(int i = 0; i < len; i++) {
        int idx = arr[i] >> 5;
        int bit = arr[i] & 31;
        if(bitmap[idx] & (1 << bit)) { dup = true; break; }
        bitmap[idx] |= (1 << bit);
    }
    free(bitmap);
    return dup;
}

時間 O(n)，空間 O(max)。若 max 過大（如 10⁹），改用雜湊表。

場景三：位圖排序（適用於無重複、範圍已知整數）

void bitmap_sort(int *arr, int len) {
    if(len == 0) return;
    
    int min = arr[0], max = arr[0];
    for(int i = 1; i < len; i++) {
        if(arr[i] < min) min = arr[i];
        if(arr[i] > max) max = arr[i];
    }
    
    int range = max - min + 1;
    int *bitmap = (int*)calloc((range >> 5) + 1, sizeof(int));
    
    // 標記存在的數 (偏移 min)
    for(int i = 0; i < len; i++)
        bitmap[(arr[i] - min) >> 5] |= 1 << ((arr[i] - min) & 31);
    
    // 回寫排序結果
    int idx = 0;
    for(int i = 0; i < range; i++) {
        int word = bitmap[i >> 5];
        int bit = i & 31;
        if(word & (1 << bit))
            arr[idx++] = i + min;
    }
    free(bitmap);
}

**優勢**：O(n + range)，無比較、無交換，極快。**限制**：需知範圍、無重複、整數類型。

場景四：1000 萬整數排序輸出（1MB 記憶體限制）

#include <stdio.h>
#define N 10000000
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F

int bitmap[1 + N/BITSPERWORD];

void set_bit(int i) { bitmap[i >> SHIFT] |= 1 << (i & MASK); }
int test_bit(int i) { return bitmap[i >> SHIFT] & (1 << (i & MASK)); }

int main() {
    int x;
    while(scanf("%d", &x) == 1) set_bit(x);
    for(int i = 0; i < N; i++)
        if(test_bit(i)) printf("%d\n", i);
    return 0;
}

記憶體：10,000,000 / 32 × 4 = 1.25MB，符合限制。這是《程式設計珠玑》經典案例。

負數處理技巧

位圖索引不能為負，統一轉換為無符號：

// 處理有符號整數
unsigned int ux = (unsigned int)x;  // 二進制位模式不變
// 或偏移法：index = x - min_value

位圖 vs 其他資料結構

特性	位圖	雜湊表	布隆過濾器
空間效率	極高 (1 bit/元素)	中等	極高 (可調)
查詢時間	O(1) 確定	O(1) 平均	O(k) 可能誤判
支援刪除	是	是	否 (標準版)
適用範圍	密集整數集合	稀疏/任意類型	海量去重預檢