[Algorithm/C++] 비트마스크 (BitMask) 란?

비트는 이진숫자(binary digit) 를 뜻하는 말로 컴퓨터에서 사용하는 데이터의 최소 단위를 의미합니다.

비트는 0/1 , true/false, on/off 상태를 나타낼 수 있습니다. 

 

비트 마스크(BitMask) 는 이러한 비트의 형태를 활용해, 정수의 이진수를 표현을 활용하는 기법입니다. 

예시

길이가 5인 집합 {0,1,2,3,4} 가 존재한다고 가정합니다.

우리는 여기서 몇 가지 요소를 뽑아 어떤 요소를 선택했는지 부분집합을 사용해 표현할 수 있습니다. 

{ 1, 2, 3, 4 }, { 1, 2, 4 }, { 2, 4 }, { 1 } .......

 

위와 같은 형태로, Integer 형으로 인덱스를 활용할 수 있다면, 단순히 boolean 배열을 통해 구현할 수도 있습니다.

int[] array1 = [1, 1, 1, 1, 0]; 
int[] array2 = [1, 1, 0, 1, 0]; 
int[] array3 = [1, 0, 1, 0, 0];

하지만 위와 같은 형태는 메모리를 많이 차지해 오버헤드가 증가합니다.

이는 비트마스크를 통해 더욱 효율적이게 처리할 수 있습니다.

{ 0, 1, 2, 3, 4 } => 11111
{ 1, 2, 3, 4 } => 11110
{ 1, 2, 4 } => 10110
{ 2, 4 } => 10100
{ 1 } => 00010

위와 같은 표현 기법 (비트마스크) 는 각 요소를 인덱스처럼 표현합니다.

즉 집합 n번째 원소가 존재하면 1을, 그렇지 않으면 0을 반환합니다.

장점

1. 더 빠른 수행 시간을 보장합니다.

2. 더 간결한 코드를 제공합니다.

3. 메모리 사용량을 줄일 수 있습니다.

* 알고리즘 문제를 풀 때에는 원소의 수가 적을 경우에 유용합니다.

주의 사항

1. 연산자 우선 순위가 낮기 때문에 괄호를 치는 습관을 가지는 것이 좋습니다.

2. 1은 부호있는 32bit 상수로 취급하므로 32bit 가 넘어가는 수 표현에서는 오류가 날 수 있습니다.

3. 부호 있는 정수형에서 최상위 비트가 켜진 숫자는 음수를 표현합니다. 

비트 연산

1. AND(&) : 대응하는 두 비트가 모두 1일 때에만 1 반환

2. OR(|) : 대응하는 두 비트가 모두 1이거나 하나라도 1일 경우 1 반환

3. XOR(^) : 대응하는 두 비트가 서로 다를 때 1 반환

4. NOT(~) : 비트 값을 전환하여 반환

5. SHIFT(>>, <<) : 왼쪽 혹은 오른쪽으로 비트를 옮겨 반환