Bitmask Technique

이번 포스트는 PS 테크닉 중 하나인 비트마스크(Bitmask) 기법을 다룹니다. Bitmask 기법은 이진수(bit)와 이진수 연산(bitwise operation)을 활용해 연산에서 큰 이득을 제공하기 때문에 고급 PS를 위해서는 꼭 익혀야 하는 기법입니다.

---

이진수와 이진수 연산, 그리고 집합 표현

컴퓨터공학을 공부했다면, 이진수와 십진수 변환에 대해 이미 빠삭하게 알고 있을 것이다. 또, &(AND), |(OR), ~(NOT)과 같은 Bitwise 이진수 연산에 대해서도 이미 익숙할 것이다. Bitmask는 이진수 표기법과 이진수 연산들을 통해 ‘집합‘을 표현하는 기법이다.

집합의 표현은 Boolean Array로 가능하다. bool mySet[100]과 같은 코드에서 몇번째 비트가 켜졌는지, 꺼졌는지로 집합을 표현할 수 있다. 만약 2, 3, 5번째 비트가 켜져있다면, 2, 3, 5번째 원소가 존재하는 집합을 말한다.

(Boolean Array)
| 0 | 1 | 1 | 0 | 1 | ...

그러나 이것을 Boolean Array 대신 Integer 하나로도 표현이 할 수 있다.

(Integer)
01101...

C언에서 int형 변수의 4 바이트, 즉 32 bit이기 때문에 32개 원소를 갖는 부분집합을 Integer 변수 하나로 표현할 수 있다. 더 큰 집합을 표현해야 한다면, int 대신 long long을 쓸 수 있다. 그러면 8 바이트, 즉 64개 원소의 부분집합을 표현할 수 있다.

Bitmask 집합의 연산

Bitmask 기법의 가장 큰 장점은 Bitwise 연산을 통해 집합 연산을 빠르게 수행할 수 있다는 점에 있다.

1. 공집합

int A = 0

2. 꽉 찬 집합

int A = (1 << 10) - 1

int N = (size of your set)
int A = (1 << N) - 1

3. 원소 추가

A라는 Bitmask 집합에 k 번째 원소를 추가

0101 | 0010 -> 0111

A | (1 << k)

4. 원소 삭제

A라는 Bitmask 집합에 k 번째 원소를 삭제. 원소 삽입 때의 연산의 반대것을 수행하면 된다.

0101 & ~(0100) -> 0101 & (1011) -> 0001

A & ~(1 << k)

5. 원소 추출

A라는 Bitmask 집합에 k 번째 원소의 존재여부를 추출

if(0101 & 0100) -> if(0100) -> True
if(0101 & 0010) -> if(0000) -> False

A ^ (1 << k)

6. 원소 토글

A라는 Bitmask 집합에 k 번째 원소를 토글

0101 ^ 0100 -> 0001

A ^ (1 << k)

지금까의 Bitmask 집합 연산 중에 반복해서 보이는 패턴은 (1 << k) 였다. 특정 원소를 다루기 위해선 (1 << k)를 쓴다는 점, 기억해두자.

7. 집합 사이 연산

• A | B: A, B의 합집합. $A \cup B$
• A & B: A, B의 교집합. $A \cap B$
• A & (~B): A, B의 차집합. $A - B$
• A ^ B: A와 B, 둘 중 하나에만 포함된 원소들의 집합.

만약 집합을 Boolean Array로 표현했다면, 위의 집합 연산들을 수행하는데 $O(n)$의 시간이 걸린다, 그러나 Bitmask 집합 기법을 쓴다면, $O(1)$의 비용만 들 뿐이다!

예제 및 활용

지금까지 기본적인 Bitmask 집합 연산들을 살펴보았다. 이번에는 Bitmask를 쓰는 대표적인 문제인 [외판원 문제]와 Bitmask 연산의 활용들을 살펴보자.

외판원 문제

외판원 문제에서는 방문한 도시를 Bitmask 집합으로 표현한다. 예를 들어 001010이라면 2번째, 4번째 도시를 방문한 것이 된다. 발상 자체는 외판원 문제 포스트에서 확인하고 DP에서 쓰는 점화식만 따로 써보면 아래와 같다.

\[C(j, S) = \min_{i \in S, \; i \ne j} \left\{ C(i, S - \{j\}) + d_{ij}\right\}\]

만약 visited를 Bitmask 집합이 아니라 Boolean Array로 표현했다면, 위와 같은 부분집합을 기반으로 하는 점화식을 구현하는게 아주 까다로웠을 것이다. Bitmask 집합을 사용하면, 집합 $S$에 대한 부분을 정수 변수로 쉽게 표현할 수 있다.

dp[curr][visited] = min(dp[prev, visited - prev] + w[prev][curr])

단, 이번에 살펴본 DP+Bitmask의 외판원 문제는 방문하는 도시의 수가 최대 16개로 상당히 적다. 만약 방문해야 하는 도시 수가 Integer 변수의 표현 범위를 벗어난다면, Bitmask 집합 기법을 쓸 수 없다는 점에 유의하자.

활용

Bitmask 집합 기법의 추가적인 활용법에 대해 살펴보자.

8. 최소 원소 추출

이진수 A에 음수 -A는 2의 보수 표현법에 의해 ~A + 1로 표현된다. 이진수 A의 가장 오른쪽 비트 k에 대해 오른쪽은 모두 0으로 표현되는데, ~A 연산은 k를 0으로 그리고 그 오른쪽을 모두 1로 바꾼다. 여기서 1을 더해주게 되면, k보다 오른쪽에 있는 bit는 모두 0이 되고, k번째 비트는 다시 1이 되지만, k의 왼쪽에 있던 비트는 ~A에 의해 토글된 채로 그대로 있다.

 A = 011011000
-A = -(011011000) -> ~(011011000) + 1 (2의 보수) -> (100100111) + 1 -> 100101000
A & (-A) = 011011000 & 100101000 -> 000001000

int first = A & (-A)

9. 최소 원소 삭제

011011000 & (011011000 - 1) -> 011011000 & (011010111) -> 011010000

A &= (A - 1)

A-1을 하게 되면, 가장 오른쪽에 있던 bit는 0이 되고, 그보다 오른쪽에 있는 bit는 모두 1이 된다. 이를 활용해 최소 원소를 삭제한다.

10. 모든 부분집합 순회

for (int subset = A; subset; subset = (subset - 1) & A) { ... }

A = 1011

[subset]
                                     1011 (초기값)
(1011 - 1) & 1011  -> 1010 & 1011 -> 1010
(1010 - 1) & 1011  -> 1001 & 1011 -> 1001
(1001 - 1) & 1011  -> 1000 & 1011 -> 1000
(1000 - 1) & 1011  -> 0111 & 1011 -> 0011
(0011 - 1) & 1011  -> 0110 & 1011 -> 0010

A라는 집합의 부분집합을 순회하는 코드다. 본인은 일종의 테크닉으로 받아들이고 쓰고 있다. 위의 코드는 A라는 집합의 부분집합을 순회하는 코드인데, 약간 변형해 전체 집합을 순회하는 코드도 만들 수 있다.

for (int subset = 0, subset < (1 << N); subset++) { ... }

References

• ‘마이구미’님의 ‘비트마스크(BitMask) 는 무엇인가?’ 포스트
• ‘Rebro’님의 ‘비트마스크 (BitMask) 알고리즘’ 포스트