文章目录
我们如果要查看100亿个数中某个数是否存在是完全不合理的,内存根本存放不下这么多的数,会爆炸
这样我们就可以用一个bit位来代表一个数
例如一个字节8个bit位,其中如果第2位被设置成1,说明2,这个数存在
这个也是一种映射关系
但是位图只能处理整数,这个就是它最大的问题
bit_set的模拟实现
- bitset里面的成员对象我们设置为vector里面是char,可以对里面的比特位进行操作
- 通过计算在第几个char中第几个位里面
- 运用位运算来进行置1,或置0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
| #include <vector> #include "HashTable.hpp" using namespace std; #include<bitset> template <size_t N> class bit_set { private: vector<char> _bits; public: bit_set() { _bits.resize(N / 8 + 1, 0); } void set(size_t x) { size_t i = x / 8; int j = x % 8; _bits[i] |= (1 << j); } void reset(size_t x) { size_t i = x / 8; int j = x % 8; _bits[i] &= (~(1 << j)); } bool find(size_t x) { size_t i = x / 8; int j = x % 8; return (bool)_bits[i] & (~(1 << j)); } };
|
位图的应用
- 给定100亿个数,设计算法,找到只出现一次的整数
思路我们可以使用两个位图,组成00,01,10,11序列
我们只要用这个判断出现的是01即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
| template<size_t N> class twobit { private: bit_set<N> bts1; bit_set<N> bts2;
public: void Set(size_t x) { if(!bts1.find(x)&&!bts2.find(x)) { bts2.set(x); } else if (!bts1.find(x)&&bts2.find(x)) { bts2.reset(x); bts1.set(x); } else { bts2.set(x); bts1.reset(x); } } void PrintOnceNum() { for(size_t i=0;i<N;i++) { if(!bts1.find(i)&&bts2.find(i)) { cout<<i<<endl; } } }
};
|
- 给两个文件,分别由100亿个整数,我们只有1G内存,如何找到两个文件的交集
- 法1:一个文件中的整数,set到一个位图,读取第二个整数是否在一个位图,在就有,不在就没有交集,这个就要用O(N),交集中,会把重复值找出来,多次出现
- 法2:思路2,读取一个整数设计到位图bs1,再把另一个文件中的整数,set到位图bs2,a.把bs1中的值,一次和bs2中的值进行与一下,再去看,与完是1的位置的值,就是交集,全1是1
- 一个文件中100亿个int,1g内存,找到出现次数不超过2次的整数,
这个方法的思路和上面只出现一次的思路很相似
但是这次是用3个bit位进行操作