位圖介紹

一、位圖的引入

先來(lái)看下邊一道面試題：

給40億個(gè)不重復(fù)的無(wú)符號(hào)整數(shù)，沒(méi)排過(guò)序。給一個(gè)無(wú)符號(hào)整數(shù)，如何快速判斷一個(gè)數(shù)是否在這40億個(gè)數(shù)中。

經(jīng)過(guò)我們之前的學(xué)習(xí)，我們可能會(huì)有以下的思路：

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

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

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

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

二、位圖的概念

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

那么位圖還有哪些應(yīng)用呢？

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

位圖模擬實(shí)現(xiàn)

一、構(gòu)造函數(shù)

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

直接在構(gòu)造函數(shù)中開(kāi)好空間：

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

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

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

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

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

reset的作用是將某一位清空

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

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

test的作用是檢測(cè)位圖中某一位是否存在

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

三、代碼測(cè)試

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;
	}

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

最新評(píng)論