BitMap 의 원리 소개 와 실현

BitMap
비트 맵 (bitmap) 은 매우 자주 사용 되 는 구조 로 색인, 데이터 압축 등에 광범 위 하 게 응용 된다.비트 맵 은 배열 아래 표 시 를 응용 중의 일부 값 과 연결 시 켜 서 비 추 는 것 입 니 다. 배열 에서 이 아래 표 시 된 위치 에 있 는 요 소 는 중간 값 을 사용 하 는 상황 (존재 하거나 수량 이나 계수 등) 을 표시 할 수 있 습 니 다. 비트 맵 배열 에서 모든 요 소 는 메모리 에서 1 자 리 를 차지 하기 때문에 저장 공간 을 절약 할 수 있 습 니 다.비트 맵 은 매우 간결 하고 빠 른 데이터 구조 로 저장 공간 과 속 도 를 최적화 시 킬 수 있다.모든 요소 가 10 보다 작은 간단 한 비 마이너스 정수 집합 을 10 자리 길이 의 문자열 로 표시 할 수 있 습 니 다. 예 를 들 어 다음 문자열 로 집합 {1, 2, 4, 5, 8} 을 표시 할 수 있 습 니 다. 해당 위치 숫자 는 1 로 표시 되 어 있 습 니 다. 그렇지 않 으 면 0 으로 표시 할 수 있 습 니 다.
비트 맵 은 비트 단위 의 데이터 구조 에 데 이 터 를 저장 하 는 것 을 말한다.한 사람 당 0 과 1 두 개의 값 만 있다.0 일 때 는 증명 치가 존재 하지 않 고 1 일 때 는 존 재 를 설명 한다.
예 를 들 어:

[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

24 비트, 즉 24bit 이 며 8bit 는 1 바이트 입 니 다.이곳 의 공간 은 바로 세 개의 바이트 다.
이 럴 때 만약 우리 가 24689101719 21 이라는 숫자 를 우리 의 BitMap 에 저장 하려 고 한다 면 우 리 는 해당 하 는 위 치 를 1 로 설정 하면 된다.

[0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 1 1 0 1 0 1 0 1 0]

데이터 구조
만약 에 우리 가 저장 하고 자 하 는 데이터 범 위 는 0 - 15 이 고 이곳 의 데 이 터 는 16bit 입 니 다.

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
[0  0  0  0  0  0 0 0 0 0 0 0 0 0 0 0]

데 이 터 는 [5, 1, 7, 15, 0, 4, 6, 10] 이다.

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
[1  0  0  0  0  1 0 0 1 1 1 1 0 0 1 1]

예 를 들 면:
int 형 메모리 공간 을 신청 하면 4Byte, 32bit 가 있 습 니 다.입력 4, 2, 1, 3 시:
입력 4:
[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0]
입력 2:
[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0]
입력 1:
[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0]
입력 3:
[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0]
맵 맵 맵
정렬 하거나 찾 아야 할 총 N = 10000000 을 가정 하면 우리 가 신청 해 야 할 메모리 공간 은 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
……
변위 변환

10 진수 0 - N 에 대응 하 는 배열 a 의 아래 표 공식: index = N / 32 를 구하 면 됩 니 다. index 는 대응 하 는 배열 의 아래 표 입 니 다.예 를 들 어 N = 76 이면 index = 76 / 32 = 2 이기 때문에 76 은 a [2] 에 있다.

10 진수 0 - N 에 대응 하 는 bit 비트 비트 = N% 32 를 구하 면 됩 니 다. 예 를 들 어 N = 76, bit = 76% 32 = 12

이 위 0 - 31 을 이용 하여 대응 하 는 32bit 위 치 를 1

로 한다.
코드 구현

##include 
#include 

using namespace std;

class BitMap
{
public:
    BitMap( int range )
    {
        //    
        this->m_bits.resize(range / 32 + 1);
    }

    void set( int data )
    {
        int index = data / 32; //       
        int temp = data % 32; //      
        this->m_bits[index] |= ( 1 << temp); //  4   1
    }

    void reset( int data)
    {
        int index = data / 32;
        int temp = data % 32;
        this->m_bits[index] &= ~( 1 << temp ); //  
    }

    bool test(int data)
    {
        int index = data / 32;
        int temp = data % 32;
        if( this->m_bits[index]&( 1 << temp))
        {
            return true;
        }
        else
        {
            return false;
        }
    }

private:
    vector<int> m_bits;
};

void testBitMap()
{
    BitMap bitmap_1(-1);
    BitMap bitmap_2(31);
    bitmap_2.set(16);
    bitmap_2.set(1);
    cout<< bitmap_2.test(16) << endl;
    bitmap_2.reset(16);
    cout<< bitmap_2.test(16) << endl;
}


int main()
{
    testBitMap();
}