비트 벡터로 집합 만들기

unsigned long형이 32비트라고 가정.

• 정수를 구성하는 비트의 나열을 비트 벡터(bit vector)라고 함
  • 아래 비트부터 B0, B1, ..., B31이라고 할 때
  • 32비트의 부호가 없는 정수 하나로 {0, 1, ..., 31}을 전체 집합으로 표현 가능

 

• 매크로 SetOf(no)

typedef unsigned long BitSet;

#define SetOf(no)  ((BitSet)1 << (no))

유일한 원소가 no인 집합을 표현하는 비트 벡터를 만든다

 

 

• IsMember 함수

집합 s에 n값이 있는지 확인하기 위해 집합 s 비트 벡터와 {n} 비트 벡터를 논리곱(AND) 연산

-> 있으면 {n}, 없으면 0(공집합)

int IsMember (BitSet s, int n){
    return s & SetOf(n);
}

 

• Add 함수

집합 s에 n을 추가하기 위해서는 집합 s와 {n}을 논리합(OR) 연산

-> 집합 s의 n에 대응하는 비트가 0에서 1로 변경됨

void Add(BitSet* s, int n){
    *s |= SetOf(n);
}

 

• Remove 함수

집합 s에 n을 삭제하기 위해서는 집합 s와 {n}의 보수를 논리곱(AND) 연산

-> 집합 s의 n에 대응하는 비트가 1에서 0로 변경됨

void Remove(BitSet* s, int n){
    *s &= ~SetOf(n);
}

 

• Size 함수

집합 s의 원소의 개수를 반환하는 함수

s와 s-1을 논리곱(AND) 연산하면 가장 아래에 있는 비트 1이 0으로 바뀜

-> 이를 n번 반복해서 s와 s-1의 논리곱(AND) 결과가 0(공집합)이 되면 집합 s의 원소의 개수가 n이 됨

int Size(BitSet s){
    int n = 0;
    for(; s != (BitSet)0; n++)
    	s &= s-1;
    return n;
}

 

• Print 함수

void Print(BitSet s){
    int i;
    printf("{");
    for(i=0; i<32; i++)
    	if(IsMember(s, i)) printf("%d", i);
    printf("}");
}

 

• 두 집합 간의 연산

같은지 비교: s1 == s2, s1 != s2

교집합: s1 & s2

합집합: s1 | s2

차집합: s1 & ~s2