位图
核心概念与实现
在面试或实际工程中,常遇到海量数据查询场景。例如:给定 40 亿个不重复的无符号整数,如何快速判断一个数是否存在?
暴力遍历 O(N) 太慢,排序加二分查找 O(NlogN) 内存又不够。既然结果只有'存在'或'不存在'两种状态,我们可以用二进制的一位来代表这个信息:1 表示存在,0 表示不存在。这就是位图(BitMap)。
位图本质上是一种直接定址法的哈希表,每个整型值映射到一个比特位。它主要提供 set、reset、test 三个接口。
namespace lydly {
template<size_t N>
class BitMap {
public:
BitMap() {
// 一个 int 有 32 位,+1 为了向上取整,初始全用 0 填充
_bits.resize(N / 32 + 1, 0);
}
void Set(size_t x) {
// i 找这个数在第几个 int
// j 找这个数在这个 int 中的第几个位
// 利用或运算将这一位设为 1,不改变其他位
size_t i = x / 32;
size_t j = x % 32;
_bits[i] |= (1 << j);
}
void Reset(size_t x) {
// i 找这个数在第几个 int
// j 找这个数在这个 int 中的第几个位
// 利用且运算将这一位设为 0,不改变其他位
size_t i = x / 32;
size_t j = x % 32;
_bits[i] &= ~(1 << j);
}
bool Test( x) {
i = x / ;
j = x % ;
_bits[i] & ( << j);
}
:
std::vector<> _bits;
};
}


