快捷導(dǎo)航

C++ 位圖及位圖的實(shí)現(xiàn)原理

更新時(shí)間：2021年05月31日 10:59:07 作者：WhiteShirtI

位圖實(shí)際上就是一個(gè)數(shù)組，因?yàn)閿?shù)組有隨機(jī)訪問的功能，比較方便查找，這個(gè)數(shù)組一般是整形，今天通過本文給大家分享c++位圖的實(shí)現(xiàn)原理及實(shí)現(xiàn)代碼，感興趣的朋友跟隨小編一起看看吧

概念

位圖就是bitmap的縮寫，所謂bitmap，就是用每一位來存放某種狀態(tài)，適用于大規(guī)模數(shù)據(jù)，該數(shù)據(jù)都是不重復(fù)的簡(jiǎn)單數(shù)據(jù)。通常是用來判斷某個(gè)數(shù)據(jù)存不存在的

例如：給40億個(gè)不重復(fù)的unsigned int的整數(shù)，沒排過序的，然后再給一個(gè)數(shù)，如何快速判斷這個(gè)數(shù)是否在那40億個(gè)數(shù)當(dāng)中
如果不看數(shù)據(jù)量，我們第一想到的肯定就是依次從頭遍歷，但是這個(gè)數(shù)據(jù)量是非常大的，有40億，遍歷40億次消耗的時(shí)間和內(nèi)存是非常多的。但是引入位圖后，就可以專門解決這種大量數(shù)據(jù)查找是否存在的問題。查找這個(gè)數(shù)是否存在所消耗的時(shí)間復(fù)雜度為O(1)，且節(jié)省了32倍的容量（下面有解釋）。下面我們一起來看看位圖的原理及代碼實(shí)現(xiàn)

原理

查找一個(gè)數(shù)是否存在，其實(shí)答案就是存在或者不存在，這種只需要回答是與否的問題，我們都可以用二進(jìn)制中的位來表示，1表示該數(shù)存在，反之0表示該數(shù)不存在。而位圖中的每個(gè)數(shù)據(jù)單元都是一個(gè)bit位，這樣子平時(shí)我們都要話32位4字節(jié)來存儲(chǔ)數(shù)據(jù)，而現(xiàn)在我們只需要花1個(gè)字節(jié)就能“存儲(chǔ)數(shù)據(jù)”，在空間上減少了約32倍的容量。例如40G的數(shù)據(jù)我們只要花1.3G來存儲(chǔ)。但是我們平時(shí)操作的數(shù)據(jù)類型最小就是一個(gè)字節(jié)，我們不能直接對(duì)位進(jìn)行操作，所以我們可以借助位運(yùn)算來對(duì)數(shù)據(jù)進(jìn)行操作。下面我們來看看數(shù)據(jù)在位圖中是如何存儲(chǔ)的
我們這里給出一個(gè)數(shù)組
int arr[] = {1,2,4,5,7,10,11,14,16,17,21,23,24,28,29,31}；則我們只需要花1個(gè)字節(jié)來存這些數(shù)據(jù)

在這里插入圖片描述

解釋：我們目前很多的機(jī)器都是小端存儲(chǔ)，也就是低地址存低位，一個(gè)整形數(shù)據(jù)中，第一個(gè)字節(jié)用來存儲(chǔ)0-7的數(shù)字，第二個(gè)字節(jié)用來存儲(chǔ)8-15的數(shù)字，第三個(gè)字節(jié)用來存儲(chǔ)16-23的數(shù)字，第四個(gè)字節(jié)用來存儲(chǔ)24-31的數(shù)字。我們來看看數(shù)字10是如何存儲(chǔ)的。先通過模上32，取余還是10，然后再將4字節(jié)中第10個(gè)比特位置為1，則表示該數(shù)字出現(xiàn)過。由于我們的機(jī)器是小端存儲(chǔ)，所以我們的每個(gè)比特位都是要從右邊開始計(jì)算的，如下圖

在這里插入圖片描述

所以說我們只需要將對(duì)應(yīng)的比特位置為1即可。但是如果我們要存儲(chǔ)的數(shù)據(jù)很大呢？其實(shí)也很簡(jiǎn)單，我們可以定義一個(gè)數(shù)組，當(dāng)做一個(gè)位圖，如果該數(shù)字在0-31之間，我們就存儲(chǔ)在0號(hào)下標(biāo)的元素中進(jìn)行操作，如果在32-63之間，則就在1號(hào)下標(biāo)之間進(jìn)行操作。計(jì)算下標(biāo)我們可以通過模32來獲得下標(biāo)。

我們知道位圖的原理后，我們?cè)谕ㄟ^原理來用代碼實(shí)現(xiàn)一個(gè)位圖吧

實(shí)現(xiàn)

成員變量和構(gòu)造函數(shù)：在實(shí)現(xiàn)位圖中，我們的成員變量只需要一個(gè)數(shù)組就可以實(shí)現(xiàn)。而這個(gè)數(shù)組有多我們要開多大呢？數(shù)組多開一個(gè)整形空間，就能多存32個(gè)數(shù)字，所以我們可以讓用戶提供一個(gè)準(zhǔn)確的數(shù)，這個(gè)數(shù)是一個(gè)數(shù)據(jù)量，也是數(shù)的最大范圍。我們可以通過該數(shù)模上32，就可以獲得該數(shù)組的大小，但是0~31模上32為0，我們開0個(gè)空間那顯然不合適，所以我們要開range/32 + 1個(gè)空間大小的數(shù)組

存儲(chǔ)數(shù)據(jù)：存儲(chǔ)一個(gè)數(shù)字num需要3個(gè)步驟，第一是需要計(jì)算出該值對(duì)應(yīng)的數(shù)組下標(biāo)。計(jì)算數(shù)組下標(biāo)方式為idx=num / 32；第二步是計(jì)算num在對(duì)應(yīng)整數(shù)的比特位的位置bitIdx=num%32；第三步是要將計(jì)算出來的bite位置為1。我們之前說過，要操作位，我們可以通過位運(yùn)算來操作，可以先將1左移bitIdx位后再和整數(shù)進(jìn)行或運(yùn)算
例如假設(shè)bitIdx=5，數(shù)據(jù)為10010011
1.將1進(jìn)行左移5位==>100000
2.將數(shù)據(jù)和第一步計(jì)算出來的結(jié)果進(jìn)行或運(yùn)算
10010011 | 100000 =10110011，此時(shí)我們就將指定位置置位1了

查找數(shù)據(jù)：要判斷一個(gè)數(shù)據(jù)是否存在，其實(shí)和存儲(chǔ)數(shù)據(jù)是類似，也是需要計(jì)算出兩個(gè)位置idx和bitIdx。然后通過這兩個(gè)位置來判斷對(duì)應(yīng)位置是否為1，為1則表示該數(shù)字存在。如何判斷呢？我們可以先將數(shù)組下標(biāo)為idx的整數(shù)向右移bitIdx位，然后再和1進(jìn)行與運(yùn)算，如果為1則表示存在，否則不存在
例如假設(shè)bitIdx=5，數(shù)據(jù)為10110011
1.將數(shù)據(jù)進(jìn)行右移5位00000101
2.將第一步計(jì)算出來的結(jié)果和1進(jìn)行與運(yùn)算
00000101 & 1 = 1，此時(shí)表示該數(shù)字存在，返回true

刪除數(shù)據(jù)：刪除數(shù)據(jù)和存儲(chǔ)數(shù)據(jù)操作一樣，唯一的區(qū)別就是將對(duì)應(yīng)的bit位置為0。我們可以通過先將1進(jìn)行左移bitIdx位，然后取反，將結(jié)果再和原來數(shù)據(jù)進(jìn)行與運(yùn)算
例如假設(shè)bitIdx=5，數(shù)據(jù)為10110011
1.將1進(jìn)行左移5位后并取反011111
2.將第一步計(jì)算出來的結(jié)果和數(shù)據(jù)進(jìn)行與運(yùn)算
10110011 & 011111 = 10010011，刪除成功

代碼：

class BitMap
{
public:
	//位圖的內(nèi)存大小和數(shù)據(jù)范圍有關(guān)
	BitMap(size_t range)
		:_bit(range / 32 + 1)
	{}

	void set(const size_t num)
	{
		//計(jì)算數(shù)組中的下標(biāo)
		int idx = num / 32;
		//計(jì)算num在對(duì)應(yīng)下標(biāo)整數(shù)中的下標(biāo)位置
		int bitIdx = num % 32;
		//將對(duì)應(yīng)的比特位置1
		_bit[idx] |= 1 << bitIdx;
	}

	bool find(const size_t num)
	{
		int idx = num / 32;
		int bitIdx = num % 32;
		return (_bit[idx] >> bitIdx) & 1;
	}

	void reset(const size_t num)
	{
		int idx = num / 32;
		int bitIdx = num % 32;
		_bit[idx] &= ~(1 << bitIdx);
	}
private:
	vector<int> _bit;
};

測(cè)試截圖：

在這里插入圖片描述