位图通过位操作高效管理布尔状态，使用std::vector按位存储，支持set、reset、get操作，适用于去重、排序等场景，空间时间效率优于集合容器。
位图（Bitmap）是一种高效的数据结构，用来表示一组布尔值（0 或 1），常用于快速标记和查询某个元素是否存在。在 C++ 中，可以通过 std::vector
基本原理
位图的核心思想是：用一个 bit 来表示一个整数的状态（比如是否存在）。假设我们要管理 0 到 N-1 的整数，那么只需要 (N + 31) / 32 个 32 位整数（即 unsigned int）即可存储所有状态。
每个 bit 对应一个整数：
- bit[i] = 1 表示整数 i 存在
- bit[i] = 0 表示整数 i 不存在
通过位运算可以高效地进行设置、清除和查询操作。
立即学习“C++免费学习笔记（深入）”；
关键位操作
要实现位图，需要掌握三个基本操作：
- 确定所在整数位置：index / 32 → index >> 5
- 确定在该整数中的 bit 位置：index % 32 → index & 0x1F
- 设置某一位为 1：bits[i >> 5] |= (1U
- 设置某一位为 0：bits[i >> 5] &= ~(1U
- 查询某一位是否为 1：(bits[i >> 5] & (1U
简单 Bitmap 类实现
#include#include class Bitmap { private: std::vector bits; size_t size; public: // 构造函数：指定最大处理的数值范围 [0, n) Bitmap(size_t n) : size(n) { bits.resize((n + 31) / 32, 0); } // 设置第 i 个位为 1 void set(size_t i) { if (i >= size) return; bits[i >> 5] |= (1U << (i & 0x1F)); } // 将第 i 个位清零 void reset(size_t i) { if (i >= size) return; bits[i >> 5] &= ~(1U << (i & 0x1F)); } // 查询第 i 个位是否为 1 bool get(size_t i) const { if (i >= size) return false; return (bits[i >> 5] & (1U << (i & 0x1F))) != 0; } // 打印前 n 个位的状态（用于调试） void print(size_t n) { for (size_t i = 0; i < n && i < size; ++i) { std::cout << get(i); } std::cout << std::endl; } };
使用示例
int main() {
Bitmap bm(64); // 支持 0~63
bm.set(10);
bm.set(20);
bm.set(31);
std::cout << "位状态: ";
bm.print(32); // 输出前32位
std::cout << "get(10): " << bm.get(10) << std::endl; // 1
std::cout << "get(15): " << bm.get(15) << std::endl; // 0
bm.reset(10);
std::cout << "reset 后 get(10): " << bm.get(10) << std::endl; // 0
return 0;
}
这个简单的位图适用于去重、排序（如计数排序变种）、布隆过滤器底层等场景。相比直接使用 std::set 或 std::unordered_set，位图在处理密集整数时空间和时间效率更高。
基本上就这些。理解位操作是关键，实际应用中还可以扩展支持更多功能，比如按位与/或、统计 1 的个数（popcount）等。不复杂但容易忽略边界检查和位运算细节。
