目录
一、位图概念
1.使用场景?
假如给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中？
计算一下40亿个无符号整数会占多大内存呢？
可以采用如下方法：
（1）放进set或unordered_set中，再用find进行查找
（2）排序，再使用二分法查找，排序的时间复杂度是O(N*logN)，二分查找的时间复杂度是O(logN)
但是，16GB的大小，这会很消耗内存，我们不可能把16GB的数据全部加载到内存中。还有另外一种比较节省内存的方式——位图。
2.位图
一个bit位代表一个整数在不在，因此现在一个整数大小（4个字节32位）可以表示32个整数在不在，那么对于第一小节的40亿个整数16GB就可以用500MB进行表示了，500MB是可以加载到内存中的，这也提高了效率。
二、位图介绍
1.构造
?有3种构造方式：分为默认0、整数、字符串3种类型
bitset();//默认
bitset (unsigned long val);//参数传整数，10进制或16进制都可以
template<class charT, class traits, class Alloc> explicit bitset (const basic_string<charT,traits,Alloc>& str, typename basic_string<charT,traits,Alloc>::size_type pos = 0, typename basic_string<charT,traits,Alloc>::size_type n = basic_string<charT,traits,Alloc>::npos);//字符串
用3种构造方式构造3个位图对象：
#include<iostream>
#include<string>
#include<bitset>
using namespace std;
int main()
{
bitset<16> bs1;
bitset<16> bs2(125);
bitset<32> bs3("101000101010");
cout << "bs1:" << bs1 << endl;
cout << "bs2:" << bs2 << endl;
cout << "bs3:" << bs3 << endl;
return 0;
}打印结果如下：?
2.operator[ ]
返回下标位置的值：?
bool operator[] (size_t pos) const;reference operator[] (size_t pos);?修改bs1第3位和第6位的值：
bs1[3] = 1;
bs1[6] = 1;
cout << "bs1:" << bs1 << endl;
3.count( )
返回位图对象中1的个数：
size_t count() const;?返回bs3中1的个数：
cout << bs3.count() << endl;
4.size( )
返回该位图对象的位数：?
size_t size() const;?返回bs1、bs2、bs3的位数：
cout << "bs1:" << bs1.size() << endl;
cout << "bs2:" << bs2.size() << endl;
cout << "bs3:" << bs3.size() << endl;
5.test( )
返回该位在不在：
bool test (size_t pos) const;返回bs2的每一位在不在：?
cout << boolalpha;//把布尔值打印成true或false
for (size_t i = 0; i < bs2.size(); i++)
{
cout << bs2.test(i) << endl;
}?
6.any( )
是否有至少1位为1：?
bool any() const;?判断bs3是否至少有1位为1：
if (bs3.any())
{
cout << "bs3至少有1位为1" << endl;
}
else
{
cout << "bs3没有1位为1" << endl;
}?
7.none( )
是否全为0：?
bool none() const;判断bs3是否全为0：?
if (bs3.none())
{
cout << "bs3全为0" << endl;
}
else
{
cout << "bs3不全为0" << endl;
}
?
8.all( )
是否所有位都为1：?
bool all() const noexcept;?判断bs3是否全为1：
if (bs3.all())
{
cout << "bs3全为1" << endl;
}
else
{
cout << "bs3不全为1" << endl;
}
9.set( )
标记分以下两种：?
bitset& set();//每个bit位都标记为1
bitset& set (size_t pos, bool val = true);//把第pos位标记为val将bs4全标记为1 ，再将第6位标记为0，再将第6为标记为1：
bitset<16> bs4;
bs4.set();
cout << bs4 << endl;
bs4.set(6,0);
cout << bs4 << endl;
bs4.set(6, 1);
cout << bs4 << endl;?
10.reset( )
删除分为以下两种：
bitset& reset();//删除所有位，每一位都置为0
bitset& reset (size_t pos);//删除指定pos位，置为0先删除bs5的第2位的标记?，再删除所有位的标记：
bitset<16> bs5(0xFFFF);
cout << bs5 << endl;
bs5.reset(2);
cout << bs5 << endl;
bs5.reset();
cout << bs5 << endl;?
11.flip( )
取反分为以下两种：
bitset& flip();//全部取反
bitset& flip (size_t pos);//把第pos位取反先对bs5的第2位取反，再对bs5全部取反：?
bitset<16> bs5(0xFFFF);
cout << bs5 << endl;
bs5.flip(2);
cout << bs5 << endl;
bs5.flip();
cout << bs5 << endl;?
三、位图实现
1.位图定义
位图只需要定义一个成员_bits即可，表明传入的数据个数：
#pragma once
#include<assert.h>
namespace delia
{
template<size_t N>//数据总数
class BitSet
{
private:
vector<int> _bits;
};
}2.构造
1个字节可以表示32个数在不在，因此只需要申请N/32+1个空间，向上取整
public:
BitSet()
{
_bits.resize(N/32+1,0)//向上取整，否则不够存，默认每一位标记为0
}3.标记
只把该位置1，其他位都不变：
①计算x在位图中的第几个整数的第几个位置
②要把该位置1，就必须让该位和1按位或，且其他位都不能被改变
//标记
void Set(size_t x)
{
assert(x < N);
//计算x映射的位在第i个整数
//计算x映射的位在这个整数的第j位
size_t i = x / 32;
size_t j = x % 32;
//_bits[i]的第j位标记为1，并且不影响其他位
_bits[i] |= (1 << j);
}4.删除
只把该位置0，其他位都不变：
①计算x在位图中的第几个整数的第几个位置
②要把该位置0，就必须让该位和0按位与，且其他位都不能被改变
③把1左移j位再按位取反，就可以将该位置为0。
//删除
void Reset(size_t x)
{
assert(x < N);
//计算x映射的位在第i个整数
//计算x映射的位在这个整数的第j位
size_t i = x / 32;
size_t j = x % 32;
//_bits[i]的第j位标记为0，并且不影响其他位，
_bits[i] &= (~(1 << j));
}5.检验在不在
①计算x在位图中的第几个整数的第几个位置
②返回该位和1左移j位置后相与的结果
//检验在不在
void Test(size_t x)
{
assert(x < N);
//计算x映射的位在第i个整数
//计算x映射的位在这个整数的第j位
size_t i = x / 32;
size_t j = x % 32;
//如果第j位为1，结果是非0，非0为真
//如果第j位为0，结果是0，0为假
return _bits[i] & (1 << j);
}6.完整代码段
#pragma once
#include<assert.h>
#include<vector>
using namespace std;
namespace delia
{
template<size_t N>
class BitSet
{
public:
BitSet()
{
_bits.resize(N/32+1,0)//向上取整，否则不够存，默认每一位标记为0
}
//标记
void Set(size_t x)
{
assert(x < N);
//计算x映射的位在第i个整数
//计算x映射的位在这个整数的第j位
size_t i = x / 32;
size_t j = x % 32;
//_bits[i]的第j位标记为1，并且不影响其他位
_bits[i] |= (1 << j);
}
//删除
void Reset(size_t x)
{
assert(x < N);
//计算x映射的位在第i个整数
//计算x映射的位在这个整数的第j位
size_t i = x / 32;
size_t j = x % 32;
//_bits[i]的第j位标记为0，并且不影响其他位，
_bits[i] &= (~(1 << j));
}
//检验在不在
void Test(size_t x)
{
assert(x < N);
//计算x映射的位在第i个整数
//计算x映射的位在这个整数的第j位
size_t i = x / 32;
size_t j = x % 32;
//如果第j位为1，结果是非0，非0为真
//如果第j位为0，结果是0，0为假
return _bits[i] & (1 << j);
}
private:
vector<int> _bits;
};
void test_BitSet()
{
BitSet<4294967295u>* bs=new BitSet<4294967295u>;//40亿个数据向上取整，即开辟2^32个bit位
}
}四、位图应用
1.给定两个文件，这两个文件分别都有100亿个整数，现在只有1G内存，如何找两个文件交集？
方案（1）：依次读取第一个文件中的所有整数并标记映射到一个位图，再读取第二个文件中的所有整数，判断在不在位图，在就是交集中的书，不在就不是
方案（2）：依次读取第一个文件的所有证书标记映射为位图1，一次读取第二个文件的所有证书标记映射为位图2，再对两个位图进行相与，结果为1的位就是交集。
无论方案（1）还是方案（2），由于整数最多只有2^32=4294967295个，42亿多个，文件有100亿个数据，肯定有重复的，因此只需要开辟2^32个bit位就能覆盖到这100亿个数据。
2.给定100亿个整数，设计算法找到只出现一次的整数
方案：位图是一个bit位标记一个值，现在用两个bit位标记一个值，位图能标记32个值在不在，那么现在只能标记16个值在不在：
00? ? 出现0次
01? ? 出现1次
10? ? 出现2次及以上
11? ? 不考虑
最后找出01标记的整数
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<assert.h>
#include<iostream>
#include<vector>
#include<bitset>
using namespace std;
int main()
{
vector<int> v = { 3,67,259,1,7890,4,36,23 };
bitset<4294967295u>* bs1 = new bitset<4294967295u>;
bitset<4294967295u>* bs2 = new bitset<4294967295u>;
for (auto e : v)
{
if (!bs1->test(e) && !bs2->test(e))//00->01，第一次出现
{
bs2->set(e);
}
else if (!bs1->test(e) && bs2->test(e))//01->10，第二次出现
{
bs1->set(e);
bs2->reset(e);
}
else if (bs1->test(e) && !bs2->test(e))//10->11，第三次出现
{
//不用处理
}
else//第四次出现
{
//不用处理
assert(false);
}
}
for (size_t i = 0; i < 4294967295; i++)
{
if (!bs1->test(i) && bs2->test(i))//找01
{
cout << i << endl;
}
}
return 0;
}3.? 1个文件有100亿个整数，1G内存，设计算法找到出现次数不超过2次的所有整数
现在用两个bit位标记一个值，?
00? ? 出现0次
01? ? 出现1次
10? ? 出现2次
11? ? 出现3次
最后找出01和10标记的，即出现1次和出现2次的整数
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<assert.h>
#include<iostream>
#include<vector>
#include<bitset>
using namespace std;
int main()
{
vector<int> v = { 3,67,259,1,7890,4,36,23 };
bitset<4294967295u>* bs1 = new bitset<4294967295u>;
bitset<4294967295u>* bs2 = new bitset<4294967295u>;
for (auto e : v)
{
if (!bs1->test(e) && !bs2->test(e))//00->01，第一次出现
{
bs2->set(e);
}
else if (!bs1->test(e) && bs2->test(e))//01->10，第二次出现
{
bs1->set(e);
bs2->reset(e);
}
else if (bs1->test(e) && !bs2->test(e))//10->11，第三次出现
{
bs1->set(e);
}
else//第四次出现
{
//不用处理
assert(false);
}
}
//找01或10
for (size_t i = 0; i < 4294967295; i++)
{
if ((!bs1->test(i) && bs2->test(i))
|| (bs1->test(i) && !bs2->test(i))
{
cout << i << endl;
}
}
return 0;
}