## 方法介紹 ### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/06.07.md#什么是bit-map)什么是Bit-map 所謂的Bit-map就是用一個bit位來標記某個元素對應的Value， 而Key即是該元素。由于采用了Bit為單位來存儲數據，因此在存儲空間方面，可以大大節省。 來看一個具體的例子，假設我們要對0-7內的5個元素(4,7,2,5,3)排序（這里假設這些元素沒有重復）。那么我們就可以采用Bit-map的方法來達到排序的目的。要表示8個數，我們就只需要8個Bit（1Bytes），首先我們開辟1Byte的空間，將這些空間的所有Bit位都置為0(如下圖：) [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/9/9.2/9.2.1.gif) 然后遍歷這5個元素，首先第一個元素是4，那么就把4對應的位置為1（可以這樣操作 p+(i/8)|(0×01<<(i%8)) 當然了這里的操作涉及到Big-ending和Little-ending的情況，這里默認為Big-ending）,因為是從零開始的，所以要把第五位置為一（如下圖）： [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/9/9.2/9.2.2.gif) 然后再處理第二個元素7，將第八位置為1,，接著再處理第三個元素，一直到最后處理完所有的元素，將相應的位置為1，這時候的內存的Bit位的狀態如下： [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/9/9.2/9.2.3.gif) 然后我們現在遍歷一遍Bit區域，將該位是一的位的編號輸出（2，3，4，5，7），這樣就達到了排序的目的。下面的代碼給出了一個BitMap的用法：排序。 ~~~ //定義每個Byte中有8個Bit位 #include ＜memory.h＞ #define BYTESIZE 8 void SetBit(char *p, int posi) { for(int i=0; i < (posi/BYTESIZE); i++) { p++; } *p = *p|(0x01<<(posi%BYTESIZE));//將該Bit位賦值1 return; } void BitMapSortDemo() { //為了簡單起見，我們不考慮負數 int num[] = {3,5,2,10,6,12,8,14,9}; //BufferLen這個值是根據待排序的數據中最大值確定的 //待排序中的最大值是14，因此只需要2個Bytes(16個Bit) //就可以了。 const int BufferLen = 2; char *pBuffer = new char[BufferLen]; //要將所有的Bit位置為0，否則結果不可預知。 memset(pBuffer,0,BufferLen); for(int i=0;i<9;i++) { //首先將相應Bit位上置為1 SetBit(pBuffer,num[i]); } //輸出排序結果 for(int i=0;i<BufferLen;i++)//每次處理一個字節(Byte) { for(int j=0;j<BYTESIZE;j++)//處理該字節中的每個Bit位 { //判斷該位上是否是1，進行輸出，這里的判斷比較笨。 //首先得到該第j位的掩碼（0x01＜＜j），將內存區中的 //位和此掩碼作與操作。最后判斷掩碼是否和處理后的 //結果相同 if((*pBuffer&(0x01<<j)) == (0x01<<j)) { printf("%d ",i*BYTESIZE + j); } } pBuffer++; } } int _tmain(int argc, _TCHAR* argv[]) { BitMapSortDemo(); return 0; } ~~~ 可進行數據的快速查找，判重，刪除，一般來說數據范圍是int的10倍以下 ### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/06.07.md#基本原理及要點)基本原理及要點 使用bit數組來表示某些元素是否存在，比如8位電話號碼. ## [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/06.07.md#問題實例)問題實例 **1、在2.5億個整數中找出不重復的整數，注，內存不足以容納這2.5億個整數** **解法一**：采用2-Bitmap（每個數分配2bit，00表示不存在，01表示出現一次，10表示多次，11無意義）進行，共需內存2^32 * 2 bit=1 GB內存，還可以接受。然后掃描這2.5億個整數，查看Bitmap中相對應位，如果是00變01，01變10，10保持不變。所描完事后，查看bitmap，把對應位是01的整數輸出即可。 **解法二**：也可采用與第1題類似的方法，進行劃分小文件的方法。然后在小文件中找出不重復的整數，并排序。然后再進行歸并，注意去除重復的元素。” **2、給40億個不重復的unsigned int的整數，沒排過序的，然后再給一個數，如何快速判斷這個數是否在那40億個數當中？** **解法一**：可以用位圖/Bitmap的方法，申請512M的內存，一個bit位代表一個unsigned int值。讀入40億個數，設置相應的bit位，讀入要查詢的數，查看相應bit位是否為1，為1表示存在，為0表示不存在。