비트마스크
비트는 이진 숫자(binary digit) 라는 뜻으로 컴퓨터에서 사용되는 데이터의 최소 단위이다.
비트는 0,1 값을 가질 수 있고, true/false, on/off 상태를 나타낸다.
장점
- 수행 시간이 빠르다.
비트마스크 연산은 bit 연산이기 때문에 O(1)에 구현되는 것이 많다. 따라서 다른 자료구조를 이용하는 것보다 훨씬 빠르게 동작하게 된다.
다만, 비트마스크를 이용하는 경우에는 비트의 개수만큼 원소를 다룰 수 있기 때문에 연산 횟수가 적은 경우에는 속도에 큰 차이가 없지만, 연산 횟수가 늘어날수록 차이가 매우 커지게 된다. - 코드가 짧다.
- 메모리 사용량이 적다.
길이가 8인 집합 {0,1,2,3,4,5,6,7} 이 존재하고 부분집합을 나타내고 싶을 때
위와 같은 형태로, Integer 형으로 인덱스를 활용할 수 있다면, 단순히 boolean 배열을 통해 구현할 수도 있다.
bool array1[] = { 1,1,1,0,0,0,1,0 };
bool array2[] = { 1,0,1,0,1,0,0,0 };
bool array3[] = { 0,1,0,0,1,0,1,1 };
...하지만 이건 많은 메모리를 차지하고 오버헤드<1>가 증가한다.
비트마스크를 사용하면 보다 효율적이게 메모리를 쓸 수 있다.
{0,1,2,3,4,5,6,7} => [1111 1111]
{1,2,3,5,7} => [1010 1110]
{0,3,4,6} => [0101 1001]
각 요소는 인덱스처럼 표현할 수 있다.
집합 i번째 요소가 부분집합에 존재한다면 1을 의미하고, 그렇지 않으면 0을 의미한다.
위에 언급한 2진수를 10진수로 표현할 수도 있다.
{0,1,2,3,4,5,6,7} => [1111 1111] => 255
{1,2,3,5,7} => [1010 1110] => 174
{0,3,4,6} => [0101 1001] => 89
비트 연산자
비트 연산자는 비트(bit)단위로 논리 연산을 할 때 사용하는 연산자이다.
또한, 비트 단위로 전체 비트를 왼쪽이나 오른쪽으로 이동시킬 때도 사용한다.
-
AND 연산
두 정수 변수 a와 b를 AND 한다고 하면 a와 b의 한 비트씩 비교하며 둘 다 1인 경우에 c의 해당 비트를 1로 한다.
c = a & b; -
OR 연산
AND가 둘 다 1일 때 1이라면 OR 연산은 둘 중 하나라도 1일 때 c의 해당 비트를 1로 한다.
c = a | b; -
XOR 연산
배타적 연산이며 두 개의 input값이 서로 다를 때 1이 된다.
input이 2보다 클 경우는 1의 개수가 홀수일 경우 1이 출력된다.
c = a ^ b; -
NOT 연산
켜져 있는 비트는 끄고, 꺼져 있는 비트는 키는 결과를 낸다.
0->1, 1->0
c = ~a; -
시프트 연산
시프트 연산자는 정수 a의 비트들을 왼쪽 또는 오른쪽으로 원하는 만큼 움직이고 빈자리는 0으로 채운다.
c = (a << 1);
왼쪽으로 이동하는 것은 0110 -> 1100으로 되는 것을 뜻하고 이는 2를 곱한 것과 같다.
즉 a << n 일 때의 값은 을 곱한 것과 같다. 반대로는 으로 나눈 값과 같다.
비트 연산자를 이용할 때에는 주의해야할 점이 있다
1. 비트 연산자들의 우선순위는 비교 연산자보다 낮다.
2. 오버플로우가 발생할 수 있다.
2^50을 구하기 위해서 1<<50으로 표현하면, C에서는 1은 32bit 상수 취급하기 때문에 50번 왼쪽으로 shift하게 되면 overflow가 발생하게 된다. 따라서 1LL로 표현을 해주어야 한다.
비트마스크를 이용한 집합 구현
앞서 말한 것처럼 비트마스크를 통해 집합을 구현할 수 있다.
다시 정리하면 bit가 켜져 있으면 해당 원소가 집합에 포함되어 있다는 의미고, 꺼져 있으면 포함되어 있지 않다는 의미이다.
따라서 N비트 정수 변수라면 N개의 원소를 갖는 집합의 부분집합들을 모두 표현할 수 있게 된다.
| 연산 | 사용 예시 |
|---|---|
| 공집합과 꽉 찬 집합 | A = 0; / A = (1 << N) - 1; |
| 원소 추가 | A |= (1 << k); |
| 원소 삭제 | A &= ~(1 << k); |
| 원소의 포함 여부 확인 | if(A & (1 << k)) |
| 원소의 토글(toggle) | A ^= (1 << k); |
| 두 집합에 대해서 연산 | A | B -> A와 B의 합집합 |
| A & B -> A와 B의 교집합 | |
| A & (~B) -> A에서 B를 뺀 차집합 | |
| A ^ B -> A와 B 중 하나에만 포함된 원소들의 집합 | |
| 최소 원소 찾기 | A & (-A); |
예를 들어 포켓몬이 있고 상태이상이 있다고 생각할 때..
const int NONE = 0;
const int FREEZE = 1 << 0;
const int POISON = 1 << 1;
const int CONFUSED = 1 << 2;
int state = NONE; //처음엔 아무 상태이상이 안걸린 상태(공집합)
state |= FREEZE; //빙결 상태이상이 걸렸다. (원소 추가)
state &= ~POISON; //해독제를 먹어 독 상태가 풀렸다. (원소 삭제) 이미 안걸려있었다고 한다면 상태 유지
if (state & CONFUSED)
;// 혼란이 걸린 상태
<1>오버 헤드는 특정 기능을 수행하는데 드는 간접적인 시간, 메모리 등 자원을 말한다.
