[알고리즘] 비트마스킹(bitmasking) 이란

안녕하세요, 여행벌입니다.

오늘은 2진수 표기법의 특징을 활용한 비트마스킹 알고리즘에 대해서 포스팅해보겠습니다.

---

[ 비트마스킹 ]

 컴퓨터는 내부적으로 모든 자료를 이진수로 표현합니다. 이와 같은 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법을 비트 마스크라고 합니다.

 비트 마스크를 이용하면 더 빠른 수행 시간, 더 간결한 코드, 더 적은 메모리 사용이라는 효과를 얻을 수 있습니다.

비트 연산자

 비트마스킹은 기본적으로 비트를 다뤄야 하므로, 비트 연산자에 대해서 먼저 간단하게 알아보겠습니다.

a & b	a의 모든 비트와 b의 모든 비트를 AND연산한다. 둘다 1이라면 1, 아니면 0	ex) a = 4 = 100(2) b = 7 = 111(2) a & b = 100(2) = 4
a | b	a의 모든 비트와 b의 모든 비트를 OR연산한다. 둘다 0이라면 0, 아니면 1	ex)  a = 2 = 010(2) b = 5 = 101(2) a | b = 111(2) = 7
a ^ b	a의 모든 비트와 b의 모든 비트를 XOR연산한다. 둘이 다르다면 1, 아니면 0	ex) a = 3 = 011(2) b = 5 = 101(2) a ^ b = 110(2) = 6
~a	a의 모든 비트에 NOT 연산을 한다. 0이면 1, 1이면 0	ex) 3비트라고 가정 a = 3 = 011(2) ~a  = 100(2) = 4
a << b	a를 b비트 만큼 왼쪽으로 시프트	ex)  a = 1 = 001(2) a << 2 = 100(2) = 4
a >> b	a를 b비트 만큼 오른쪽으로 시프트	ex) a = 4 = 100(2) a >> 2 =  001(2) = 1

집합의 표현

 비트마스크를 이용하면 집합을 쉽게 표현할 수 있습니다. 또, 집합에 원소를 추가, 삭제하는 등 다양한 연산을 굉장히 빠르게 수행할 수 있습니다.

 

 그럼 비트를 이용해서 어떻게 집합을 표현할 수 있을까요? 원소의 개수가 N인 집합이 있다고 하면, 각각의 원소를 0번부터 (N-1)번 까지 번호를 부여하고, 번호에 해당하는 비트가 1이면 원소가 포함, 0이면 원소가 불포함이라고 한다면 집합을 비트를 이용해 표현할 수 있습니다.

 

 예를 들어, { A, B, C, D, E, F, G } 집합이 있다고 하겠습니다.

총 7개의 원소가 존재하므로 우리는 7개의 비트로 이 집합을 표현할 수 있습니다. 즉, 각 원소마다 비트를 하나씩 대응시켜서 원소가 존재한다면 1, 존재하지 않다면 0으로 표현해보겠습니다.

예를 들어, { A } 라는 부분집합은 64 = 1000000(2) 로 표현하고 { C, F } 는 18 = 0010010(2) 로 표현할 것입니다.

원소 추가

 현재 상태 cur이 있을 때, p번 원소를 추가한다고 해보겠습니다. 그럼, 현재 상태 cur에서 p번 비트를 1로 바꿔줘야 됩니다. a | b 비트연산자를 활용하면 쉽게 해결할 수 있습니다.

cur = cur | (1 << p)

 1 << p를 통해서 p번 비트만 1, 나머지 비트는 0인 값을 만들고 | 연산을 진행한다면 cur의 p번 비트는 1로 바뀌게 되고, 나머지 비트는 원래 상태를 유지하게 됩니다.

원소 삭제

 원소를 삭제하는 연산도 쉽게 구현할 수 있습니다. 현재 상태 cur에서 p번 원소를 삭제한다고 생각해보겠습니다. 그러면, p번 비트를 0으로 바꿔줘야됩니다.

cur = cur & ~(1 << p);

 1 << p 를 통해서 p번 비트만 1, 나머지 비트는 0으로 만듭니다. 그 후, ~ 연산을 통해 p번 비트만 0, 나머지 비트는 1로 만들고 & 연산을 진행한다면 p번 비트만 0으로 바뀌고 나머지는 현재 상태 cur과 동일하게 유지할 수 있습니다.

원소 토글

 p번 비트가 1이면 0, 0이면 1로 바꾸는 토글 연산도 쉽게 구현할 수 있습니다. 현재 상태 cur에서 p번 원소가 있다면 삭제하고, 없다면 추가해보겠습니다.

cur = cur ^ (1 << p);

 1 << p 를 통해서 p번 비트만 1, 나머지 비트는 0으로 만듭니다. cur의 나머지 비트들은 0과 XOR 연산을 진행하므로 0이면 0, 1이면 1로 현재 상태를 유지하게 되고, p번 비트는 1과 XOR 연산을 진행하므로 1이면 0, 0이면 1로 토글이 됩니다.

집합 연산(합집합)

 비트마스킹을 이용하면 원소를 추가, 삭제, 토글 하는 연산 외에도 합집합, 교집합, 차집합 등등을 쉽게 구할 수 있습니다.

a | b; // a 와 b의 합집합
a & b; // a 와 b의 교집합
a & ~b; // a 에서 b를 뺀 차집합
a ^ b; // a와 b 중 하나에만 포함된 원소들의 집합

 A집합을 나타내는 a와 B집합을 나타내는 b가 있을 때, 둘이 | 연산을 하게 된다면 존재하는 원소들의 비트는 모두 1로 켜지게 되고, 두 집합에 모두 없는 원소들만 비트가 0이 됩니다. 따라서, 합집합 연산이 됩니다.

 마찬가지로 & 연산을 하게 되면, 두 집합에 모두 존재하는 원소들의 비트만 1과 1을 AND 연산하게 되므로 1로 살아남고, 나머지는 0이 됩니다. 따라서 교집합 연산이 됩니다.

 a & ~b 연산을 하게 되면 a 집합과 b의 여집합과 & 연산을 하게 됩니다. 즉, A - B 인 차집합 연산이 됩니다.

 마지막으로, ^ 연산을 하게 되면 둘 중 하나에만 포함된 원소들만 1로 살아남게 됩니다.

집합의 크기 구하기

 집합의 크기를 구하려면, 현재 1로 켜져 있는 비트의 수를 count 해야 됩니다. 따라서, 모든 비트를 순회해야 되고 재귀적으로 다음과 같이 구현할 수 있습니다.

int bitCount(int x){
	if(x == 0) return 0;
	return x % 2 + bitCount(x / 2);
}

 x % 2 를 하면 마지막 비트를 얻게 되고, x / 2 를 하게 되면 마지막 비트를 삭제할 수 있습니다. 따라서, 모든 비트를 재귀적으로 순회할 수 있습니다.

모든 부분 집합 순회하기

 어떤 집합의 모든 부분 집합을 순회하는 과정도 정말 간단하게 구현할 수 있습니다.

for(int subset = set; subset; subset = (subset - 1) & set){
	// subset은 set의 부분집합 중 하나.
}

 예를 들어, { A, B, D } 를 포함한 집합을 생각해보겠습니다.

 모든 부분 집합은 공집합을 제외하고 { A }, { B }, { D }, { A, B }, { A, D }, { B, D }, { A, B, D } 가 존재합니다.

 비트로 표현하면 다음과 같습니다.

{ A, B, D }	1101(2)
{ A, B }	1100(2)
{ A, D }	1001(2)
{ B, D }	0101(2)
{ A }	1000(2)
{ B }	0100(2)
{ D }	0001(2)

 위에서 구현한 코드를 한 번 따라가 보겠습니다. set = 1101(2) = { A, B, D } 입니다.

subset	(subset - 1)	(subset - 1) & set
1101(2) // { A B D }	1100(2)	1100(2)
1100(2) // { A B }	1011(2)	1001(2)
1001(2) // { A D }	1000(2)	1000(2)
1000(2) // { A }	0111(2)	0101(2)
0101(2) // { B D }	0100(2)	0100(2)
0100(2) // { B }	0011(2)	0001(2)
0001(2) // { D }	0000(2)	0000(2) // 종료

 for문을 통해 모든 부분 집합을 다 순회하는 것을 확인할 수 있습니다.

---

 위처럼 비트마스크를 이용하면 집합의 표현, 원소 추가, 원소 삭제, 원소 토글, 합집합, 교집합, 차집합 등등 다양한 연산들을 어떤 자료구조보다 빠르게 구현할 수 있습니다.