Page 294 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

실습 7-6[A] •완성 파일 chap07/BitSet.c
01 /* 비트 벡터에 의한 정수 집합 연산(소스) */
02 #include <stdio.h>
03 #include "BitSet.h"
04
05 /*--- 집합 s에 n이 들어 있는지 확인 ---*/
06 int IsMember (BitSet s, int n)
07 {
08 return s & SetOf(n);
09 }
10
11 /*--- 집합 s에 n을 추가 ---*/
12 void Add (BitSet *s, int n)
13 {
14 *s |= SetOf(n);
15 }
16 (실습 7-6[B]에서 계속)

원소가 들어 있는지 확인하는 IsMember 함수

IsMember 함수는 집합 s에 n 값이 들어 있는지 확인하는 함수입니다. 집합 s에 n 값이 들어
있는지 확인하는 방법은 집합 s 비트 벡터와 {n} 비트 벡터를 논리곱(AND) 연산하면 됩니다.
그림 7-14에 이 과정을 나타냈습니다. a 처럼 집합에 n이 들어 있는 경우 비트 벡터 s와 n으
로 논리곱 연산을 하면 {n}이 나옵니다. 반대의 경우로 b 처럼 집합에 n이 들어 있지 않은 경

우 논리곱 연산을 하면 공집합이 나옵니다. 다시 말해 집합 s에 n 값이 없다면 모든 비트가 0
인 배열이 나옵니다. C 언어에서 1은 참, 0은 거짓입니다. 따라서 다음과 같이 IsMember 함
수를 그대로 if문에 사용할 수 있습니다.

a 집합 {1, 3, 5, 6}에 6이 들어 있는지 확인합니다. b 집합 {1, 3, 5, 6}에 4가 들어 있는지 확인합니다.

３１ ３０ ９ ８ ７ ６ ５ ４ 3 ２ １ ０ ３１ ３０ ９ ８ ７ ６ ５ ４ ３ ２ １ ０
s 0 0 0 0 0 1 1 0 1 0 1 0 s 0 0 0 0 0 1 1 0 1 0 1 0
SetOf(n) 0 0 0 0 0 1 0 0 0 0 0 0 SetOf(n) 0 0 0 0 0 0 0 1 0 0 0 0
& &
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
논리곱(AND) 연산을 통해 이 비트만 논리곱(AND) 연산을 통해 모든
1이 됩니다. 비트가 0이 됩니다.
즉, n은 s 안에 들어 있습니다. 즉, n은 s 안에 들어 있지 않습니다.

[그림 7-14] IsMember 함수로 n이 있는지 확인하는 과정

294 C 알고리즘