bitset类要实现的接口函数总览
bitset类的模拟实现
位图结构
我们在使用位图的各种性质的时候 需要这种结构支持随机访问
所以我们会选择vector对象来当他的成员变量
模板代码如下
template<size_t N> //模板的偏特化 具体知识可以在我的博客 模板进阶中学习 class bitset { public: private: vector<int> _bits; };
构造函数
在构造位图的时候我们要根据给定的整数N构造一个N个位大小的位图
按照一个int类型四个字节的大小判断 我们vector每个数据占大小32个位
所以说 假设我们需要32位的位图 就需要开一个整型的空间
假设我们需要64位的位图 就需要开两个整型的空间
除以32就可以了
那么这里问题就出现了 假如我们要开一个24位的空间呢
很显然我们无法指定开出3/4个字节的大小 那么这个时候的处理方式是什么呢
我们说这里的解决方式就是开空间的时候 额外开一个整型的空间大小
这样子操作只有一个缺点 就是最多会浪费一个整型的空间 但是对于我们的计算机来说一个整型的空间也不算什么
代码表示如下
// 构造函数 bitset() { _bits.resize(N / 32 + 1, 0); // 多开一个字节空间防止不能被整除 }
set reset flip test
set用于设置位
比如我们想设置第34个位 我们可以通过除以32来找到它在vector的第几个数据中
之后我们可以通过模32找到它在这个数据的第几个位中
设置位图中的指定位的步骤如下
1通过上面的方式计算出要设置的位在第i个整数的第j个位置
2将1左移j个位置之后和第i和整数进行或运算
代码和示例图表示如下
void set(size_t pos) { // 1. 计算出pos第i个整数的第j位 int i = pos / 32; int j = pos % 32; // 2. 进行或操作 _bittest[i] |= 1 << j; // 将该位设置为1 }
我们来测试下写的代码
我们可以发现 容器中的第一个数变成了四
而实际上这就是将第二位设置为1的结果
reset的成员函数用于清空位
找位置还是和设置位一样的算法
接下来步骤如下
按照前面的算法 找到第i个整数的第j位
将1左移j位之后反转并且与第i个整数按位与
代码和示例图表示如下
我们来测试下写的代码
我们可以发现 整数变成了0
flip成员函数用于反转位
找位置还是和设置位一样的算法
接下来的步骤如下
按照前面的算法 找到第i个整数的第j位
将1左移j位之后并且与第i个整数按位与
代码和示例图表示如下
我们可以发现 异或之后除了指定位置之外 其他所有的位置都没有变化
void flip(size_t pos) { // 1. 计算出pos的第i个整数的第j位 int i = pos / 32; int j = pos % 32; // 2. 进行异或操作 _bits[i] ^= (1 << j); }
我们来测试下写的代码
我们可以发现容器中的第一个数变成了四
而实际上就是第二位被反转了
test的成员函数用于获取位的状态
找位置还是和设置位一样的算法
接下来步骤如下
按照前面的算法 找到第i个整数的第j位
将1左移j位之后与第i个整数按位与
如果与出来的结果是非0 则该位未被设置 反之则被设置
这里是两种按位与的结果
代码和示例图表示如下
bool test(size_t pos) { // 1. 计算出pos的第i个整数的第j位 int i = pos / 32; int j = pos % 32; // 2. 进行与操作 int test = _bits[i] & (1 << j); // 3. 判断是否指定位为0 if (test == 0) { return false; } else // 非0 { return true; } }
我们来测试下代码
我们可以发现被设置之后test结果为真
而被重新设置之后test的结果为假
size count
size成员函数用于获取容器可以容纳位的个数
这个很简单 我们直接返回非类型模板参数就可以了
代码和演示图如下
size_t size() { return N; }
count成员函数用来获取容器中被设置的位的个数
简单来说这个函数其实就是获取容器中1的个数
对于这个算法目前来说最高效的就是这样子 假设原本的数字是n
我们使用n 与上 (n - 1)
如果是0 则说明1的个数是1
如果是非0 则n等于上面的结果继续重复操作
接下来步骤如下
按照上面的算法找出1的个数
返回1的个数
size_t count() { // 使用count计数来作为最终值 size_t count = 0; // 1. 遍历整个vector数组 使用算法找出1的个数 for (auto e : _bits) { int x = e; while (x) { x = x & (x - 1); count++; } // 2. 返回最终的结果 return count; } }
我们来测试下代码
我们可以发现设置了四个位 最后计数的结果也是四
any none all
any成员函数用于获取图中是否有被设置
只要有位被设置容器中的数就会变成非0
因此我们只需要遍历整个容器看看是否有数是非0就可以
代码和演示结果如下
bool any() { // 遍历每个整数 for (auto x : _bits) { if (x != 0) // 该整数不是0 { return true; } } return false; }
none成员函数用来判断位图中是否全部位都未被设置
这个很简单我们直接复用any就行
代码和演示结果如下
bool none() { // 复用any return !(this->any()); }
all成员函数用来判断是否所有的位都被设置成1
这个应该是实现的所有成员函数中最难的一个了
因为我们不光要考虑容器的所有位 还需要考虑被浪费的空间
大概思路如下
检查前面N-1个数的二进制是否都是1
检查第N个数的前N%32个bit位是否都是1
代码和运行结果如下
bool all() { // 1. 首先查看前面N-1个数是否为全1 int x = N / 32; while (x) { if (~(_bits[x])) { return false; } x--; } // 2. 看看第N个数是否前面y位是否为1 x = N / 32; int y = N % 32; while (y) { if ((_bits[x] & (1 << y)) == 0) { return false; } y--; } return true; }
打印函数
我们可以将位图中所有的位打印出来
整体的思路还是和上面的all差不多 为了防止位图越界的问题
我们先遍历位图的前面N-1个数
之后在遍历位图的第N个数的前面N%32个位
void Print() { // 1. 先遍历前面N-1个数 int x = N / 32; while (x) { int j = 0; for (int i = 0; i < 32; i ++) { if (_bits[j] & (1 << i)) { cout << "1" << " "; } else { cout << "0" << " "; } } j++; x--; } // 2. 遍历后面的数 x = N / 32; int y = N % 32; while (y) { if (_bits[x] & (1<<y)) { cout << "1" << " "; } else { cout << "0" << " "; } y--; } }
位图代码
namespace shy // 防止命名冲突 { template<size_t N> //模板的偏特化 具体知识可以在我的博客 模板进阶中学习 class bitset { public: // 构造函数 bitset() { _bits.resize(N / 32 + 1, 0); // 多开一个字节空间防止不能被整除 } void set(size_t pos) { // 1. 计算出pos第i个整数的第j位 int i = pos / 32; int j = pos % 32; // 2. 进行或操作 _bits[i] |= 1 << j; // 将该位设置为1 } void reset(size_t pos) { // 1. 计算出pos的第i个整数的第j位 int i = pos / 32; int j = pos % 32; // 2. 进行与操作 _bits[i] &= (~(1 << j)); } void flip(size_t pos) { // 1. 计算出pos的第i个整数的第j位 int i = pos / 32; int j = pos % 32; // 2. 进行异或操作 _bits[i] ^= (1 << j); } bool test(size_t pos) { // 1. 计算出pos的第i个整数的第j位 int i = pos / 32; int j = pos % 32; // 2. 进行与操作 int test = _bits[i] & (1 << j); // 3. 判断是否指定位为0 if (test == 0) { return false; } else // 非0 { return true; } } size_t size() { return N; } size_t count() { // 使用count计数来作为最终值 size_t count = 0; // 1. 遍历整个vector数组 使用算法找出1的个数 for (auto e : _bits) { int x = e; while (x) { x = x & (x - 1); count++; } // 2. 返回最终的结果 return count; } } bool any() { // 遍历每个整数 for (auto x : _bits) { if (x != 0) // 该整数不是0 { return true; } } return false; } bool none() { // 复用any return !(this->any()); } bool all() { // 1. 首先查看前面N-1个数是否为全1 int x = N / 32; while (x) { if (~(_bits[x])) { return false; } x--; } // 2. 看看第N个数是否前面y位是否为1 x = N / 32; int y = N % 32; while (y) { if ((_bits[x] & (1 << y)) == 0) { return false; } y--; } return true; } void Print() { // 1. 先遍历前面N-1个数 int x = N / 32; while (x) { int j = 0; for (int i = 0; i < 32; i ++) { if (_bits[j] & (1 << i)) { cout << "1" << " "; } else { cout << "0" << " "; } } j++; x--; } // 2. 遍历后面的数 x = N / 32; int y = N % 32; while (y) { if (_bits[x] & (1<<y)) { cout << "1" << " "; } else { cout << "0" << " "; } y--; } } private: vector<int> _bits; }; }
