C++ 位圖及位圖的實現原理
概念
位圖就是bitmap的縮寫，所謂bitmap，就是用每一位來存放某種狀態，適用於大規模數據，該數據都是不重復的簡單數據。通常是用來判斷某個數據存不存在的
例如：給40億個不重復的unsigned int的整數，沒排過序的，然後再給一個數，如何快速判斷這個數是否在那40億個數當中
如果不看數據量，我們第一想到的肯定就是依次從頭遍歷，但是這個數據量是非常大的，有40億，遍歷40億次消耗的時間和內存是非常多的。但是引入位圖後，就可以專門解決這種大量數據查找是否存在的問題。查找這個數是否存在所消耗的時間復雜度為O(1)，且節省瞭32倍的容量（下面有解釋）。下面我們一起來看看位圖的原理及代碼實現
原理
查找一個數是否存在，其實答案就是存在或者不存在，這種隻需要回答是與否的問題，我們都可以用二進制中的位來表示，1表示該數存在，反之0表示該數不存在。而位圖中的每個數據單元都是一個bit位，這樣子平時我們都要話32位4字節來存儲數據，而現在我們隻需要花1個字節就能“存儲數據”，在空間上減少瞭約32倍的容量。例如40G的數據我們隻要花1.3G來存儲。但是我們平時操作的數據類型最小就是一個字節，我們不能直接對位進行操作，所以我們可以借助位運算來對數據進行操作。下面我們來看看數據在位圖中是如何存儲的
我們這裡給出一個數組
int arr[] = {1,2,4,5,7,10,11,14,16,17,21,23,24,28,29,31}；則我們隻需要花1個字節來存這些數據
解釋：我們目前很多的機器都是小端存儲，也就是低地址存低位，一個整形數據中，第一個字節用來存儲0-7的數字，第二個字節用來存儲8-15的數字，第三個字節用來存儲16-23的數字，第四個字節用來存儲24-31的數字。我們來看看數字10是如何存儲的。先通過模上32，取餘還是10，然後再將4字節中第10個比特位置為1，則表示該數字出現過。由於我們的機器是小端存儲，所以我們的每個比特位都是要從右邊開始計算的，如下圖
所以說我們隻需要將對應的比特位置為1即可。但是如果我們要存儲的數據很大呢？其實也很簡單，我們可以定義一個數組，當做一個位圖，如果該數字在0-31之間，我們就存儲在0號下標的元素中進行操作，如果在32-63之間，則就在1號下標之間進行操作。計算下標我們可以通過模32來獲得下標。
我們知道位圖的原理後，我們在通過原理來用代碼實現一個位圖吧
實現
成員變量和構造函數：在實現位圖中，我們的成員變量隻需要一個數組就可以實現。而這個數組有多我們要開多大呢？數組多開一個整形空間，就能多存32個數字，所以我們可以讓用戶提供一個準確的數，這個數是一個數據量，也是數的最大范圍。我們可以通過該數模上32，就可以獲得該數組的大小，但是0~31模上32為0，我們開0個空間那顯然不合適，所以我們要開range/32 + 1個空間大小的數組
存儲數據：存儲一個數字num需要3個步驟，第一是需要計算出該值對應的數組下標。計算數組下標方式為idx=num / 32；第二步是計算num在對應整數的比特位的位置bitIdx=num%32；第三步是要將計算出來的bite位置為1。我們之前說過，要操作位，我們可以通過位運算來操作，可以先將1左移bitIdx位後再和整數進行或運算
例如假設bitIdx=5，數據為10010011
1.將1進行左移5位==>100000
2.將數據和第一步計算出來的結果進行或運算
10010011 | 100000 =10110011，此時我們就將指定位置置位1瞭
查找數據：要判斷一個數據是否存在，其實和存儲數據是類似，也是需要計算出兩個位置idx和bitIdx。然後通過這兩個位置來判斷對應位置是否為1，為1則表示該數字存在。如何判斷呢？我們可以先將數組下標為idx的整數向右移bitIdx位，然後再和1進行與運算，如果為1則表示存在，否則不存在
例如假設bitIdx=5，數據為10110011
1.將數據進行右移5位00000101
2.將第一步計算出來的結果和1進行與運算
00000101 & 1 = 1，此時表示該數字存在，返回true
刪除數據：刪除數據和存儲數據操作一樣，唯一的區別就是將對應的bit位置為0。我們可以通過先將1進行左移bitIdx位，然後取反，將結果再和原來數據進行與運算
例如假設bitIdx=5，數據為10110011
1.將1進行左移5位後並取反011111
2.將第一步計算出來的結果和數據進行與運算
10110011 & 011111 = 10010011，刪除成功
代碼：
class BitMap
{
public:
//位圖的內存大小和數據范圍有關
BitMap(size_t range)
:_bit(range / 32 + 1)
{}
void set(const size_t num)
{
//計算數組中的下標
int idx = num / 32;
//計算num在對應下標整數中的下標位置
int bitIdx = num % 32;
//將對應的比特位置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++ 位圖及位圖的實現原理的詳細內容，更多關於C++ 位圖的資料請關註WalkonNet其它相關文章！