26. Bitmasks

비트마스크(Bitmasks)(비트마스킹(Bitmasking)으로 불리는 경우도 있음)는 Bool 값으로 표현할 수 있는 대상이 여러 개 존재할 때 이를 정수의 비트를 이용해서 표현하는 기법이다. Bool 값으로 표현할 수 있는 대상은 대비되는 두 개의 속성만을 가지고 있어야 한다. 예를 들어 참(True)과 거짓(False), 켜진 상태(ON)와 꺼진 상태(OFF), 선택한 상태와 선택하지 않은 상태 등이 있다. 일반적으로 $8$바이트 정수 자료형으로 $64$개의 비트를 한번에 표현할 수 있고 그보다 큰 정수 자료형이 잘 쓰이지 않기 때문에 이보다 적은 비트만을 사용해서 문제를 풀 수 있는 경우에 주로 사용되지만 정수 배열을 이용해서 더 많은 비트를 사용하고 메모리와 실행 시간의 측면에서 더 성능이 좋은 코드를 작성하는 경우도 가끔씩 존재한다.

 

BOJ 11723. 집합 (Silver V)

이 문제가 비트마스킹을 연습할 수 있는 기본적인 문제이다. 원소와 집합의 관계는 포함되거나 포함되지 않거나 둘 중 하나로 정해지기 때문에 $k$번째 원소를 $1<< k$라는 값(밑에서부터 $k$번째 비트와 같으며 최하위 비트를 $0$번째 비트로 간주한다)으로 관리하면 주어지는 연산을 빠르게 처리할 수 있다. 기본적인 비트 연산자를 활용하여 연산을 처리하는 방법은 다음과 같다.

 

• $x$의 $k$번째 비트가 $0$인지 $1$인지 확인한다. → $x \And 1<< k$
• $x$의 $k$번째 비트를 $1$로 만든다. → $x\;|=1<< k$
• $x$의 $k$번째 비트를 $0$으로 만든다. → $x \And =\;\sim(1<< k)$
• $x$의 $k$번째 비트가 $1$이면 $0$으로, $0$이면 $1$로 만든다. → $x\text{ ^}=1<< k$
• $x$의 비트 중 값이 $1$인 가장 낮은 비트를 찾는다. → $x \And -x$
• $x$에 값이 $1$인 비트가 $1$개 이하인지 확인한다. → $x \And x-1$
• $x$에 값이 $1$인 비트가 가장 낮은 비트부터 연속적으로 나타나는지 확인한다. → $x \And x+1$

$+, -, <<$ 등의 연산자는 비트 연산자보다 우선순위가 높기 때문에 위와 같이 괄호를 안 씌워도 제대로 작동한다. 헷갈린다면 괄호를 씌워도 무방하다. 또한 비트마스크를 구현할 때는 생각보다 문제가 되는 일은 적지만 비트 연산자의 우선순위는 &(AND) → ^(XOR) → |(OR)이다.

 

$k$번째 비트를 확인하고 조작하는 것은 간단하다. $k$번째 비트를 $0$으로 만드는 것이 $x \And =\;\sim(1<< k)$라고 되어 있는데, $~(1<< k)$는 $k$번째 비트만 $0$이고 나머지 비트는 모두 $1$인 상태와 같다. 따라서 이 수와 AND 연산을 하게 되면 $k$번째 비트만 $0$으로 바뀌고 나머지 비트는 변하지 않게 된다. (어떤 비트에 $1$과 AND 연산을 하거나 $0$과 XOR, OR 연산을 하면 비트의 값은 변하지 않는다.)

 

마지막 두 개의 확인 연산은 결과값이 $0$이면 참, $0$이 아니면 거짓이다. 익숙하지 않은 경우 헷갈리기 쉬우므로 주의해야 한다.

 

이제 위에 제시된 연산들을 이용하여 문제를 풀 수 있다. all과 empty 명령이 들어오면 그냥 $x$를 $(1<< 20)-1$이나 $0$으로 바꾸면 된다.

 

비트마스크는 응용하면 그 자체로 어려운 문제가 되기도 한다. 이런 문제들을 마주했다면 일단 비트별로 나눠서 확인할 수 있는지 체크하는 것이 좋다. 그밖에 때때로 비트마스크를 동적 계획법에 적용한 비트DP라는 방법으로 문제를 해결할 수 있는 경우가 있다. 이에 대해서는 나중에 다시 설명할 예정이다. 여기에 있는 연습문제는 비트마스크 자체를 응용하는 문제들이다.

 

[연습문제]

 

CF 1270C. Make Good (1400)

$n$개의 값을 모두 더한 결과를 $s$, 모두 XOR 연산한 결과를 $x$라고 하면 다음과 같이 출력하면 맞게 된다.

 

$2$

$x$  $s+x$

 

이 문제는 비트별로 나눠서 확인하면 더 복잡해지는데, 그런 문제들은 의외로 간단한 풀이가 존재하는 경우가 많으므로 다양한 접근을 시도하는 것이 좋다.

 

CF 1299A. Anu Has a Function (1500)

$f(x,y)=(x|y)-y$인데 이것을 변형하면 $x-(x\text{&}y)$가 된다. 즉 $f(f(\ldots f(f(a_1,a_2),a_3),\ldots a_{n-1}),a_n)$의 결과값은 $a_1$에만 존재하는 비트의 합이 된다. 즉 $a_2$부터 $a_n$까지의 순서는 답에 영향을 주지 않는다. 따라서 각각의 비트를 확인하면서 그 비트가 $1$인 원소가 한 개밖에 없는 경우를 체크해서 각각의 원소에만 존재하는 비트의 합을 구한다. 이 합이 가장 큰 원소를 첫 번째에 놓고 나머지 원소는 아무렇게나 배열하면 된다.

 

CF 1325D. Ehab the Xorcist (1700)

케이스를 나눠서 풀 수 있다.

A. $u$와 $v$의 홀짝이 다르거나 $u > v$인 경우 답은 $-1$이다. (어떤 수들이 있을 때 그것들의 합과 XOR 값은 홀짝이 항상 같다.) $u$와 $v$의 홀짝이 같다면 $u$와 $v$가 같은지 비교한다.

 

B. $u < v$인 경우 다음과 같은 배열을 생성할 수 있다.

 

$3$

$u$  $\frac{v-u}{2}$  $\frac{v-u}{2}$

 

C. $u = v > 0$인 경우 다음과 같은 배열을 생성할 수 있다.

 

$1$

$u$

 

D. $u = v = 0$인 경우 다음과 같이 출력하면 된다.

 

$0$

 

CF 1466E. Apollo versus Pan (1800)

각각의 원소에 대한 전처리를 하고 $x_j$를 고정하면 문제를 풀 수 있다.

 

BOJ 30697. Present (Platinum II)

CF 1322B. Present (2100)

각각의 원소를 더했을 때 각 비트에서 받아올림이 발생하는 경우가 몇 번인지 계산하면 된다. 계산은 상위 비트부터 진행하며, 나중에 소개할 투 포인터 기법으로 구할 수 있다.

 

→ solved.ac tag: bitmask