C/C++ 位圖（Bitmap）詳解：實現、應用與優化

什麼是位圖

位圖（Bitmap）是一種用連續位來表示集合的數據結構。每個位對應一個元素的存在性（0/1），極其節省空間。常用於大規模數據去重、快速查找、壓縮存儲等場景。

核心操作實現

假設用 int 數組 bitmap[] 存儲，每個 int 32 位。

#define SHIFT 5          // 2^5 = 32
#define MASK 0x1F        // 32-1 = 31，用於取模
#define MAX 1024*1024*1024
int bitmap[MAX / 32];

// 設置第 i 位為 1
void set(int i) {
    bitmap[i >> SHIFT] |= (1 << (i & MASK));
}

// 測試第 i 位
int test(int i) {
    return bitmap[i >> SHIFT] & (1 << (i & MASK));
}

// 清除第 i 位
void clear(int i) {
    bitmap[i >> SHIFT] &= ~(1 << (i & MASK));
}

關鍵技巧：i >> 5 等價 i / 32 定位數組下標；i & 31 等價 i % 32 定位位偏移。

C++ STL bitset

標準庫提供 <bitset>，固定大小編譯期確定，功能豐富（set, reset, test, count, any, none, to_string 等）。動態大小可用 vector<unsigned long> 或 boost::dynamic_bitset。

典型應用場景

1. 枚舉子集 / 全組合

長度 n 字符串的所有子集對應 0 ~ (1< 的二進制掩碼。遍歷掩碼即可生成所有組合。