Bitmask(비트마스크) 설명

비트마스크(Bitmask)

비트마스크는 간단하게 말하자면, 집합의 표현을 비트로 표현하는 것이다. 

예로 들어, 집합 A = {1,3,5,6,7}가 있다고 하자, 비트마스크를 모른다면, bool타입의 array를 이용해서 true, false 체크를 할 것이다. 하지만, 비트마스크를 이용한다면, 아주 간단하게 표현 할 수 있다. 다음 Bool Array에서 T는 해당 원소가 있음을 뜻하고, F는 없음을 뜻한다.

집합 A를 비트마스크를 이용해서 표현해보자. 가장 큰 수가 7이니, 0-7까지 집합의 원소가 있음을 1로 표현하고 없음을 0으로 표현하면, 원소 7이 있음 -> 1, 원소 6이 있음 -> 1  원소 5가 없음 -> 0 ...원소 0이 없음 ->0 으로 표현 할 수 있다. 그렇다면, 이 0과 1의 모음을 순서 그대로 비트에 넣어, 1110101(2)형태로 int 타입으로 저장된다. 이 수를 10진수로 표현하면, 236이 된다. 236자체가 A집합을 비트형태로 표현하고 있다고 할 수 있다.

비트마스크 방법을 이용하면, 데이터의 크기도 줄일 수 있고, 더욱 간단한 연산이 가능해진다. 이제 그 연산에 대해서 한번 알아보자.

집합의 연산

집합의 연산이라고 하면, 아마 검사, 추가, 제거 그리고 토글(toggle)이 있다. 각각에 대해서 알아보자.

집합 A에 대해서 어떠한 집합의 원소가 있는 지 없는 지 확인하는 것을 검사라고 한다. 만약 집합 A(비트마스킹 해서 236)에 원소 '1'이 있는 지 검사해보자.

원소 1이 있는 지 확인 하려면, (1<<1)과 236(집합 A)와 AND연산을 하면 된다. 만약 있다면, 1<<1의 값을 리턴하고, 없다면 0을 리턴 할 것이다.  만약 원소 4가 있는 지 검사하려면 어떻게 해야할까? A&(1<<4)를 하면 된다. 결과는 0이 나온다. A는 4를 가지고 있지 않기 때문이다(0,2,4번 자리는 비트가 꺼진 상태 즉, 원소 없음) 여기서 주의해야 할 것은 AND연산을 해서 해당 원소가 있다면 1을 리턴하는 것이 아니라, 1<<i (i는 찾는 원소)를 리턴한다는 것이다. 이것을 주의해야한다. 

다음으로, 해당 집합에 원소를 추가하는 연산에 대해서 알아보자. 집합  A = {1,3,5,6,7}에서 원소 '2'를 추가해보자. 

원소 '2'를 추가하려면 OR연산을 하면 된다. 236|(1<<2)로 표현할 수 있다.  집합 A는  {1,2,3,5,6,7}로 바뀌게 되고, 비트마스킹하면, 240이 된다. 

여기서 조심해야하는 것은, +하는게 아니다. 만약 추가하려는 원소가 이미 존재하고, 비트연산 +를 하게되면, carry가 발생해서, 집합이 완전히 바뀔 수 있게 된다. 그냥 OR연산을 하자..

원소의 검사와 매우 슷비슷비하다.('슷비슷비'은 '비슷비슷'과 비슷비슷해서 비슷비슷하다는 의미이다.)

그 다음으로, 집합에 원소를 제거하는 연산에 대해 알아보자. 집합 A에서 원소 '3'을 제거한다고 해보자. 

원소 3을 제거하려면, 3의 자리는 0, 나머지는 1로 만들어서 AND연산을 하면 된다. 약간 복잡하지만, 수식으로 표현하면 236&~(1<<3)이 된다. 우선 <<연산자로 00001000(2)를 표현하고, ~연산으로 11110111(2)를 하고, AND연산을 하는 것이다. 비트연산은 우선순위에 조심해야힌디. 대체로 비트연산은 우선순위가 매우 낮다. 그냥 헷갈리면 괄호를 남발하면 된다.

마지막으로 토글에 대해서 알아보자. 토글은 i번째 비트가 0이면 1로 바꾸고, 1이면 0으로 바꾸는 것이다. 즉, XOR연산이다. 그냥 XOR연산을 하면 된다.

비트마스킹을 이용한 문제를 하나 풀어보자.

부분집합의 합 (boj.kr/1182)

원소의 부분집합을 모두 표현해서, 그 표현한 부분집합의 총합이 S인지 검사하면 된다.(브루투포스)

부분집합의 개수는 2^N인데, 공집합은 제외하기 떄문에, 1개가 줄어든다.

그렇다면, 그 부분집합을 어떻게 표현은 어떻게 비트마스크로 할 수 있을까?

N=5이기 때문에, 부분집합은 31가지로 표현 할 수 있다.(공집합X)

여기서 1은 해당 위치가 포함 되었음을 뜻하고, 0은 포함 되지 않았음을 뜻한다. 예로들어, 0 0 0 0 1은 어떻게 되는 것인가? 원소 8만 부분집합으로 갖는 경우의 수를 뜻한다. 0 0 1 1 1은  -2, 5, 8을 부분집합으로 갖는 경우의 수이다.

그런데, 여기서 놀라운 것을 발견 할 수 있다.  1부터 31까지의 수를 비트로 표현하면, 모두 다른 비트형태이다 즉, 모두 다른 부분집합의 경우의 수를 표현한다고 할 수 있다. 헷갈리면, 1부터 31까지 모두 비트로 표현하는 것도 좋을 거같다. 00001(2)~11111(2)로 모든 경우의 수가 표현된다. 아까 집합 A를 236으로 표현한 것처럼, 포함의 여부를 0,1로 표현해서 정수(236처럼)로 만든 것이다

그러면 어떻게 문제를 풀면 될까. 1 ~ 31까지 돌리면서(모든 부분집합의 경우의 수 표현) 비트가 켜진부분의 위치를 다 더해서, S와 같은 지 체크하면 된다.

이 문제의 핵심 포인트는, 부분집합의 경우의 수를 비트로 표현했다는 것이다.

#include <iostream>
using namespace std;
 
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(false);
 
    int n, s, a[20];
    cin >> n >> s;
 
    for (int i = 0; i < n; ++i)
        cin >> a[i];
 
    int cnt = 0;
    for (int i = 1; i < (1 << n); ++i) {
        int sum = 0;
        for (int j = 0; j < n; ++j) {
            if (i & (1 << j)) {
                sum += a[j];
            }
        }
        if (sum == s)
            cnt += 1;
    }
 
    cout << cnt << '\n';
 
    return 0;
}

이중포문에서 j는 켜진 부분의 비트를 확인해서 더해주는 역할을 한다.

이 문제를 비트마스크를 이용해서 풀 수 있는 이유는 N제한이 작기 때문이다. 부분집합의 개수는 2^N으로 표현 가능한데, N=20이면 1억보다 적기 때문에, 이 문제의 제한인 2초내에 풀 수있는 것이다. 만약 N제한이 30정도 된다면, 이 문제를 풀 수 없을 것이다.

비트마스크는 브루트포스, DP에서 많이 쓰인다. DP에서 어떻게 쓰이는 지는 나중에 포스팅하도록 하자..