【每日算法】Day 17-1：位图（Bitmap）——十亿级数据去重与快速检索的终极方案（C++实现）

解锁海量数据处理的极致空间效率！今日深入解析位图的核心原理与实战应用，从基础操作到分块优化，彻底掌握仅用1bit存储一个数据的压缩艺术。

一、位图核心思想

位图（Bitmap） 是一种通过比特位表示数据存在性的数据结构，核心特性：

1. 空间压缩：每个元素仅占用1bit空间

2. 精确存储：无哈希冲突，无概率型误判

3. 高效操作：位运算实现O(1)复杂度查询与更新

适用场景：

• 海量整数去重（如十亿级数据去重仅需约120MB内存）

• 快速存在性检查

• 数据排序与范围查询

与布隆过滤器的对比：

特性	位图	布隆过滤器
存储方式	精确存储	概率型存储
空间占用	依赖数据范围	依赖数据量和误判率
误判率	无	可调节
支持操作	存在性检查/排序/去重	仅存在性检查

---

二、位图实现原理

1. 存储结构

• 比特数组：用基本类型数组（如uint32_t[]）模拟连续比特位

• 索引计算：

  • 数组下标：index = num / 32

  • 位偏移：offset = num % 32

2. 核心操作

操作	公式	示例（num=35）
设置位	`bits[index]	= (1 << offset)`	`bits[1]	= (1 << 3)`
清除位	bits[index] &= ~(1 << offset)	bits[1] &= ~(1 << 3)
检查位	bits[index] & (1 << offset)	bits[1] & (1 << 3) != 0

---

三、C++手写位图

class Bitmap {
private:static const int BIT_PER_WORD = 32;vector<uint32_t> bits;// 计算索引位置inline pair<int, uint32_t> getPos(int num) const {return {num / BIT_PER_WORD, 1U << (num % BIT_PER_WORD)};}public:Bitmap(int maxNum) {int size = (maxNum + BIT_PER_WORD - 1) / BIT_PER_WORD;bits.resize(size, 0);}void add(int num) {auto [index, mask] = getPos(num);bits[index] |= mask;}void remove(int num) {auto [index, mask] = getPos(num);bits[index] &= ~mask;}bool contains(int num) const {auto [index, mask] = getPos(num);return (bits[index] & mask) != 0;}// 返回所有存储的数字（用于去重后导出）vector<int> getAll() {vector<int> res;for (int i = 0; i < bits.size(); ++i) {for (int j = 0; j < BIT_PER_WORD; ++j) {if (bits[i] & (1U << j)) {res.push_back(i * BIT_PER_WORD + j);}}}return res;}
};

四、五大应用场景

场景1：十亿级手机号去重

需求：
11位手机号去重（范围0-99,999,999,999）
位图优化：

• 使用分块位图，按前3位分块（1000块）

• 每块处理8位数字（约需125MB/块）

• 总内存：1000×125MB = 125GB → 实际分批处理可降至10GB内

---

场景2：快速排序（无重复数字）

void bitmapSort(vector<int>& nums) {if (nums.empty()) return;int maxNum = *max_element(nums.begin(), nums.end());Bitmap bm(maxNum);for (int num : nums) bm.add(num);nums.clear();vector<int> sorted = bm.getAll();nums.swap(sorted);
}

场景3：检测重复元素（LeetCode 217）

bool containsDuplicate(vector<int>& nums) {// 假设数据范围已知（此处示例为0-10^5）Bitmap bm(100000);for (int num : nums) {if (bm.contains(num)) return true;bm.add(num);}return false;
}

场景4：找缺失数字（LeetCode 268）

int missingNumber(vector<int>& nums) {Bitmap bm(nums.size());for (int num : nums) {if (num <= nums.size()) bm.add(num);}for (int i = 0; i <= nums.size(); ++i) {if (!bm.contains(i)) return i;}return -1;
}

场景5：字符去重（ASCII字符集）

string removeDuplicate(string s) {Bitmap bm(128); // ASCII范围0-127string res;for (char c : s) {if (!bm.contains(c)) {res += c;bm.add(c);}}return res;
}

五、位图优化技巧

优化方法	实现原理	适用场景
分块位图	将大范围分割为多个小位图	数据范围过大时
压缩位图	使用RLE/位压缩算法减少内存	稀疏数据存储
并行位图	利用SIMD指令加速批量位操作	高性能计算场景
混合存储	结合布隆过滤器处理超大范围	允许概率型误判时

---

六、大厂真题实战

真题1：十亿级IP地址统计（某大厂2023面试）

需求：
统计独立IP数量，内存限制2GB
位图分块解法：

class IPBitmap {
private:static const int BLOCK_BITS = 24; // 高8位分块（256块）vector<Bitmap> blocks;public:IPBitmap() : blocks(1 << 8, Bitmap(1 << 24)) {}void addIP(uint32_t ip) {int blockID = ip >> 24;int lowPart = ip & 0xFFFFFF;blocks[blockID].add(lowPart);}int countDistinct() {int cnt = 0;for (auto& bm : blocks) {cnt += bm.getAll().size();}return cnt;}
};

真题2：实时在线用户统计（某大厂2024笔试）

需求：
实时统计最近5分钟的活跃用户数（用户ID范围1-1e9）
滑动窗口+位图优化：

class OnlineUsers {
private:deque<pair<Bitmap, time_t>> window;const int WINDOW_SIZE = 300; // 5分钟（秒）public:void heartBeat(int uid) {time_t now = time(nullptr);if (window.empty() || now - window.back().second >= 1) {window.emplace_back(Bitmap(1e9), now);}window.back().first.add(uid);// 移除过期窗口while (!window.empty() && now - window.front().second > WINDOW_SIZE) {window.pop_front();}}int getOnlineCount() {Bitmap merged(1e9);for (auto& [bm, _] : window) {for (int uid : bm.getAll()) {merged.add(uid);}}return merged.getAll().size();}
};

七、常见误区与优化

1. 范围估算错误：未预留足够空间导致溢出

2. 线程安全问题：多线程操作需加锁或使用线程本地存储

3. 位运算错误：位移操作符优先级陷阱（需加括号）

4. 内存对齐优化：按CPU缓存行对齐提升访问速度

---

LeetCode真题训练：

• 217. 存在重复元素

• 268. 丢失的数字

• 442. 数组中重复的数据