解锁海量数据处理的极致空间效率！今日深入解析位图的核心原理与实战应用，从基础操作到分块优化，彻底掌握仅用1bit存储一个数据的压缩艺术。
一、位图核心思想
位图（Bitmap） 是一种通过比特位表示数据存在性的数据结构，核心特性：
空间压缩：每个元素仅占用1bit空间
精确存储：无哈希冲突，无概率型误判
高效操作：位运算实现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();}
};七、常见误区与优化
-
范围估算错误：未预留足够空间导致溢出
-
线程安全问题：多线程操作需加锁或使用线程本地存储
-
位运算错误：位移操作符优先级陷阱（需加括号）
-
内存对齐优化：按CPU缓存行对齐提升访问速度
LeetCode真题训练：
-
217. 存在重复元素
-
268. 丢失的数字
-
442. 数组中重复的数据