컴퓨터는 내부적으로 모든 자료를 이진수로 표현해서 저장하고 있습니다. 이와 같은 컴퓨터의 특성을 이용해서 정수의 이진수 표현을 자료구조로 쓰는 기법을 비트 마스킹이라고 합니다.
비트마스킹을 이용하면 컴퓨터가 저장하는 자료를 그대로 이용하는 것이기 때문에 더 빠른 수행 시간, 더 간결한 코드, 더 적은 메모리 사용이라는 효과를 얻을 수 있습니다.
비트마스킹은 기본적으로 비트를 다뤄야 합니다. 따라서, 자주 쓰이는 비트 연산자에 대해서 먼저 알아보도록 하겠습니다.
| a & b | a의 모든 비트와 b의 모든 비트를 AND 연산한다. 둘 다 1이라면 1, 아니면 0 |
a = 4 = 100(2) b = 7 = 111(2) a&b = 100(2) = 4 |
|---|---|---|
| a | b | a의 모든 비트와 b의 모든 비트를 OR연산한다. 둘다 0이라면 0, 아니면 1 |
a = 2 = 010(2) b = 5 = 101(2) a | b = 111(2) = 7 |
| a ^ b | a의 모든 비트와 b의 모든 비트를 XOR연산한다. 둘이 다르다면 1, 아니면 0 |
a = 3 = 011(2) b = 5 = 101(2) a ^ b = 110(2) = 6 |
| ~a | a의 모든 비트에 NOT 연산을 한다. 0이면 1, 1이면 0 |
총 3비트라고 가정 a = 3 = 011(2) ~a = 100(2) = 4 |
| a << b | a를 b비트 만큼 왼쪽으로 시프트 | a = 1 = 001(2) a << 2 = 100(2) = 4 |
| a >> b | a를 b비트 만큼 오른쪽으로 시프트 | 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으로 바꿔줘야됩니다.
a & b , ~a 비트 연산자를 활용하면 쉽게 해결할 수 있습니다.
cur = cur & ~(1 << p);1 << p 를 통해서 p번 비트만 1, 나머지 비트는 0으로 만듭니다. 그 후, ~ 연산을 통해 p번 비트만 0, 나머지 비트는 1로 만들고 & 연산을 진행한다면 p번 비트만 0으로 바뀌고 나머지는 현재 상태 cur과 동일하게 유지할 수 있습니다.
p번 비트가 1이면 0, 0이면 1로 바꾸는 토글 연산도 쉽게 구현할 수 있습니다. 현재 상태 cur에서 p번 원소가 있다면 삭제하고, 없다면 추가해보겠습니다.
a ^ b 비트 연산자를 이용하면 됩니다.
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의 부분집합 중 하나.
}subset을 set에서 시작해서 1씩 감소하면서 set과 & 연산자를 해주면 모든 부분 집합을 순회할 수 있습니다.