STL】bitset的模拟实现"/>
【STL】bitset的模拟实现
⭐博客主页:️CS semi主页
⭐欢迎关注:点赞收藏+留言
⭐系列专栏:C++进阶
⭐代码仓库:C++进阶
家人们更新不易,你们的点赞和关注对我而言十分重要,友友们麻烦多多点赞+关注,你们的支持是我创作最大的动力,欢迎友友们私信提问,家人们不要忘记点赞收藏+关注哦!!!
bitset的模拟实现
- 一、函数接口总览
- 二、bitset类的实现
- 1、构造函数
- 2、set(设置)
- 3、reset(重置)
- 4、flip(反转)
- 5、test(获取位状态)
- 6、size(算长度/个数)
- 7、count(算位图中被设置的个数)
- 8、any(该位图中是否有位被设置)
- 9、none(判断位图中是否全部位都没有被设置)
- 10、all(判断是否全被设置)
- 11、Print(打印函数)
一、函数接口总览
#include<vector>
#include<iostream>
using namespace std;namespace JRH
{// 模拟实现位图template<size_t N>class bitset{public:// 构造函数bitset();// set设置位void set(size_t pos);// reset清空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:vector<int> _bits;};
}
二、bitset类的实现
1、构造函数
在构造位图时,我们需要根据所给位数N,创建一个N位的位图,并且将该位图中的所有位都初始化为0。
我们知道,一个整型有32个比特位,但我们传来的位图肯定不可能是32的倍数的,所以我们就需要在结束完/32以后就加1,往后多开一个32个位的空间,将多余的空间放到下一个位图中。
如下图:我们假如有40位,我们则需要开两个整型(多开一个),并将这40放进去。
// 构造函数bitset(){_bits.resize(N / 32 + 1, 0);}
2、set(设置)
// set设置位void set(size_t pos){assert(pos < N);// 除一下找到在第几个int i = pos / 32;int j = pos % 32;_bits[i] |= (1 << j);}
3、reset(重置)
// reset清空void reset(size_t pos){assert(pos < N);// 除一下找到在第几个int i = pos / 32;int j = pos % 32;_bits[i] &= (~(1 << j));}
4、flip(反转)
//反转位void flip(size_t pos){assert(pos < N);// 找到在哪里int i = pos / 32;int j = pos % 32;_bits[i] ^= (1 << j);}
5、test(获取位状态)
//获取位的状态bool test(size_t pos){assert(pos < N);// 找到位置int i = pos / 32;int j = pos % 32;if (_bits[i] & (1 << j))return true;elsereturn false;}
6、size(算长度/个数)
size成员函数用于获取位图中可以容纳的位的个数,即直接计算参数模板中的位的个数即可。
//获取可以容纳的位的个数size_t size(){return N;}
7、count(算位图中被设置的个数)
//获取被设置位的个数size_t count(){size_t count = 0;for (auto e : _bits){int num = e;// 计算1的个数while (num){num = num & (num - 1);count++;}}return count;}
8、any(该位图中是否有位被设置)
只需要一个for循环,如果有一个是1则返回true,遍历结束都没有1则返回false。
//判断位图中是否有位被设置bool any(){for (auto e : _bits){if (e != 0){return true;}}return false;}
9、none(判断位图中是否全部位都没有被设置)
只需要返回any的逻辑取反即可。
//判断位图中是否全部位都没有被设置bool none(){return !any();}
10、all(判断是否全被设置)
1、先检查前n-1个整数的二进制是否为全1
2、再检查最后一个整数的前N%32个比特位是否为全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个整数的bite位for (size_t j = 0; j < N % 32; j++){if ((_bits[n - 1] & (1 << j)) == 0){return false;}}return true;}
11、Print(打印函数)
打印函数就是先打印前n-1个数值的比特位的值,再打印最后一个整数的32个比特位中前面被设置的值。
//打印函数void Print(){int count = 0;size_t n = _bits.size();// 先打印前n-1for (int i = 0; i < n - 1; i++){for (int j = 0; j < 32; j++){if (_bits[i] & (1 << j)){cout << "1";}else{cout << "0";}count++;}}// 再打印第n个的比特位for (int j = 0; j < N % 32; j++){if (_bits[n - 1] & (1 << j)){cout << "1";}else{cout << "0";}count++;}cout << endl;cout << " " << count << endl;}
更多推荐
【STL】bitset的模拟实现
发布评论