C++ bitset（位图）的模拟实现

一、bitset接口总览

#pragma once
#include <iostream>
#include <vector>
#include <assert.h>
namespace qi
{template <size_t N>class bitset{private:std::vector<int> _bits;public:bitset();void set(size_t pos);void reset(size_t pos);void flip(size_t pos);size_t size();size_t count();bool test(size_t pos);bool any();bool none();bool all();void Print(); //打印函数};
}

二、bitset模拟实现

1. 构造函数

在创建位图的时候我们需要根据所给的参数N，来构造一个N位的位图，并将该位图的所有位全部设置为0。

这里我们使用vector来做底层容器，一个int有32个比特位，但是非类型模板参数N，不一定总是32的整数倍，所以我们在构造的时候得先计算一下需要几个int。

例如，假如我们要建立一个50个比特位的位图，就需要两个int大小，共64个比特位，使用前50个比特位，后14个舍弃不用就好。

因此我们用式子 N/32+1来计算需要几个int。

具体实现也比较简单，直接调用vector的resize函数即可。

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

2. set、reset、flip、test

set，根据下标pos，把位图的该位置设置成1

• 计算出该位位于第 i 个整数的第 j 个比特位。
• 将1左移 j 位后与第 i 个整数进行或运算即可。

void set(size_t pos)
{assert(pos < N);int i = pos / 32;//第几个整数，算出来的i相当与下标int j = pos % 32;//第i个整数的第j个比特位，j也相当于下标//注意下标都是从0开始的_bits[i] |= (1 << j);
}

reset根据下标pos，将下标为pos位置的位图设置成0

• 计算出该位位于第 i 个整数的第 j 个比特位。
• 将1左移 j 位再整体反转后与第 i 个整数进行与运算即可。

void reset(size_t pos)
{assert(pos < N);int i = pos / 32;//第几个整数，算出来的i相当与下标int j = pos % 32;//第i个整数的第j个比特位，j也相当于下标//注意下标都是从0开始的_bits[i] &= (~(1 << j));//左移后要取反在&
}

flip根据下标pos反转指定下标的比特位

• 计算出该位位于第 i 个整数的第 j 个比特位。
• 将1左移 j 位后与第 i 个整数进行异或运算即可。

void flip(size_t pos)
{assert(pos < N);int i = pos / 32;//第几个整数，算出来的i相当与下标int j = pos % 32;//第i个整数的第j个比特位，j也相当于下标//注意下标都是从0开始的_bits[i] ^= (1 << j);
}

test检测下标pos处的位图是否为1，为1返回true，否则返回false

• 计算出该位位于第 i 个整数的第 j 个比特位。
• 将1左移 j 位后与第 i 个整数进行与运算得出结果。
• 若结果非0，则该位被设置，否则该位未被设置。

bool test(size_t pos)
{assert(pos < N);int i = pos / 32;//第几个整数，算出来的i相当与下标int j = pos % 32;//第i个整数的第j个比特位，j也相当于下标//注意下标都是从0开始的if (_bits[i] & (1 << j)){return true;}return false;
}

3. size、count

size用于返回位图一共有多少位，也就是非类型模板参数N的值

直接返回N就好

size_t size()
{return N;
}

count用于计算该位图中有多少位是1，返回值是位图中1的个数
统计二进制中1的个数的方法如下：

• 将原数 n 与 n - 1 进行与运算得到新的 n 。
• 判断 n 是否为0，若 n 不为0则继续进行第一步。
• 如此进行下去，直到 n 最终为0，此时该操作进行了几次就说明二进制中有多少个1。

因为该操作每进行一次就会消去二进制中最右边的1，如图：

size_t count()
{size_t count = 0;for (auto e : _bits){int num = e;while (num){num &= (num - 1);++count;}}return count;
}

4. any、none、all

any表示位图中只要有一个1那就返回true，否则返回false

判断方式比较简单，每一个整数的所有比特位，只要有一个为1，那该整数就肯定不等于0，所以，我们可以遍历所有整数，只要有一个整数不等于0，那就说明有1，返回true，否则所有整数都是0，没一个1，返回false

bool any()
{for (auto e : _bits){if (e != 0){return true;}}return false;;
}

none表示位图中如果全是0，没一个1那就返回true，否则返回false

其实和any是对立的，如果any为假，说明全为0，说明none为真，所以none中只需将any的结果取反后返回就好了。

bool none()
{return !any();
}

all表示，全为1返回true，否则返回false

判断过程分为两步：

• 先检查前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++){if (~_bits[i] != 0) //取反后不为全0，说明取反前不为全1return false;}//再检查最后一个整数的前N%32位for (size_t j = 0; j < N % 32; j++){if ((_bits[n - 1] & (1 << j)) == 0) //该位未被设置return false;}return true;
}

5. 打印函数

为了验证bitset对象的正确性，我们可以编写一个自定义的打印函数，该函数将遍历bitset中的每一位，并打印出其状态（0或1）。同时，这个函数还可以统计并返回bitset中实际被设置（即值为1）的位的数量，并将这个数量与bitset的模板参数（即预期的大小）进行比较，以确认bitset的大小是否符合预期。

#include <iostream>
#include <bitset>
using namespace std;// 自定义打印函数，用于打印bitset并统计1的个数
template<size_t N>
void printAndVerifyBitset(const bitset<N>& bs) {size_t count = 0; // 用于统计1的个数cout << "Bitset: ";```cpp
//打印函数
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)) //该位被设置std::cout << "1";else //该位未被设置std::cout << "0";count++;}}//再打印最后一个整数的前N%32位for (size_t j = 0; j < N % 32; j++){if (_bits[n - 1] & (1 << j)) //该位被设置std::cout << "1";else //该位未被设置std::cout << "0";count++;}std::cout << " " << count << std::endl; //打印总共打印的位的个数
}

三、完整代码

#pragma once
#include <iostream>
#include <vector>
#include <assert.h>
namespace qi
{template <size_t N>class bitset{private:std::vector<int> _bits;public:bitset(){_bits.resize(N / 32 + 1, 0);}void set(size_t pos){assert(pos < N);int i = pos / 32;int j = pos % 32;_bits[i] |= (1 << j);}void reset(size_t pos){assert(pos < N);int i = pos / 32;int j = pos % 32;_bits[i] &= (~(1 << j));}void flip(size_t pos){assert(pos < N);int i = pos / 32;int j = pos % 32;_bits[i] ^= (1 << j);}size_t size(){return N;}size_t count(){size_t count = 0;for (auto e : _bits){int num = e;while (num){num &= (num - 1);++count;}}return count;}bool test(size_t pos){assert(pos < N);int i = pos / 32;int j = pos % 32;if (_bits[i] & (1 << j)){return true;}return false;}bool any(){for (auto e : _bits){if (e != 0){return true;}}return false;;}bool none(){return !any();}bool all(){size_t n = _bits.size();for (int i = 0; i < n - 1; i++){if (~_bits[i] != 0){return false;}}for(int i = 0; i < N % 32; i++){if ((_bits[n - 1] & (1 << i)) == 0) //该位未被设置return false;}return true;}//打印函数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)) //该位被设置std::cout << "1";else //该位未被设置std::cout << "0";count++;}}//再打印最后一个整数的前N%32位for (size_t j = 0; j < N % 32; j++){if (_bits[n - 1] & (1 << j)) //该位被设置std::cout << "1";else //该位未被设置std::cout << "0";count++;}std::cout << " " << count << std::endl; //打印总共打印的位的个数}};
}