【数据结构】位图

位图（bitmap），就是用一块内存区域的每个比特表示一个对象的数据结构。

优点是速度快，内存空间占用小，能表示大范围的数据。

假设要对0到一千万范围内的、没有重复元素的正整数排序，则利用位图数据结构很合适。

应用场景：
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。
思路：如果内存够的话，40亿个整型使用位图存储需要500M左右的空间。

#pragma once 
#include <assert.h>
 class Bitmap { public: Bitmap(size_t N) { _size = N / 32 + 1; _array = new size_t[_size]; memset(_array,sizeof(size_t)*_size); } ~Bitmap() { delete[] _array; } public: void Set(size_t num) { size_t index = num / 32; size_t pos = num % 32; assert(index < _size); _array[index] |= (1<<(32-pos)); } void Reset(size_t num) { size_t index = num / 32; size_t pos = num % 32; assert(index < _size); _array[index] &= ~(1<<(32-pos)); } void Clear() { memset(_array,sizeof(size_t)*_size); } bool Test(size_t num) { size_t index = num / 32; size_t pos = num % 32; assert(index < _size); return _array[index] & (1<<(32-pos)); } private: size_t* _array; size_t _size; }; void Test1() { Bitmap bs(100); bs.Set(9); bs.Set(10); bs.Set(40); cout<<"Test 10?"<<bs.Test(10)<<endl; cout<<"Test 21?"<<bs.Test(21)<<endl; cout<<"Test 40?"<<bs.Test(40)<<endl; cout<<"Test 41?"<<bs.Test(41)<<endl; bs.Reset(10); cout<<"Test Reset 10?"<<bs.Test(10)<<endl; } void Test2() { Bitmap bs(-1); }