[Data Structure] bitmap

Bitmap

Implementation

 #pragma once#include#includeusing namespace std;class BitMap{public: BitMap(size_t range) {_bitMap.resize((range>>5) +1);} void Set(size_t x) { size_t index=x>>5; size_t num =x%32; /*size_t tmp=1; tmp<<=num;*/ //_bitMap[index]|=tmp; _bitMap[index]=(1<>5; size_t num =x%32; size_t tmp=0; tmp<<=num; _bitMap[index] &=(~(tmp));} bool Test(size_t x) {size_t index=x>>5; size_t num = x%32; size_t tmp=1; tmp<<=num; _bitMap[index] &=tmp; return _bitMap[index];} ~BitMap () {}protected: vector _bitMap;};void test(){ BitMap bm1(10 24); bm1.Set(33); bm1.Set(333); cout<

From "Programming Pearls". The so-called Bit-map is to use a bit to mark the Value corresponding to an element, and the Key is the element. Due to the use of Bit as a unit to store data, the storage space can be greatly saved. 
If you have said so much and still don’t understand what Bit-map is, then let’s look at a specific example. Suppose we want to The 5 elements (4,7,2,5,3) within 0-7 are sorted (here we assume that these elements are not repeated). Then we can use the Bit-map method to achieve the purpose of sorting. To express 8 numbers, we only need 8 Bits (1Bytes). First, we open up 1Byte space and set all Bit bits in these spaces to 0
then traverse these 5 elements, first the first element is 4, then the position corresponding to 4 is 1 (you can do this p+(i/8)|(0×01<<( i%8)) Of course, the operation here involves Big-ending and Little-ending, here the default is Big-ending), because it starts from zero, so set the fifth position to 1. 
Then process the second element 7, set the eighth position to 1, and then process the third element until Finally, after processing all the elements, set the corresponding position to 1. 
Then we now traverse the Bit area and output the number of the bit that is one (2, 3, 4, 5, 7) In this way, the purpose of sorting is achieved. 
In fact, each unit of the statistical array used for counting and sorting is reduced to a bit-level boolean array