位图
原理
用bit组成的数组来存放值，用bit状态1、0代表存在、不存在，取值和存值操作都用位运算。
限制是必须为连续范围且不能过大。好处是极大的节省空间，因为1个数字只占用1个bit的空间。
常用操作
对位图内元素的操作
- 增：set(num) // 把num加入到位图
- 删：reset(num) // 把num从位图中删除
- 改：flip(num) // 取反num的bit位置
- 查：test(num) // 查询num是否在位图中
位图之间的操作
- 交：
& // 按位与
- 并：
| // 按位或
- 异或：
^ // 按位异或
- 取反：
flip() // 按位取反
- 统计：
count() // 统计1的个数
- 交换：
swap() // 交换两个位图
- 字符串：
to_string() // 转化为字符串
实现
此处使用vector<int>来模拟位图，每个int表示32位，用&、|和^操作来操作位。
创建
初始化位图的大小，默认所有位都为0。只支持
1
2
| vector<int> set((n + 31) / 32); // n位的位图（向上取整得到int数组的个数）
bitset<n> a; // n位的位图
|
增加(set)
1
2
| set[num / 32] |= (1 << (num % 32)); // 把num的bit位置为1
a.set(num); // 将num加入位图
|
删除(reset)
1
2
| set[num / 32] &= ~(1 << (num % 32)); // 把num的bit位置为0
a.reset(num); // 从位图中删除num
|
修改(flip)
1
2
| set[num / 32] ^= (1 << (num % 32)); // 取反num的bit位置
a.flip(num); // 取反num
|
查询(test)
1
2
3
4
| if(set[num / 32] & (1 << (num % 32))) // 第num位是否为1
cout << num << "存在" << endl;
if(a.test(num)) // num是否在位图中
cout << num << "存在" << endl;
|
运算
1
2
3
4
| bitset<10> b(a); // 复制位图
bitset<10> c = a & b; // 位与
bitset<10> d = a | b; // 位或
bitset<10> e = a ^ b; // 位异或
|
遍历
1
2
3
4
5
6
7
8
| for(int i = 0; i < n; i++){ // 遍历位图
// 输出第i位
cout << set[i / 32] & (1 << i % 32) << " ";
}
for(int i = 0; i < a.size(); i++){
cout << a[i] << " ";
}
|
统计
1
2
| bitset<10> g(a); // 复制位图
int count = g.count(); // 统计1的个数
|
交换
其他
1
2
3
| bitset<10> j(a); // 复制位图
j.flip(); // 按位反转位图
j.to_string(); // 转化为字符串
|
