[Data_Structure] 비트 마스킹

비트마스킹을 사용하면 대상이 2가지 state를 나타내는 경우(켜져있다/꺼져있다, 있다/없다, 포함한다/포함하지 않는다 등..)의 문제를 쉽게 해결할 수 있다.

0부터 9까지의 정수를 원소로 가질 수 있는
집합 S가 있다고 가정하고 이를 비트마스킹을 통해 표현해보자.

1. 공집합과 전체 집합 구하기

int S_zero = 0; //  공집합 ==>  0000000000
int S_full = (1<<10) -1; //전체 집합 ==> 1111111111

공집합은 너무 당연하므로 넘어가고,

전체 집합의 경우 1<<10은 1을 10bit만큼 왼쪽으로 이동시킨 것이므로

여기서 1을 빼면 0부터 9까지 모두 1이 된다.

2. 원소 추가

S |= (1<<p);

만약 p번째 원소를 추가하고 싶다면, 왼쪽으로 p비트 shift하면 p번 비트만 1이된 정수가 되므로 이를 집합 S에 OR하면 해당 비트는 반드시 켜지게 된다.

3. 원소의 포함 여부 확인

1. if(S & ( 1 << p) )


2. if( (S & ( 1 << p ) ) == 1) // 제대로 동작하지 않는다.

집합 S가 p번째 원소를 포함하는지를 확인하고 싶다면 1을 p만큼 왼쪽으로 shift한 뒤, AND 연산을 수행하자. 만약 S가 p번째 원소를 포함했다면 1<<p를, 그렇지 않았다면 0을 반환한다.


두 번째와 같이, 논리 연산자처럼 true, false가 반환된다고 착각하면 안 된다.
bit연산자 임에 주의하자.

4. 원소의 삭제

S &= ~(1<<p);

'~'연산자는 비트별 NOT 연산을 수행하므로, ~(1 << p)는 p번 비트를 제외한 나머지 비트를 1로 바꾼다. 따라서 이 숫자와 AND 연산을 수행하면, p번 비트는 반드시 0이 된다.

5. 원소의 토글

S ^= (1<<p)

XOR을 사용하면 해당 비트가 1이면 0으로, 0이면 1로 바꿀 수 있음을 활용한다.

6. 두 집합에 대한 연산

int add = (a|b); // a+b인 합집합
int intersect = (a&b); // a, b의 교집합
int remove = (a& ~b); // a-b인 차집합
int toggle = (a^b) // a와 b중 하나에만 포함된 원소들의 집합(교집합 제외)

7. 모든 부분 집합 순회하기

for(int subset = pizza; subset; subset = ((subset -1) & pizza)) {
	...
}

만약 pizza가 {페퍼로니, 소시지, 양파}라면, {페퍼로니}, {페퍼로니, 소시지}, {페퍼로니, 양파} 등 모든 부분 집합을 순회할 수 있다.
subset에서 1을 빼가는데, 이때 순회의 대상인 pizza와 AND 연산을 통해 pizza에 속하지 않는 연산은 모두 0으로 만들기 때문에 pizza의 모든 부분 집합을 순회할 수 있다. 만약 배열을 사용한다면 재귀 함수를 작성해야했을 것이다.

참조: 프로그래밍 대회에서 배우는 알고리즘 해결 전략2