비트벡터(BitVector) 이용하기
개발 2007. 10. 17. 17:33제목 : 비트벡터 이용하기
날짜 : 2007-10-02
저자 : hanburn
데이터를 표현할 때 비트단위를 이용하면 효율적인 경우가 있다. 요즘처럼 메모리도 많아지고 CPU도 빨라진 상황에서 굳이 비트단위의 연산을 사용할 필요가 있나 라고 생각할 수도 있지만 상황에 따라서 사용하면 상당히 효과적인 경우가 있다. 예를 들어서 2, 5, 8, 10, 14 19 이렇게 6개의 숫자를 저장해야 한다고 할 때 다음과 같이 표현될 수 있다.
앞에서부터 각각의 비트는 0,1,2,3,... 을 나타내는 표현방식으로 3번째 비트가 참이므로 2를 의미하게 된다. 20이하의 숫자이므로 3Byte로(3*8=24 : 24까지 표현가능) 표현을 할 수가 있는 것이다. 6개의 int를 저장하려면 4*6=24Bytye 가 필요한것에 피하면 21Byte가 절약이 된것이다. 1백만 이하의 숫자를 저장하는데는 1백만 비트가 필요하므로 125000 바이트가(약 125KB) 필요하게 된다. 그냥 4Byte 의 숫자 1백만개를 저장하려면 4백만 바이트 (약 4MB)의 공간이 필요하다. 메모리 사용측면에서 엄청난 효율이다. 더욱이 사용하는 메모리가 줄어들면 속도도 빨라지는 이점이 있으므로 상당히 괜찮은 방법이다.
하지만 몇가지 제약사항이 있는데, 다음과 같다.
첫째, 중복되는 숫자가 있으면 안 된다.
둘째, 상대적으로 작은 숫자의 범위
셋째, 숫자와 연관되는 데이터가 없어야 한다.
그러면 이러한 비트형태의 데이터를 표현하기 위해서는 어떻게 하면 좋을까?
보통의 경우라면 C++ 의 표준라이브러리에서(STL) 제공하는 vector<bool> 을 이용하는 것이 좋은 방법이고, 환경적인 요인으로 C++의 STL을 사용할 수 없다면 다음과 같이 간단하게 구현하여 사용 할 수 있을 것이다. 간단한 클래스라서 C 함수로 변경도 쉬울 것이다.
// BitVector.h 파일
#define BITPERWORD 32
#define SHIFT_FIVE 5
#define MASK_BYTE 0x1F // 0001 1111
#define BITCOUNT 1000000
class CBitVector
{
public:
CBitVector(){}
~CBitVector(){}
void SetBit(int i)
{
bitVector[i>>SHIFT_FIVE] |= ( 1<<(i&MASK_BYTE) );
}
void ClearBit(int i)
{
bitVector[i>>SHIFT_FIVE] &= ~( 1<<(i&MASK_BYTE) );
}
int GetBit(int i)
{
return bitVector[i>>SHIFT_FIVE] & ( 1<<(i&MASK_BYTE) );
}
protected:
int bitVector[BITCOUNT/BITPERWORD+1];
private:
};
위의 클래스를 사용하는 예는 다음과 같다.
BOOL bit;
CBitVector bitVector;
bitVector.SetBit(5);
bit = bitVector.GetBit(5);
bitVector.ClearBit(5);
bit = bitVector.GetBit(5);
5번째 비트를 설정하고 그값을 확인하고 다시 5번째 비트를 해제하고 값을 확인하는 간단한 코드이다.
정리하면, 비트벡터는 적절한 경우에 사용하면 메모리와 수행성능에서 좋은 결과를 보여준다. 다만 사용할 때 몇 가지 제약사항이 있고, 나중에 프로그램이 변경되어서(요구사항 변경으로) 비트벡터로 저장된 값이 다른데이터와 연관이 생기는 경우에는 대폭적인 수정이 필요 할 수도 있다.
비트벡터라는 개념과 사용시의 주의점을 알아두고 나중에 필요할 때 한번씩 사용을 해보자.