C++位圖的實(shí)現(xiàn)原理與方法
概念
位圖就是bitmap的縮寫,所謂bitmap,就是用每一位來(lái)存放某種狀態(tài),適用于大規(guī)模數(shù)據(jù),該數(shù)據(jù)都是不重復(fù)的簡(jiǎn)單數(shù)據(jù)。通常是用來(lái)判斷某個(gè)數(shù)據(jù)存不存在的
例如:給40億個(gè)不重復(fù)的unsigned int的整數(shù),沒(méi)排過(guò)序的,然后再給一個(gè)數(shù),如何快速判斷這個(gè)數(shù)是否在那40億個(gè)數(shù)當(dāng)中
如果不看數(shù)據(jù)量,我們第一想到的肯定就是依次從頭遍歷,但是這個(gè)數(shù)據(jù)量是非常大的,有40億,遍歷40億次消耗的時(shí)間和內(nèi)存是非常多的。但是引入位圖后,就可以專門解決這種大量數(shù)據(jù)查找是否存在的問(wèn)題。查找這個(gè)數(shù)是否存在所消耗的時(shí)間復(fù)雜度為O(1),且節(jié)省了32倍的容量(下面有解釋)。下面我們一起來(lái)看看位圖的原理及代碼實(shí)現(xiàn)
原理
查找一個(gè)數(shù)是否存在,其實(shí)答案就是存在或者不存在,這種只需要回答是與否的問(wèn)題,我們都可以用二進(jìn)制中的位來(lái)表示,1表示該數(shù)存在,反之0表示該數(shù)不存在。而位圖中的每個(gè)數(shù)據(jù)單元都是一個(gè)bit位,這樣子平時(shí)我們都要話32位4字節(jié)來(lái)存儲(chǔ)數(shù)據(jù),而現(xiàn)在我們只需要花1個(gè)字節(jié)就能“存儲(chǔ)數(shù)據(jù)”,在空間上減少了約32倍的容量。例如40G的數(shù)據(jù)我們只要花1.3G來(lái)存儲(chǔ)。但是我們平時(shí)操作的數(shù)據(jù)類型最小就是一個(gè)字節(jié),我們不能直接對(duì)位進(jìn)行操作,所以我們可以借助位運(yùn)算來(lái)對(duì)數(shù)據(jù)進(jìn)行操作。下面我們來(lái)看看數(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é)來(lái)存這些數(shù)據(jù)
解釋:我們目前很多的機(jī)器都是小端存儲(chǔ),也就是低地址存低位,一個(gè)整形數(shù)據(jù)中,第一個(gè)字節(jié)用來(lái)存儲(chǔ)0-7的數(shù)字,第二個(gè)字節(jié)用來(lái)存儲(chǔ)8-15的數(shù)字,第三個(gè)字節(jié)用來(lái)存儲(chǔ)16-23的數(shù)字,第四個(gè)字節(jié)用來(lái)存儲(chǔ)24-31的數(shù)字。我們來(lái)看看數(shù)字10是如何存儲(chǔ)的。先通過(guò)模上32,取余還是10,然后再將4字節(jié)中第10個(gè)比特位置為1,則表示該數(shù)字出現(xiàn)過(guò)。由于我們的機(jī)器是小端存儲(chǔ),所以我們的每個(gè)比特位都是要從右邊開(kāi)始計(jì)算的,如下圖
所以說(shuō)我們只需要將對(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)我們可以通過(guò)模32來(lái)獲得下標(biāo)。
我們知道位圖的原理后,我們?cè)谕ㄟ^(guò)原理來(lái)用代碼實(shí)現(xiàn)一個(gè)位圖吧
實(shí)現(xiàn)
成員變量和構(gòu)造函數(shù):在實(shí)現(xiàn)位圖中,我們的成員變量只需要一個(gè)數(shù)組就可以實(shí)現(xiàn)。而這個(gè)數(shù)組有多我們要開(kāi)多大呢?數(shù)組多開(kāi)一個(gè)整形空間,就能多存32個(gè)數(shù)字,所以我們可以讓用戶提供一個(gè)準(zhǔn)確的數(shù),這個(gè)數(shù)是一個(gè)數(shù)據(jù)量,也是數(shù)的最大范圍。我們可以通過(guò)該數(shù)模上32,就可以獲得該數(shù)組的大小,但是0~31模上32為0,我們開(kāi)0個(gè)空間那顯然不合適,所以我們要開(kāi)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ì)算出來(lái)的bite位置為1。我們之前說(shuō)過(guò),要操作位,我們可以通過(guò)位運(yùn)算來(lái)操作,可以先將1左移bitIdx位后再和整數(shù)進(jìn)行或運(yùn)算
例如假設(shè)bitIdx=5,數(shù)據(jù)為10010011
1.將1進(jìn)行左移5位==>100000
2.將數(shù)據(jù)和第一步計(jì)算出來(lái)的結(jié)果進(jìn)行或運(yùn)算
10010011 | 100000 =10110011,此時(shí)我們就將指定位置置位1了
查找數(shù)據(jù):要判斷一個(gè)數(shù)據(jù)是否存在,其實(shí)和存儲(chǔ)數(shù)據(jù)是類似,也是需要計(jì)算出兩個(gè)位置idx和bitIdx。然后通過(guò)這兩個(gè)位置來(lái)判斷對(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ì)算出來(lái)的結(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。我們可以通過(guò)先將1進(jìn)行左移bitIdx位,然后取反,將結(jié)果再和原來(lái)數(shù)據(jù)進(jìn)行與運(yùn)算
例如假設(shè)bitIdx=5,數(shù)據(jù)為10110011
1.將1進(jìn)行左移5位后并取反011111
2.將第一步計(jì)算出來(lái)的結(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è)試截圖:
總結(jié)
到此這篇關(guān)于C++位圖的實(shí)現(xiàn)原理與方法的文章就介紹到這了,更多相關(guān)C++位圖實(shí)現(xiàn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Qt學(xué)習(xí)筆記之QPalette調(diào)色板類
這篇文章主要為大家詳細(xì)介紹了Qt學(xué)習(xí)筆記之QPalette調(diào)色板類,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2019-07-07一起來(lái)學(xué)習(xí)C++的動(dòng)態(tài)內(nèi)存管理
這篇文章主要為大家詳細(xì)介紹了C++的動(dòng)態(tài)內(nèi)存管理,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來(lái)幫助2022-03-03C語(yǔ)言與java語(yǔ)言中關(guān)于二維數(shù)組的區(qū)別
這篇文章主要介紹了C語(yǔ)言與java語(yǔ)言中關(guān)于二維數(shù)組的區(qū)別,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-08-08C語(yǔ)言實(shí)現(xiàn)制作通訊錄(新手推薦)
本文推薦給C語(yǔ)言學(xué)習(xí)到結(jié)構(gòu)體的新手們,供其練習(xí)。這篇文章主要是利用C語(yǔ)言制作一個(gè)簡(jiǎn)單的通訊錄功能,感興趣的小伙伴可以跟隨小編一起了解一下2022-09-09C語(yǔ)言詳解格式控制符scanf與printf的輸入輸出
這篇文章主要介紹了C語(yǔ)言格式控制符中輸入scanf()和輸出printf()的操作,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2022-04-04基于C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)易掃雷游戲
這篇文章主要為大家詳細(xì)介紹了基于C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)易掃雷游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下<BR>2022-01-01數(shù)據(jù)結(jié)構(gòu) 數(shù)組順序存儲(chǔ)詳細(xì)介紹
這篇文章主要介紹了數(shù)據(jù)結(jié)構(gòu) 數(shù)組順序存儲(chǔ)詳細(xì)介紹的相關(guān)資料,需要的朋友可以參考下2017-05-05