【C++】位图

        位图（Bitmap）是一种用于高效表示集合的数据结构，其核心思想是使用二进制位来指示某个元素是否存在。在位图中，每个元素对应一个二进制位，若该元素存在，则对应的位为1；若不存在，则为0。

        背景：假设有这样一个需求：在20亿个随机整数中找出某个数m是否存在其中，并假设32位操作系统，4G内存。

        C++中int占4个字节一个字节8个比特位。

如果每个数字用int存储，那就是20亿个int，因而占用的空间约为  (2000000000*4/1024/1024/1024)≈7.45G

如果按位存储就不一样了，20亿个数就是20亿位，占用空间约为  (2000000000/8/1024/1024/1024)≈0.233G

        问题：如何表示这一个数存不存在？

        每一位表示一个元素，标识为1表示存在，标识为0表示不存在。

        假如，我们存了10，20，30，40，48，那我们在位图中如何表示？

下面我就用从左到右依次增高的地址来表示：

既然是在位图中，我们使用常规的遍历肯定是不行的。

那该如何查找存不存在？？？？这里我们要先 

Element / 32  -->除32（int占32位）

Element%32  -->取模

这样我们就知道他位于哪个字节中的哪个位置了。因此可以判断是否存在。

既然了解了上面的知识，我们模拟一下C++中STL容器中的bitset吧。

	template<size_t N>class bit_set{public:bit_set(){_bs.resize(N / 32 + 1);}// x映射的位标记成1void set(size_t x){size_t i = x / 32;size_t j = x % 32;_bs[i] |= (1 << j);}// x映射的位标记成0void reset(size_t x){size_t i = x / 32;size_t j = x % 32;_bs[i] &= (~(1 << j));}// x映射的位是1返回真// x映射的位是0返回假bool test(size_t x){size_t i = x / 32;size_t j = x % 32;return _bs[i] & (1 << j);}private:std::vector<size_t> _bs;};

当我们设置一个数字进入位图里面，也就是我们要把相应的位图设置为1，同时又不能改变其他的位置标识。如何操作呢？这里我使用的是|。举个例子吧，下面这两个是位，我们进行按位或操作

0100 0 0000

0000 1 0000

结果就是

0100 1 0000

当我们要取消一个数字进入位图里面，也就是我们要把相应的位图设置为0，同时又不能改变其他的位置标识。如何操作呢？这里我使用的是&。举个例子

0100 1 1010

1111 0 1111

结果

0100 0 1010

优点：

位图（Bitmap）在单个元素的查找、插入、删除操作上的时间复杂度可以达到 O(1)。

快速排序：

假设我们要对0-7内的5个元素(4,7,2,5,3)排序（这里假设这些元素没有重复）,我们就可以采用Bit-map的方法来达到排序的目的。

要表示8个数，我们就只需要8个Bit（1字节），首先我们开辟1字节的空间，将这些空间的所有Bit位都置为0，然后将对应位置为1。

最后，遍历一遍Bit区域，将该位是一的位的编号输出（2，3，4，5，7），这样就达到了排序的目的，时间复杂度O(n)。

缺点：

只能用于整形。

---

        题目：1.给定100亿个数字，设计算法找到只出现一次的整数？

                    2.一个文件有100亿个整数，1G内存，设计算法找到出现次数不超过2的所有整数  

这里我们可以实现两个位图来实现一下。如果第一个位图为0第二个位图为1，说明出现了1一次，

如果第一个位图为1第二个位图为0，说明出现了2次，如果第一个位图为1第二个位图为1，说明出现了2次及以上。

	template<size_t N>class two_bit_set{public:void set(size_t x){bool bit1 = _bs1.test(x);bool bit2 = _bs2.test(x);if (!bit1 && !bit2) // 00 -> 01{_bs2.set(x);}else if (!bit1 && bit2) // 01->10{_bs1.set(x);_bs2.reset(x);}else if (bit1 && !bit2) // 10 -> 11{_bs1.set(x);_bs2.set(x);}}private:bit_set<N> _bs1;bit_set<N> _bs2;};