ビットマップ

1.ビットマップとは?
『プログラミング珠玉』から来ました.Bit-mapとは、ある要素に対応するValueをビットでマークするもので、Keyはその要素です.Bitを単位としてデータを格納するため、記憶空間においても大幅に節約できる.
例えば、int型の空間を申請すると、4 Bytte、32 bitがあります.入力1,2,3,4 0000 0000 0000,000入力1,000 000,000 000,000,000,000入力2,000,000入力2 0000,000入力3 0000,0000入力3,000 0000 0000,0110入力4,000 0000入力4 0000,000入力4,000 0000入力0000,010入力4,000,000入力0000
2.mapマップテーブル
並べ替えまたは検索が必要な範囲が0～1000であれば、申請するメモリ空間はint a[N/32+1].そのうちa[0]はメモリに32桁を占め、これに類推する.bitmapはa[0]0~31 a[1]32~63 a[2]64~95 a[3]96~127…
3.シフト変換
(1)10進数0-Nに対応する配列aの下付きindex=N/32を求めると良いです.indexはnに対応する配列下付きです.
(2)十進数-Nに対応するビットpos=N%32を求めると良いです.
(3)対応する32 bitビットを0-31シフトで1にする
4.コード実現(c++)

#pragma once
#include 
#include 
using namespace std;

class BitMap
{
public:
    BitMap(size_t range)   //            
    {
        _bitmap.resize(range / 32 + 1);  //    
    }

    void Set(size_t num)  //  1
    {
        size_t index = num / 32;        //    
        size_t pos = num % 32;          //    
        _bitmap[index] |= (1 << pos);   
    }

    void Reset(size_t num)  //  0 
    {
        size_t index = num / 32;
        size_t pos = num % 32;
        _bitmap[index] &= (~(1 << pos));
    }

    bool Test(size_t num)  //     
    {
        size_t index = num / 32;
        size_t pos = num % 32;
        return _bitmap[index] & (1 << pos);
    }

protected:
    vector _bitmap;
};

void TestBitMap()
{
    BitMap bm(1000);
    bm.Set(1);
    bm.Reset(1);
    bm.Set(2);
    bm.Set(3);
    bm.Set(12);
    cout<1)<cout<2)<