[Algorithm] 비트마스크

비트마스크

현대의 모든 CPU는 이진수를 이용하여 자료를 표현한다.

이러한 구조 덕분에 컴퓨터는 이진법 관련한 연산들을 아주 빠르고 쉽게 수행할 수 있다.

그리고 이 특성을 프로그래밍에서도 활용할 수 있는데, 그 활용 기법을 비트마스크라고 부른다.

 

비트마스크

 

비트마스크를 이용하면 다음과 같은 이점들을 얻을 수 있다.

1. 매우 빠른 시간에 동작한다.

2. 간결하게 코드를 작성할 수 있다.

3. 메모리 절약이 가능하다.

4. 중첩 컨테이너를 단순 컨테이너로 대체할 수 있다.

ex) 

// 기존
map<vector<bool>, int>

// 비트마스크 활용
vector<int> 

 

5. 집합 개념으로 활용될 수 있고 집합 관련한 연산들을 매우 쉽게 표현할 수 있다. (매우 중요)

ex)

다음과 N개의 원소가 있을 때, 이에 대한 모든 부분집합을 나열해보자.

vector<string> company = { "Apple", "Google", "Amazon", "Facebook" };

x
"Apple"
"Google"
"Amazon"
"Facebook"
"Apple", "Google"
"Apple", "Amazon"
"Apple", "Facebook"
"Google", "Amazon"
"Google", "Facebook"
"Amazon", "Facebook"
"Apple", "Google", "Amazon", 
"Apple", "Google", "Facebook"
"Apple", "Amazon", "Facebook"
"Google", "Amazon", "Facebook"
"Apple", "Google", "Amazon", "Facebook"

맨 위 공집합부터 맨 아래 전체집합까지 모든 원소들이 나열되었다.

이번에는 이진수를 0부터 15까지 나열해보자.

각각의 자리수의 비트가,

0이면 해당 위치 원소를 선택하지 않도록 하고,

1이면 해당 위치의 원소를 선택하도록 하여 위 원소들과 대응시키면 다음과 같이 나열될 것이다.

0		0000		x
1		0001		"Apple"
2		0010		"Google"
3		0011		"Amazon"
4		0100		"Facebook"
5		0101		"Apple", "Google"
6		0110		"Apple", "Amazon"
7		0111		"Apple", "Facebook"
8		1000		"Google", "Amazon"
9		1001		"Google", "Facebook"
10		1010		"Amazon", "Facebook"
11		1011		"Apple", "Google", "Amazon"
12		1100		"Apple", "Google", "Facebook"
13		1101		"Apple", "Amazon", "Facebook"
14		1110		"Google", "Amazon", "Facebook"
15		1111		"Apple", "Google", "Amazon", "Facebook"

즉, 비트마스크를 활용하면 모든 부분집합에 대한 구현을 굉장히 쉽게 처리할 수 있다.

 

 

기본 비트 연산

기본 비트 연산 예제이다.

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Bitmask/1-Bitmask.cpp

insooneelife/AlgorithmTutorial

 

주의할 점들

비트마스크 사용시 문제가 될 수 있는 상황들에 대한 예제이다.

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Bitmask/2-Bitmask-Error.cpp

insooneelife/AlgorithmTutorial

 

집합으로 활용

비트마스크를 집합으로서 이용하는 방법에 대한 예제이다.

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Bitmask/3-Bitmask-Set.cpp

insooneelife/AlgorithmTutorial