• 模拟bitset就是用一个普通的数组来存储数据以达到模拟的目的。
• 一个单元我们分成4个小组，每个小组8个位置。存放一个数据要先判断在那个单元，然后是那个小组，那个位置。
• 找到对应单元后，数据/8=对应小组；数据%8=对应位置。

• 如果我们以一个整型作为比特位的容器，那么如果要求0~N范围的比特位，就需要有N/32+1个整型来容纳这些比特位，同理如果以char为容器，则需要N/8+1个char来容纳N个比特位。这里我们用vector数组作为底层容纳比特位的容器。之所以+1是怕开的空间存不下，所以多开一个，就算剩下也剩不了多少。

namespace cpp
{
	//N个比特位的位图
	templateclass bitset
	{
	public:
		//构造函数
		bitset();
		//把value映射的位标记成1
		void set(size_t value);
		//把value映射的位标记成0
		void reset(size_t value);
		//判断指定位value的状态是否为1
		bool test(size_t value);
		//翻转指定位置
		void flip(size_t value);
		//获取位图中可以容纳位N的个数
		size_t size()
		//统计set中1的位数
		size_t count();
		//判断所有比特位若无置为1，返回true
		bool none();
		//判断位图中是否有位被置为1，若有则返回true
		bool any();
		//全部NUM个bit位被set返回true
		bool all();
	private:
		vector_bits;//位图
	};
}

这里我们用的存储类型是char。

构造还是构造，但是文章已不是当年的文章了。

public :
		//构造函数
		bit_set
		{
			_bits.resize(N / 8 + 1,0);   // 全部赋值0
		}

之所以+1是因为如果数据的个数不是8的倍数时，可以再存进去，要不那多余的数据咋弄？

把映射的位置标记为1（把设置位置标记为1）。

例如：value=13;

//映射的位置标为1
		void set(size_t value)
		{
			size_t i = value / 8;  //找到小组
			size_t j = value % 8;   //找到位置
			//把对应位置标记为1
			_bits[i] |= 1<< j;     //或运算，有1则1
		}

清空指定位或所有位 

这个和set正好相反，这个是把指定位置的数变成0，最后一步变化，其他不变，先按位取反，在按位与即可。j<<1按位取反后变成1，在按位与_bits[i]后就设置成0了。

//把value映射的位标记成0
		void reset(size_t value)
		{
			size_t i = value / 8;  //找到小组
			size_t j = value % 8;   //找到位置
			//把对应位置标记为1
			_bits[i] &=~(( 1<< j));     //先按位取反在与运算
		}

判断指定位置是否为1

这个跟上面的reset就缺少一个按位取反。只进行一个按位与运算即可

//判断指定位value的状态是否为1
		bool test(size_t value)
		{
			size_t i = value / 8;  //找到小组
			size_t j = value % 8;   //找到位置
			//把对应位置标记为1
			_bits[i] &= (1<< j);  
		}

指定位置数据翻转： 如果是1变成0，0变成1。

这个按位异或就行了 ,相同为0，1变成0，相异为1，0^1=1

//翻转指定pos
		void flip(size_t value)
		{
			size_t i = value / 8;  //找到小组
			size_t j = value % 8;   //找到位置
			//把对应位置标记为1
			_bits[i] ^= (1<< j);
		}

统计位图中出现的1的次数 

这个跟前面几个就不一样了。

这个是n&n-1

size_t count()
		{
			size_t count = 0;
			for (auto e : _bits)
			{
				int n = e;   //再设置个中间变量，别直接用e
				while (n)
				{
					n = n & (n - 1);
					count++;
				}
			}
			return count;
		}

size的作用是获取位图中可以容纳位N的个数

size_t size()
		{
			return N;
		}

none是查找位图中是否全部是0，是就返回true,不是返回false。

any是查找位图中是否有1，是就返回true,没有返回false。any可以复用none。完整

bool none()
		{
			//遍历每个char
			for (auto e : _bits)
			{
				if (e != 0)//位图中有位置被置为1，返回false
					return false;
			}
			return true;//说明全为0，返回true
		}
		//若有位置为1，返回true
		bool any()
		{
			 return !none;
		}

完整代码可到gitee查看

C++ 进阶: 本仓库存放一些较难C++代码https://gitee.com/j-jun-jie/c---advanced.git

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧