位圖介紹

一、位圖的引入

先來看下邊一道面試題：

給40億個不重復的無符號整數(shù)，沒排過序。給一個無符號整數(shù)，如何快速判斷一個數(shù)是否在這40億個數(shù)中。

經過我們之前的學習，我們可能會有以下的思路：

• 對這些數(shù)進行排序，再通過二分算法，查找這個數(shù)是否存在
• 插入到unordered_set中，使用find函數(shù)查找是否存在

上述方法看起來還不錯，二分查找算法時間復雜度為logN,而插入到unordered_set中時間復雜度為O(N),而查找時時間復雜度為O(1)，但是都有一個問題就是要將空間不足，40億個無符號整形，需要160億字節(jié)的空間，大概就是16GB的空間，一般計算機的內促都是4G或者8G，所以空間不足，此時就有了位圖的方法來解決：

數(shù)據(jù)是否在給定的整形數(shù)據(jù)中，結果是在或者不在，剛好是兩種狀態(tài)，那么可以使用一個二進制比特位來代表數(shù)據(jù)是否存在的信息，如果二進制比特位為1，代表存在，為0代表不存在。比如：

對于上圖來說，有一個整形數(shù)組，我們可以使用直接定址法對數(shù)組的數(shù)據(jù)進行映射，但是與之前不同的是，此時只是使用一個比特位來代表一個整形數(shù)據(jù)，當這個數(shù)存在時，比特位置1，不存在時，比特位置0,此時就可以大大節(jié)省空間資源，無符號整數(shù)只有2的32次方個，所以最多開2的32次方個空間，一個空間為一個比特，所以最終只需要512MB的空間。但是我們不能按照位來空間，最少必須一個字節(jié)，所以我們就每次開一個字節(jié)的空間，也就是8個比特位，將8位當做一個整體來處理，對要保存的數(shù)據(jù)除8就是第幾個字節(jié)，對保存的數(shù)據(jù)模8就是在這個字節(jié)中的第幾個位置。

二、位圖的概念

所謂位圖，就是用每一位來存放某種狀態(tài)，適用于海量數(shù)據(jù)，數(shù)據(jù)無重復的場景。通常是用來判斷某個數(shù)據(jù)存不存在的。

那么位圖還有哪些應用呢？

• 快速查找某個數(shù)據(jù)是否在一個集合中
• 排序 + 去重
• 求兩個集合的交集、并集等
• 操作系統(tǒng)中磁盤塊標記

位圖模擬實現(xiàn)

一、構造函數(shù)

由于不能按位開空間，所以我們選擇每次開一個字節(jié)的空間，由于有范圍最大為N，一位關聯(lián)一個數(shù)據(jù)，所以需要開N/8個字節(jié)的空間，但是有時可能不能整除，所以要開N/8+1個字節(jié)的空間。所以

直接在構造函數(shù)中開好空間：

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

二、set，reset，test函數(shù)

set函數(shù)的作用是對位圖中的某一位進行填充

i就表示是第幾個字節(jié)，而j表示該位在該字節(jié)中的第幾位，所以對1進行左移j位后與該字節(jié)按位或，按位或的作用時不論該位為0還是為1，都將該位變?yōu)?.

void set(size_t x)
		{
			int i = x / 8;
			int j = x % 8;
			_bits[i] |= (1 << j);
		}

reset的作用是將某一位清空

同樣的將要清空的那一位置為0，進行按位與，不論原本該位是0還是1，都將該位置0

void reset(size_t x)
		{
			int i = x / 8;
			int j = x % 8;
			_bits[i] &= ~(1 << j);
		}

test的作用是檢測位圖中某一位是否存在

bool test(size_t x)
		{
			int i = x / 8;
			int j = x % 8;
			return _bits[i] & (1 << j);
		}

三、代碼測試

void test_bit_set1()
	{
		bitset<100> bs1;
		bs1.set(8);
		bs1.set(9);
		bs1.set(20);
		cout << bs1.test(8) << endl;
		cout << bs1.test(9) << endl;
		cout << bs1.test(20) << endl;
		bs1.reset(8);
		bs1.reset(9);
		bs1.reset(20);
		cout << bs1.test(8) << endl;
		cout << bs1.test(9) << endl;
		cout << bs1.test(20) << endl;
	}

四、完整代碼

namespace tmt
{
	template<size_t N>
	class bitset
	{
	public:
		bitset()
		{
			_bits.resize(N / 8 + 1,0);
		}
		void set(size_t x)
		{
			int i = x / 8;
			int j = x % 8;
			_bits[i] |= (1 << j);
		}
		void reset(size_t x)
		{
			int i = x / 8;
			int j = x % 8;
			_bits[i] &= ~(1 << j);
		}
		bool test(size_t x)
		{
			int i = x / 8;
			int j = x % 8;
			return _bits[i] & (1 << j);
		}
	private:
		vector<char> _bits;
	};
	void test_bit_set1()
	{
		bitset<100> bs1;
		bs1.set(8);
		bs1.set(9);
		bs1.set(20);
		cout << bs1.test(8) << endl;
		cout << bs1.test(9) << endl;
		cout << bs1.test(20) << endl;
		bs1.reset(8);
		bs1.reset(9);
		bs1.reset(20);
		cout << bs1.test(8) << endl;
		cout << bs1.test(9) << endl;
		cout << bs1.test(20) << endl;
	}

到此這篇關于C++中bitset位圖介紹及模擬實現(xiàn)的文章就介紹到這了,更多相關C++ bitset位圖內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論