• 模擬bitset就是用一個普通的數(shù)組來存儲數(shù)據(jù)以達到模擬的目的。
• 一個單元我們分成4個小組，每個小組8個位置。存放一個數(shù)據(jù)要先判斷在那個單元，然后是那個小組，那個位置。
• 找到對應單元后，數(shù)據(jù)/8=對應小組；數(shù)據(jù)%8=對應位置。

• 如果我們以一個整型作為比特位的容器，那么如果要求0~N范圍的比特位，就需要有N/32+1個整型來容納這些比特位，同理如果以char為容器，則需要N/8+1個char來容納N個比特位。這里我們用vector數(shù)組作為底層容納比特位的容器。之所以+1是怕開的空間存不下，所以多開一個，就算剩下也剩不了多少。

namespace cpp
{
	//N個比特位的位圖
	templateclass bitset
	{
	public:
		//構造函數(shù)
		bitset();
		//把value映射的位標記成1
		void set(size_t value);
		//把value映射的位標記成0
		void reset(size_t value);
		//判斷指定位value的狀態(tài)是否為1
		bool test(size_t value);
		//翻轉指定位置
		void flip(size_t value);
		//獲取位圖中可以容納位N的個數(shù)
		size_t size()
		//統(tǒng)計set中1的位數(shù)
		size_t count();
		//判斷所有比特位若無置為1，返回true
		bool none();
		//判斷位圖中是否有位被置為1，若有則返回true
		bool any();
		//全部NUM個bit位被set返回true
		bool all();
	private:
		vector_bits;//位圖
	};
}

這里我們用的存儲類型是char。

構造還是構造，但是文章已不是當年的文章了。

public :
		//構造函數(shù)
		bit_set
		{
			_bits.resize(N / 8 + 1,0);   // 全部賦值0
		}

之所以+1是因為如果數(shù)據(jù)的個數(shù)不是8的倍數(shù)時，可以再存進去，要不那多余的數(shù)據(jù)咋弄？

把映射的位置標記為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正好相反，這個是把指定位置的數(shù)變成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的狀態(tài)是否為1
		bool test(size_t value)
		{
			size_t i = value / 8;  //找到小組
			size_t j = value % 8;   //找到位置
			//把對應位置標記為1
			_bits[i] &= (1<< j);  
		}

指定位置數(shù)據(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);
		}

統(tǒng)計位圖中出現(xiàn)的1的次數(shù)?

這個跟前面幾個就不一樣了。

這個是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的個數(shù)

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

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧