비트 벡터(Beat Vector)

비트 벡터란

비트 벡터란 중복되지 않는 정수 집합을 비트로 나타내는 방식이다.
8bit가 1byte이므로 0 ~ 7까지의 8개의 정수 집합은 고작 1byte 공간만 사용하여 데이터를 저장할 수 있다. 따라서 비트 벡터를 이용하면 최소의 저장 공간만 이용하는 장점이 있다.

비트 연산자

비트 벡터를 구현을 위해서 비트 연산자를 숙지해야 한다.

• AND(논리곱 연산)
  0 & 0 -> 0
  1 & 0 -> 0
  0 & 1 -> 0
  1 & 1 -> 1
  지정한 비트값을 0으로 만들고자 할때 사용

• OR(논리합 연산)
  0 | 0 -> 0
  1 | 0 -> 1
  0 | 1 -> 1
  1 | 1 -> 1
  지정한 비트값을 1로 만들고자 할때 사용

• left shift(<<)
  1 << 3
  0000 0001 -> 0001 1000
  연산자 왼쪽에 위치한 비트 값에 대해 연산자 오른쪽에 위치한 수 만큼 왼쪽으로 이동

• right shift(>>)
  3 >> 5
  0000 1000 -> 0010 0000
  연산자 왼쪽에 위치한 비트 값에 대해 연산자 오른쪽에 위치한 수 만큼 오른쪽으로 이동

비트 벡터로 집합 만들기

unsigned long형이 32비트라고 가정하면, 이때 정수를 구성하는 비트의 나열을 비트 벡터라고 하자. 아래쪽 비트부터 시작하여, 집합의 원소의 유무의 따라 1, 0으로 표시한다. 그러면 32비트의 부호가 없는 정수로 그림과 같은 {1, 5, 30} 전체 집합을 표현할수 있다.

비트 벡터로 집합을 구현하는 프로그램

• BitSet.h 헤더파일

/* 비트 벡터 집합 BitSet(헤더 부분) */
#ifndef ___BitSet
#define ___BitSet

typedef unsigned long BitSet;			/* 집합을 나타내는 형 */

#define BitSetNull    (BitSet)0			/* 공집합 */
#define BitSetBits     32			/* 유효 비트 수 */
#define SetOf(no)  ((BitSet)1 << (no))		/* 집합 {no} */

/*--- 집합 s에 n이 있는지 확인 ---*/
int IsMember(BitSet s, int n);

/*--- 집합 s에 n을 추가 ---*/
void Add(BitSet* s, int n);

/*--- 집합 s에서 n을 삭제 ---*/
void Remove(BitSet* s, int n);

/*--- 집합 s의 원소 개수를 반환 ---*/
int Size(BitSet s);

/*--- 집합 s의 모든 원소를 ​​출력 ---*/
void Print(BitSet s);

/*--- 집합 s의 모든 원소를 ​​출력(줄 바꿈 문자 포함) ---*/
void PrintLn(BitSet s);

#endif

• 이 프로그램에서 정의한 자료형과 매크로

1. BitSet형
   BitSet는 비트 벡터를 나타내는 자료형(집합), typedef 선언으로 unsigned long형과 동일하게 정의

2. BitSetNull
   객체형 매크로 BitSetNull은 공집합의 비트 벡터를 나타내는 정수, 모든 비트가 0(unsigned long형)

3. BitSetBits
   객체형 매크로 BitSetBits는 비트 벡터에서 유효한 비트 수를 나타냄, 여기서는 unsigned long형 비트의 아래쪽 32비트만 사용하므로 32로 정의

4. SetOf(no)
   함수 형식의 매크로 SetOf는 유일한 원소가 no인 집합{no}를 표현하는 비트 벡터를 만든다. 가장 아래쪽 비트의 값이 1인 집합 {0}에서 비트를 왼쪽으로 no만큼 shift하여 집합 {no}를 만든다.

• BitSet.c 소스파일

/* 비트 벡터에 의한 정수 집합 연산(소스 부분) */
#include <stdio.h>
#include "BitSet.h"

/*--- 집합 s에 n이 들어있는지 확인 ---*/
int IsMember(BitSet s, int n)
{
	return s & SetOf(n);
}

/*--- 집합 s에 n을 추가 ---*/
void Add(BitSet* s, int n)
{
	*s |= SetOf(n);
}

/*--- 집합 s에서 n을 삭제 ---*/
void Remove(BitSet* s, int n)
{
	*s &= ~SetOf(n);
}

/*--- 집합 s의 원소 개수를 반환 ---*/
int Size(BitSet s)
{
	int n = 0;
	for (; s != BitSetNull; n++)
		s &= s - 1;
	return n;
}

/*--- 집합 s의 모든 원소를 ​​출력 ---*/
void Print(BitSet s)
{
	int i;
	printf("{ ");
	for (i = 0; i < BitSetBits; i++)
		if (IsMember(s, i))
			printf("%d ", i);
	printf("}");
}

/*--- 집합 s의 모든 원소를 ​​출력(줄 바꿈 문자 포함) ---*/
void PrintLn(BitSet s)
{
	Print(s);
	putchar('\n');
}

1. IsMember 함수(원소가 들어 있는지 확인)
   집합 s에 n값이 들어 있는지 확인하는 함수이며, 집합 s 비트 벡터와 {n} 비트 벡터 를 논리곱(AND) 연산한다.

2. Add 함수(원소를 추가)
   Add 함수는 집합 s에 n을 추가하는 함수이다. 집합 s 비트 벡터와 SetOf(n)으로 얻는 논리합(OR) 연산한다.

3. Remove 함수(원소를 삭제)
   집합 s에서 n을 삭제한다. 집합 s의 비트 벡터와 SeOf(n)으로 얻은 비트 벡터의 보수로 논리곱 연산을 하면 n이 삭제된다.

4. Size 함수(원소 개수를 반환)
   집합의 원소 개수는 비트 벡터 안의 '1'인 비트가 몇개인지 알아내면 된다. s에서 1을 뺀 s - 1과 논리곱 연산을 하면 s에서 가장 아래쪽 비트가 0으로 바뀐다. 따라서 s &= s - 1을 반복하여 가장 아래쪽의 1인 비트가 차례로 삭제되어 모든 비트가 0이 될때, 이 연산 횟수가 집합의 원소 개수가 된다.

• BitSetTest.c 소스파일
  s1과 s2를 사용해 대화형으로 다양한 집합 연산을 수행하는 프로그램

/* 비트 벡터로 정수 집합 표현 */
#include <stdio.h>
#include "BitSet.h"

enum { ADD, RMV, SCH };

/*--- 데이터 입력 ---*/
int scan_data(int sw)
{
	int data;

	switch (sw) {
	case ADD: printf("추가할 데이터 : "); break;
	case RMV: printf("삭제할 데이터 : "); break;
	case SCH: printf("검색할 데이터 : "); break;
	}

	scanf("%d", &data);

	return data;
}

int main(void)
{
	BitSet s1 = BitSetNull;
	BitSet s2 = BitSetNull;

#define BitSetNull    (BitSet)0			/* 공집합 */
#define BitSetBits     32			/* 유효 비트 수 */
#define SetOf(no)  ((BitSet)1 << (no))		/* 집합 {no} */


	while (1) {
		int m, x, idx;

		printf("s1 = "); PrintLn(s1);
		printf("s2 = "); PrintLn(s2);
		printf("(1) s1에 추가 (2) s1에서 삭제 (3) s1에서 검색 (4) s1←s2 (5) 여러 연산\n"
			"(6) s2에 추가 (7) s2에서 삭제 (8) s2에서 검색 (9) s2←s1 (0) 종료 : ");
		scanf("%d", &m);
		if (m == 0) break;
		switch (m) {
		case 1: x = scan_data(ADD); Add(&s1, x);	break; 	/* 추가 */
		case 2: x = scan_data(RMV); Remove(&s1, x);	break; 	/* 삭제 */
		case 3: x = scan_data(SCH); idx = IsMember(s1, x);	/* 검색 */
			printf("s1에 들어있%s.\n", idx != 0 ? "습니다" : "지 않습니다"); break;
		case 4: s1 = s2; break;								/* s2를 s1에 대입 */
		case 5: printf("s1 == s2 = %s\n", s1 == s2 ? "true" : "false");
			printf("s1 & s2 = "); PrintLn(s1 & s2);
			printf("s1 | s2 = "); PrintLn(s1 | s2);
			printf("s1 - s2 = "); PrintLn(s1 & ~s2);
			break;
		case 6: x = scan_data(ADD); Add(&s2, x); break;		/* 추가 */
		case 7: x = scan_data(RMV); Remove(&s2, x); break;	/* 삭제 */
		case 8: x = scan_data(SCH); idx = IsMember(s2, x);	/* 검색 */
			printf("s2에 들어있%s.\n", idx != 0 ? "습니다" : "지 않습니다"); break;
		case 9: s2 = s1; break;								/* s1을 s2에 대입 */
		}
	}

	return 0;
}