位图（Bitmap）是一种使用二进制位（bit）来存储数据状态的结构，常用于大规模数据去重、状态标记、高效存储等场景。

🧠 1. 什么是位图？

位图是一种紧凑的数组结构，用 0/1 表示某个状态是否存在，占用空间非常小，适合存储布尔状态或整数集合。

比如要表示 0 ~ 15 的数字是否存在：

原始数组：[0, 1, 3, 7]
位图表示：10001001 00000001 （高位在左）
           ↑   ↑     ↑    ↑
           0   1     3    7

🧮 2. 基本原理

2.1 结构定义

位图是一种 bit 数组，通常使用整数类型来表示一组 bit：
- 1 个字节（Byte） = 8 个 bit
- 1 个 int（32 位系统） = 32 个 bit

2.2 空间计算

要表示 N 个非负整数，需要的内存大小为：

内存大小 = N / 8 字节（byte）

举例：如果要表示 1 亿个数字（最多 1e8 个），需要约：
1e8 / 8 = 12.5 MB

⚙️ 3. 位图的操作

3.1 设置某位为 1（标记存在）

bitmap[index / 8] |= (1 << (index % 8));

3.2 清除某位为 0（标记不存在）

bitmap[index / 8] &= ~(1 << (index % 8));

3.3 判断某位是否为 1（是否存在）

if (bitmap[index / 8] & (1 << (index % 8))) {
    // 存在
}

🛠️ 4. 示例代码（C语言）

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

#define MAX_NUM 100000000

unsigned char *bitmap;

void setBit(int num) {
    bitmap[num / 8] |= (1 << (num % 8));
}

void clearBit(int num) {
    bitmap[num / 8] &= ~(1 << (num % 8));
}

int testBit(int num) {
    return bitmap[num / 8] & (1 << (num % 8));
}

int main() {
    bitmap = (unsigned char *)calloc(MAX_NUM / 8 + 1, sizeof(unsigned char));

    setBit(123);
    setBit(99999);

    if (testBit(123)) {
        printf("123 exists\n");
    }

    if (!testBit(88888)) {
        printf("88888 does not exist\n");
    }

    free(bitmap);
    return 0;
}

📦 5. 位图的应用场景

- 去重（大数据判重）
- 排序（外排序的替代方案）
- Bloom Filter 的底层实现
- 状态标记（如是否已访问）
- 离线数据标记、日志处理
- 网络流量记录

⚖️ 6. 优点与缺点

✅ 优点

- 空间效率高：bit 级别控制
- 时间复杂度 O(1)：插入、查询、删除都很快

❌ 缺点

- 只能用于非负整数
- 无法存储复杂结构
- 存在稀疏浪费问题（若数据集中但范围大）

📚 7. 相关拓展

布隆过滤器（Bloom Filter）
通过多个位图和多个哈希函数实现更高效的去重
压缩位图（Roaring Bitmap）
用于优化稀疏位图的存储问题
Java BitSet
Java 中的位图实现类

🧪 8. 位图 vs 哈希表

特性	位图（Bitmap）	哈希表（HashSet）
空间占用	极小	较大
时间复杂度	O(1)	O(1)
是否支持负数	否（需偏移）	是
是否支持泛型	否	是
最大支持数量	高（10 亿级）	中等（百万级）