位图的介绍和模拟实现

@TOC

位图的介绍

经典面试题：

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。

常用方法有：

1.先排序，在利用二分查找

2.将数据放到unorder_set中，利用find进行查找，判断是否在这些数中

方法1的时间复杂度：排序O(NlogN),二分查找O(logN)

方法2的时间复杂度：O(N)

这2个方法都还可以，但是40亿个无符号整数会占用内存约16GB，空间消耗非常的大，所以上面的2种方法就不行了。

那么用位图来解决

数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比

特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。

例如：

无符号整数是2^32个字节，也就是521MB的大小，空间消耗变得很小了。

位图概念

位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个

数据存不存在的。

位图的应用

快速查找某个数据是否在一个集合中

排序

求两个集合的交集、并集等

操作系统中磁盘块标记

位图使用

位图的定义

方式一：构造1个16位的位图，所有初始化位是0

bitset<16> foo;

方式二：构造1个16位的位图，根据所给值初始化前n位

bitset<16> bar(0xf);

方式三：构造1个16位的位图，根据字符串的0,1序列初始化

bitset<16> baz(string("1000001"));

打印出来的效果：

位图的成员函数

void Testbiset2() { bitset<16> baz; baz.set(8); baz.set(10); cout << baz << endl; baz.reset(8);//清空第8位 cout << baz << endl; baz.flip(8);//反转第8位 cout << baz << endl; cout << baz.size() << endl; cout << baz.any() << endl; cout << baz.none() << endl; cout << baz.all() << endl; }

位图运算符的使用

1.bitset中对>>,<<重载过可以直接使用

bitset<8> baz; cin >> baz; cout << baz << endl;

2.对一些运算符的重载

赋值运算符：=

关系运算符：==、!=

复合赋值运算符：&=、|=、^=、<<=、>>=

单目运算符：~

bitset<4> foo(std::string("1001")); bitset<4> bar(std::string("0011")); cout << (foo ^= bar) << endl; // 1010 cout << (foo &= bar) << endl; // 0010 cout << (foo |= bar) << endl; // 0011 cout << (foo <<= 2) << endl; // 1100 cout << (foo >>= 1) << endl; // 0110 cout << (~bar) << endl; // 1100 cout << (bar << 1) << endl; // 0110 cout << (bar >> 1) << endl; // 0001 cout << (foo == bar) << endl; // false cout << (foo != bar) << endl; // true cout << (foo & bar) << endl; // 0010 cout << (foo | bar) << endl; // 0111 cout << (foo ^ bar) << endl; // 0101

3.opeartor[],直接对某位进行修改或访问

bitset<4> bar; bar[1] = 1; bar[2] = bar[1]; cout << bar << endl;

位图的模拟实现

构造函数

我们需要根据所给的N来构造N位的位图，并且将位图中的所有位初始化位0

1个整形是32个比特位，N位的位图就是N/32，但是N可能不是32的整数倍还需要+1。

bitset() { _bits.resiez(N / 32 + 1,0); }

set、reset、filp

set设置位

设置位图中指定位的方法：

1.计算出是第i个数的第j位

2.将1左移j位后和第i个位进行或运算

代码如下：

void set(size_t pos) { assert(pos < N); //计算pos映射在第几个数的多少位 int i = pos / 32; int j = pos % 32; _bits[j] |= (1 << j);//将该位置设为1 }

reset清空位

清空位图中指定位的方法：

1.计算出是第i个数的第j位

2.将1左移j位再整体取反与第i个数相与

代码如下：

void reset(size_t pos) { assert(pos < N); //计算pos映射在第几个数的多少位 int i = pos / 32; int j = pos % 32; _bits[j] &= (~(1 << j));//左移取反在相与 }

filp反转指定位

1.计算出是第i个数的第j位

2.将1左移j位后和第i个位进行异或运算

void filp(size_t pos) { assert(pos < N); int i = pos / 32; int j = pos % 32; _bits[j] ^= (1 << j);//左移在取反 }

size、count

size直接返回N即可

size_t size() { return N; }

count获取位图中设置位的个数

逻辑如下：

1.将原数n与n-1与运算得到新数n

2.判断n是否为0，不为0继续进行第1步

size_t count() { size_t count = 0; //将每个整数中1的个数累加起来 for (auto e : _bits) { int num = e; //计算整数num中1的个数 while (num) { num = num & (num - 1); count++; } } return count; //位图中1的个数，即被设置位的个数 }

其他的接口博主就没有实现，主要都是位运算的操作。

数据结构

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。