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

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

一、位图核心思想

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

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

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

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

适用场景：

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

• 快速存在性检查

• 数据排序与范围查询

与布隆过滤器的对比：

二、位图实现原理

1. 存储结构

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

• 索引计算：

  • 数组下标：index = num / 32

  • 位偏移：offset = num % 32

2. 核心操作

三、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-127
    string res;
    for (char c : s) {
        if (!bm.contains(c)) {
            res += c;
            bm.add(c);
        }
    }
    return res;
}

五、位图优化技巧

六、大厂真题实战

真题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. 数组中重复的数据