位图的应用
目录
问题引入
面试题
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在
这40亿个数中。【腾讯】
解决思路
1. 遍历，时间复杂度O(N)
2. 排序(O(NlogN))，利用二分查找: logN
3. 位图解决
数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一
个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0
代表不存在。比如：
位图概念
所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用
来判断某个数据存不存在的。
位图的实现
namespace bitset
{
template<size_t N>
class bitset
{
public:
bitset()
{
_bits.resize((N >> 5) + 1);//1 int = 32 bits
}
void set(size_t x)//将数据x的所映射的位置设置为1
{
size_t i = x / 32;
size_t j = x % 32;
_bits[i] |= (1 << j);
}
void reset(size_t x)//将数据x的所映射的位置设置为0
{
size_t i = x / 32;
size_t j = x % 32;
_bits[i] &= ~(1 << j);
}
bool test(size_t x) const//测试数据x的所映射的位置是否为1
{
size_t i = x / 32;
size_t j = x % 32;
return _bits[i] & (1 << j);
}
private:
vector<int> _bits;
};
}
开空间时，开所有整型的空间，一次把空间开够
可以是size_t -1，也可以用16进制
应用2：找到只出现一次的整数
给定100亿个整数，找到只出现一次的整数
我们设置两个bitset来控制出现的次数
00代表出现0次
01代表出现1次
10代表出现两次及以上
template<size_t N>
class twobitset
{
public:
void set(size_t x)
{
if (_bit1.test(x) == false && _bit2.test(x) == false)//00->01
_bit2.set(x);
else if (_bit1.test(x) == false && _bit2.test(x) == true)//01->10
{
_bit1.set(x);
_bit2.reset(x);
}
else if (_bit1.test(x) == true && _bit2.test(x) == false)//10->11
{
_bit2.set(x);
}
}
void print()
{
for (size_t i = 0; i < N; i++)
{
if (_bit1.test(i) == false && _bit2.test(i) == true)//01
cout << i << " ";
}
cout << endl;
}
private:
bitset<N> _bit1;//自动调用该类的构造函数
bitset<N> _bit2;
};虽然是100亿，但是只需要开 size_t -1就可以，因为数据重复（整数的范围就这些）
应用三：找交集
给你两个文件，分别有100亿个整数，只有1G内存，如何找到两个文件的交集
解决：将数据分别映射到两个位图，如果test之后都为true，那么就是交集
位图的应用
1. 快速查找某个数据是否在一个集合中
2. 排序 + 去重
3. 求两个集合的交集、并集等
4. 操作系统中磁盘块标记
STL中的位图
C++的bitset数据并不是每一位都占用一个字节，而是通过优化使得每个位只占用1 bit的空间。（这是STL中的标准吗？）
是的，这是C++标准库中bitset的设计原则。bitset是一种专门用于处理位操作的数据结构，它通过将多个位压缩到一个字节中来实现空间优化。每个元素只占用1 bit的空间，而不是传统的bool类型通常占用的1字节空间。
这种设计使得bitset在处理大量二进制数据时非常高效，因为它减少了内存消耗并提高了访问速度。由于bitset直接操作位级别，而非字节级别，因此它可以提供更快的位操作性能。
需要注意的是，虽然bitset本身的大小不是固定的，但它的元素大小始终为1 bit。这意味着无论bitset的大小如何，每个元素的存储空间都是相同的。
缺陷：只能处理整型（数据需要/ %）
原文地址：https://blog.csdn.net/2302_80190394/article/details/142741443
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！