비트마스크(BitMask)
이진수 표현을 자료구조로 사용하는 기법이다.
하나의 비트에서 나타낼 수 있는 경우의 수는 0 혹은 1 두가지가 있다.
보통 비트마스크를 이용하는 경우에 0이면 false, 1이면 true를 나타내며, 특정 집합에서 원소의 포함 여부를 표현할 때 사용한다.
비트단위로 정보를 처리하기 때문에 메모리를 적게 사용할 뿐만 아니라 수행 속도가 빠르다는 장점이 있다.
비트 연산
비트마스크는 비트 연산을 이용하여 집합 내의 원소를 다룰 때 주로 사용된다.
예를 들어, 0부터 9까지 넣을 수 있는 어떠한 집합 S가 존재하고 그 집합 내에 들어있는 원소가 0,1,2 이라고 하자.
만약 배열로 이를 표현한다고 하면,
10개의 크기를 가지는 boolean 배열을 생성하고,
arr[0] = true
arr[1] = true
arr[2] = true
arr[3] = false
arr[4] = false
arr[5] = false
arr[6] = false
arr[7] = false
arr[8] = false
arr[9] = false
로 표현할 수 있다. 이렇게 배열로 나타내기 위해서는 배열의 크기 10 x 1byte = 10byte가 필요하다.
비트마스크를 사용하여 집합을 표현하면 어떻게 나타낼 수 있을까?
각 비트는 0부터 9까지의 포함 여부를 1혹은 0으로 나타낼 수 있다.
만약 위의 집합 상태를 비트마스크로 표현한다면 아래처럼 나타낼 수 있을 것이다.
이 경우, 총 10bit만 필요하다. 10bit만으로 집합의 상태를 표현하였다.
즉, 비트마스크를 사용하면 메모리가 훨씬 절약되며, 비트 연산을 하므로 수행 속도도 빠르다.
집합을 표현하기 위해서 필요한 몇가지 동작이 존재한다.
집합에 새로운 원소를 삽입하거나, 혹은 삭제할 수도 있으며, 집합에 특정 원소가 포함되어 있는지 여부를 확인할 수도 있을 것이다.
이러한 동작들은 비트 연산을 이용하여 나타낼 수 있다.
비스마스크를 이용한 집합 표현
공집합 : S = 0
집합이 공집합인 경우, 모든 비트가 0이 된다. 따라서 S = 0으로 표현할 수 있다.
꽉찬 집합 : S = (1<<n) - 1
만약 n개의 원소가 있고, 이 원소들이 모두 집합에 포함되어 있으면 모든 비트가 1로 채워진다.
n = 10인 경우를 보면 1<<10는 10000000000(2) 이다. 여기서 1을 빼면 111111111(2)가 된다.
원소 추가 : S = S | (1<<n)
원소 n을 집합에 추가하는 경우에는 1을 n번만큼 왼쪽으로 SHIFT연산 후에 OR연산을 수행한다.
만약 현재 집합 내에 있는 원소가 0,1,2이고, 여기서 새롭게 7을 추가한다고 하자.
기존의 집합을 표현한다면 0000000111(2)이다. 여기서 10000000(2)을 OR연산하면 8번째 비트가 0에서 1로 변경된다.
원소 삭제 : S = S & ~(1<<n)
집합에서 특정 원소를 삭제하고 싶으면 1을 n번만큼 왼쪽으로 SHIFT한 후, NOT연산을 하고, AND 연산을 한다.
현재, 집합 내에 0,1,2,7이 존재하고 여기서 1를 집합에서 제외하고 싶은 경우,
1<<1한 결과인 0000000010(2)에서 NOT연산을 수행하면 1111111101(2)이 되고, 이 상태에서 집합 S와 AND 연산을 한다. 그러면 1의 존재여부를 나타내는 2번째 비트가 1에서 0으로 변경된다.
원소 포함 : S & (1<<n)
집합 내에 특정 원소 n이 포함되어 있는지를 알고 싶은 경우이다.
- 만약 S & (1<<n)의 결과가 0이면, 집합 내에 해당 원소가 포함되어 있지 않다는 의미이다.
- 만약 결과가 0이 아니라면, 집합 내에 해당 원소가 포함되어 있다는 의미이다.
집합 내에 0,2,7이 존재하고 2의 존재여부를 확인하는 연산은 아래와 같다. 연산의 결과가 0이 아니므로 원소 2는 집합 내에 포함되어 있다.
집합 내에 1의 존재 여부를 확인하는 연산은 아래와 같다. 연산의 결과가 0이므로 원소 1은 집합 내에 포함되어 있지 않다.
원소 토글 : S = S ^ (1<<n)
토글이란, 원소 n이 포함되어 있으면(1) 불포함(0)으로 바꾸고, 포함되어 있지 않으면(0) 포함(1)으로 바꾸는 연산을 말한다. 이 때는 1을 n만큼 왼쪽으로 SHIFT연산을 하고 XOR 연산을 수행하면 된다.
집합에 0,2,7이 존재하고 원소 7에 대하여 토글 연산을 수행한다고 하면 아래와 같다.
8번째 자리에 있던 1이 0으로 변경되는 것을 확인할 수 있다.
