城乡建设部网站稽查执法专栏,家居网站 模板,阿里巴巴组织调整,重庆万州网站建设多少钱bitset的介绍
位图的引入
给40亿个不重复的无符号整数#xff0c;没排过序。给一个无符号整数#xff0c;如何快速判断一个数是否在这40亿个数中#xff1f;
要判断一个数是否在某一堆数中#xff0c;我们可能会想到如下方法#xff1a;
将这一堆数进行排序#xff0…bitset的介绍
位图的引入
给40亿个不重复的无符号整数没排过序。给一个无符号整数如何快速判断一个数是否在这40亿个数中
要判断一个数是否在某一堆数中我们可能会想到如下方法
将这一堆数进行排序然后通过二分查找的方法判断该数是否在这一堆数中。将这一堆数插入到unordered_set容器中然后调用find函数判断该数是否在这一堆数中。
单从方法上来看这两种方法都是可以而且效率也不错第一种方法的时间复杂度是O(N*LogN)第二种方法的时间复杂度是O(N)。
但问题是这里有40亿个数若是我们要将这些数全部加载到内存当中那么将会占用16G的空间空间消耗是很大的。因此从空间消耗来看上面这两种方法实际都是不可行的。
位图解决
实际在这个问题当中我们只需要判断一个数在或是不在即只有两种状态那么我们可以用一个比特位来表示数据是否存在如果比特位为1则表示存在比特位为0则表示不存在。比如 无符号整数总共有2的32次方个因此记录这些数字就需要2的32次方个比特位也就是512M的内存空间内存消耗大大减少。
位图的概念
所谓位图就是用每一位来存放某种状态适用于海量数据数据无重复的场景。通常是用来判断某个数据存不存在的。
位图的应用
常见位图的应用如下
快速查找某个数据是否在一个集合中。排序。求两个集合的交集、并集等。操作系统中磁盘块标记。内核中信号标志位信号屏蔽字和未决信号集。
bitset的使用
bitset是一种特殊的容器类它的每个元素只占用一位只能为0或1。
bitset的定义方式
创建bitset对象你可以直接指定它的大小或者使用一个无符号长整型数或字符串初始化它
方式一 构造一个16位的位图所有位都初始化为0。
bitset16 bs1; //0000000000000000方式二 构造一个16位的位图根据所给值初始化位图的前n位。
bitset16 bs2(0xfa5); //0000111110100101方式三 构造一个16位的位图根据字符串中的0/1序列初始化位图的前n位。
bitset16 bs3(string(10111001)); //0000000010111001bitset成员函数的使用
bitset类提供了以下一些常用的成员函数
set将bitset中的一位或所有位设置为1reset将bitset中的一位或所有位设置为0flip翻转bitset中的一位或所有位test获取指定位的状态count返回bitset中1的个数size返回bitset中位的个数any如果bitset中至少有一位为1则返回truenone如果bitset中所有位都为0则返回trueall如果所有位都被设置则返回trueto_string将bitset转换为字符串to_ulong 或 to_ullong将bitset转换为无符号(长)整型数
使用示例
#include bitset
#include iostream
using namespace std;int main() {bitset8 bs;//位置从0开始bs.set(2); //设置第2位bs.set(4); //设置第4位cout bs endl;//00010100bs.flip(); //反转所有位cout bs endl; //11101011cout bs.count() endl;//6cout bs.test(3) endl;//1 3的位置为1bs.reset(0); //清空第0位,第0位变成了0cout bs endl;//11101010bs.flip(7); //反转第7位cout bs endl;//01101010cout bs.size() endl;//8cout bs.any() endl;//任何位为1就返回true 1bs.reset(); //清空所有位cout bs.none() endl;//没有位被设置就返回true 1bs.set(); //设置所有位cout bs.all() endl;//所有位被设置返回true 1return 0;
}22211注意 使用成员函数set、reset、flip时若指定了某一位则操作该位若未指定位则操作所有位。
bitset运算符的使用
一、bitset中、运算符的使用。 bitset容器对、运算符进行了重载我们可以直接使用、运算符对biset容器定义出来的对象进行输入输出操作。
#include iostream
#include bitset
using namespace std;int main() {bitset8 bs;cin bs; //10110cout bs endl;//00010110return 0;
}二、bitset中赋值运算符、关系运算符、复合赋值运算符、单目运算符的使用。
bitset容器中不仅对赋值运算符和一些关系运算符进行了重载而且对一些复合赋值运算符和单目运算符也进行了重载我们可以直接使用这些运算符对各个位图进行操作。
包括如下运算符
赋值运算符。关系运算符、!。复合赋值运算符、|、^、、。单目运算符~。
三、bitset中位运算符的使用。 bitset容器中同时也对三个位运算符进行了重载我们可以直接使用、|、^对各个位图进行操作。
#include bitset
#include iostream
#include string
using namespace std;int main() {bitset8 bs1(string(10101010));bitset8 bs2(string(01010101));cout (bs1 bs2) endl;//00000000cout (bs1 | bs2) endl;//11111111cout (bs1 ^ bs2) endl;//11111111return 0;
}四、bitset中[ ]运算符的使用。 bitset容器中对[ ]运算符进行了重载我们可以直接使用[ ]对指定位进行访问或修改。
#include bitset
#include iostream
#include string
using namespace std;int main() {bitset8 bs(string(00110101));cout bs[0] endl;//1bs[0] 0;cout bs endl;//00110100return 0;
}bitset的模拟实现
bit类各函数接口总览
namespace cl {//模拟实现位图templatesize_t Nclass bitset {public://构造函数bitset();//设置位void set(size_t pos);//清空位void reset(size_t pos);//反转位void flip(size_t pos);//获取位的状态bool test(size_t pos);//获取可以容纳的位的个数size_t size();//获取被设置位的个数size_t count();//判断位图中是否有位被设置bool any();//判断位图中是否全部位都没有被设置bool none();//判断位图中是否全部位都被设置bool all();//打印函数void Print();private:vectorint _bits;//位图};
}// namespace clbitset类的实现
构造函数
在构造位图时我们需要根据所给位数N创建一个N位的位图并且将该位图中的所有位都初始化为0。
一个整型有32个比特位因此N个位的位图就需要用到N/32个整型但是实际我们所需的整型个数是N/321因为所给非类型模板参数N的值可能并不是32的整数倍。
例如当N为40时我们需要用到两个整型即40/3212。 代码如下
//构造函数
bitset(){_bits.resize(N / 32 1, 0);
}成员函数
set
set成员函数用于设置位。
设置位图中指定的位的方法如下 计算出该位位于第 i 个整数的第 j 个比特位。 将1左移 j 位后与第 i 个整数进行或运算即可。
代码如下
//设置位
void set(size_t pos){assert(pos N);//算出pos映射的位在第i个整数的第j个位int i pos / 32;int j pos % 32;_bits[i] | (1 j); //将该位设置为1不影响其他位
}reset
reset成员函数用于清空位。
清空位图中指定的位的方法如下
计算出该位位于第 i 个整数的第 j 个比特位。将1左移 j 位再整体反转后与第 i 个整数进行与运算即可。 代码如下
//清空位
void reset(size_t pos){assert(pos N);//算出pos映射的位在第i个整数的第j个位int i pos / 32;int j pos % 32;_bits[i] (~(1 j)); //将该位设置为0不影响其他位1进行翻转后只有第j位置位0 其他都是1所以只会影响第j位置的数字
}flip
flip成员函数用于反转位。
反转位图中指定的位的方法如下
计算出该位位于第 i 个整数的第 j 个比特位。将1左移 j 位后与第 i 个整数进行异或运算即可。 代码如下
//反转位
void flip(size_t pos){assert(pos N);//算出pos映射的位在第i个整数的第j个位int i pos / 32;int j pos % 32;_bits[i] ^ (1 j); //将该进行反转不影响其他位
}test
test成员函数用于获取位的状态。
获取位图中指定的位的状态的方法如下
计算出该位位于第 i 个整数的第 j 个比特位。将1左移 j 位后与第 i 个整数进行与运算得出结果。若结果非0则该位被设置否则该位未被设置。 代码如下
//获取位的状态
bool test(size_t pos){assert(pos N);//算出pos映射的位在第i个整数的第j个位int i pos / 32;int j pos % 32;//该比特位被设置if (_bits[i] (1 j)){return true;} else {//该比特位未被设置return false;}
}size、count
size成员函数用于获取位图中可以容纳的位的个数。
我们直接将所给非类型模板参数进行返回即可。
//获取可以容纳的位的个数
size_t size(){return N;
}count成员函数用于获取位图中被设置的位的个数。
获取位图中被设置的位的个数也就是统计位图中1的个数我们只需要依次统计每个整数二进制中1的个数然后将其相加即可得到位图中1的个数。
统计二进制中1的个数的方法如下
将原数n与n - 1进行与运算得到新的 n 。判断n是否为0若 n 不为0则继续进行第一步。
如此进行下去直到n最终为0此时该操作进行了几次就说明二进制中有多少个1。
因为该操作每进行一次就会消去二进制中最右边的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的个数即被设置位的个数
}any、none、all any成员函数用于判断位图中是否有位被设置。 我们只需遍历每一个整数若这些整数全部都为0则说明位图中没有位被设置过。 虽然位图可能并没有包含最后一个整数的全部比特位但由于我们构造位图时是将整数的全部比特位都初始化成了0因此不会对此处判断造成影响。 代码如下
//判断位图中是否有位被设置
bool any(){//遍历每个整数for (auto e : _bits){//该整数中有位被设置if (e ! 0) {return true;} }return false; //全部整数都是0则没有位被设置过
}none成员函数用于判断位图中是否全部位都没有被设置。 位图中是否全部位都没有被设置实际上就是位图中有位被设置的反面因此none成员函数直接调用any成员函数然后将返回值取反后再进行返回即可。
//判断位图中是否全部位都没有被设置
bool none() {return !any();
}all成员函数用于判断位图中是否全部位都被设置。 判断过程分为两步
先检查前n-1个整数的二进制是否为全1。再检查最后一个整数的前N%32个比特位是否为全1。
需要注意的是如果位图没有包含最后一个整数的全部比特位那么最后一个整数的二进制无论如何都不会为全1所以在判断最后一个整数时应该只判断位图所包含的比特位。 代码如下
//判断位图中是否全部位都被设置
bool all() {size_t n _bits.size();//先检查前n-1个整数for (size_t i 0; i n - 1; i) {//取反后不为全0说明取反前不为全1if (~_bits[i] ! 0){return false;}}//再检查最后一个整数的前N%32位for (size_t j 0; j N % 32; j) {//等于0表示没有被设置if ((_bits[n - 1] (1 j)) 0){return false;}}return true;
}打印函数
可以实现一个打印函数便于检查我们上述代码的正确性打印位图时遍历位图所包含的比特位进行打印即可在打印位图的过程中可以顺便统计位图中位的个数count将count与我们传入的非类型模板参数N进行比较可以判断位图大小是否是符合我们的预期。
//打印函数
void Print() {int count 0;size_t n _bits.size();//先打印前n-1个整数for (size_t i 0; i n - 1; i) {for (size_t j 0; j 32; j) {if (_bits[i] (1 j)) {cout 1;} else {cout 0;}count;}}//再打印最后一个整数的前N%32位for (size_t j 0; j N % 32; j) {if (_bits[n - 1] (1 j)){cout 1;}else{cout 0;}count;}cout count endl;//打印总共打印的位的个数
}
