비트마스크(BitMask) 사용해보기

개요

문제해결을 할때, 우리는 int나 float 형과 같이 우리 인간에게 가장 익숙한 수체계인 십진수로 표현할 수 있는 수들을 사용하여 각종 문제를 해결해왔습니다. 하지만 현대의 대부분의 컴퓨터는 이진수를 사용하여 데이터를 나타내거나 연산을 합니다. 따라서 내부적으로 다시 이진수로 변환되어 연산되는 십진수 연산보다 처음부터 이진수로 연산되는 연산이 더 빠를 것이라고 짐작할 수 있습니다.

비트마스크란?

앞서 말한 이진수 연산의 장점을 최대한 활용하기 위해 고안된, 정수의 이진수 표현을 활용한 기법이 바로 비트마스크(BitMask)입니다. 다음 예시문제를 생각해 봅시다.

$0$ 번부터 $N-1$ 번까지 번호가 붙어있는 전구의 상태는 총 몇가지로 표현될 수 있을까?

전구는 그럼 총 $N$ 개가 있고, 각 전구는 켜졌거나 꺼졌거나의 두가지 상태를 나타낼 수 있기 때문에 $2^N$ 가지의 상태가 있다고 생각할 수 있습니다. 이 상태를 각 $0$부터 $2^N-1$까지, 총 $2^N$ 가지의 정수에 일대일 대응을 하는겁니다.

$N=4$라고 생각하겠습니다. 모든 전구가 다 꺼졌을때는, 0000 즉, 십진수로 표현하면 0이라는 상태로 나타낼 수 있습니다. 만약 모든 전구가 다 켜졌을때는 어떻게 될까요? 1111 즉, 십진수로 표현했을 때, 15가 됩니다. 만약 x번째 전구가 켜졌을때는, 상태번호를 이진수로 표현했을때 그 수의 x번째 수를 1, 꺼졌을때는 0으로 표현합니다. 말이 좀 복잡했네요, 마지막으로 한가지 예시를 들면 0번째 전구와 3번째 전구가 켜진 상태는 1001, 즉 상태를 십진수 9로 나타낼 수 있는 것입니다.

비트마스크를 사용하면 좋은점

예시를 들다보니, 조금 더 쉽게 설명하고 싶은 욕심에 글이 길어졌네요. 말로만 들으면 이렇게 복잡한 비트마스크를 도대체 왜 사용해야할까요? 대표적으로 **TSP(Travelling Salesman Problem, 외판원순회문제)**에서 비트마스킹이 유용하게 사용될 수 있습니다. 메모리제한이 빡빡한 문제에서 어떤 집합을 표현할때 비트마스킹이 다른 집합 표현방법보다 메모리를 덜 사용하는 장점이 있습니다. 앞서 말했듯, N개의 원소로 이루어진 집합의 부분집합을 단 N개의 비트만 사용해서 나타낼 수 있으니까요. 그리고 대부분의 비트마스크 연산은 $O(1)$의 시간복잡도를 가지기 때문에, 시간적인 면에서 약간의 이득을 볼 가능성도 있습니다.

비트마스크 사용법(C++)

그래서 비트마스크 그리고 비트마스크와 관련된 연산은 어떻게 구현해야할까요? 이 문단에서는 C++을 이용해 비트마스크를 사용할 수 있는 방법을 알려드립니다.

집합표현

자 우선 비트마스크를 하기 위해서는 집합의 상태를 표현할 수 있는 숫자가 있어야합니다.

int status = 0;

집합의 상태를 표현하는 변수인 status를 만들었습니다. 이 집합은 현재 모든 비트가 꺼져있습니다. 앞으로 공집합을 나타내고 싶을때는, 해당 변수를 0으로 초기화해주세요. 이 집합은 원소가 10개 인것으로 약속합시다.

공집합과 반대로, 집합의 원소 10개 모두 존재하는 것으로 나타내고 싶으면 어떻게 해야할까요?

status = (1 << 10) - 1;

<< 연산자는, 현재 변수에서 원하는 만큼 비트를 왼쪽으로 미는 연산자입니다. 예시에서는 1이라는 수를 왼쪽으로 10번 밀고 1을 뺀 수를 나타내고 있네요, 이진수 10000000000 에서 1을 빼면 어떻게 되나요? 1111111111이 되겠죠? 그러면 우리가 원하는대로 10개의 비트 모두 켜진 상태가 됩니다.

원소 포함 여부 확인

만약에 x번째 전구가 켜져있는지 확인하려면 어떻게 해야할까요?

if(status & (1 << x)){
    //...
}

소스코드를 이해해봅시다. 여기서 나오는 & 연산은 우리가 알고있는 AND 논리연산과 같습니다. 같은자리수 비트를 비교할 때, 두 비트 모두 켜져있어야 1을 반환하고 그렇지 않으면 0을 반환하는 연산자입니다. 1 << x 는 x번째 비트만 켜진, 우리가 만든 수입니다. 그 수와 status와 AND연산을 하고있네요. 만약 status의 x번째 비트가 1이라면 if절안의 내용이 참이되고, x번째 비트가 0이라면 if절 안의 내용이 거짓이 되겠죠. 이해가 안되시면 천천히 다시 읽어보면서 제대로 이해하고 넘어가주세요.

원소 추가와 삭제

자, 집합의 상태는 문제에 따라 변할수도, 아닐수도 있습니다. 이 절에서는 집합의 상태가 변하는 경우를 살펴보죠.

우선 원소를 추가해보고 싶습니다. 앞의 예시의 표현대로라면, 특정한 전구를 켜고싶습니다. 어떻게 해야할까요? 다음 예시는 x번째 비트를 켜는 소스코드입니다.

status |= (1 << x);

여기서 |는 OR연산입니다. 그러니까 다음과 같은 표현의 축약형입니다.

status = status | (1 << x);

x번째 비트가 이미 켜져있으면 유지하고, 꺼져있으면 켜지겠네요. 따라서 원소가 추가된것과 같은 효과라고 말할 수 있겠습니다.

그 다음은 원소를 삭제해볼 차례입니다.

status &= ~(1 << x);

참고로, ~는 NOT연산입니다. 그러니까 위의 예시는 ~(1 << x)는 x번째 비트 빼고 모두 켜진 수겠네요. AND연산을 해보면 x번째 비트가 꺼져있으면 꺼져있는대로 유지하고, 켜져있으면 그 비트를 끄는 동작을 하니까 결과적으로 x번째 비트가 꺼지는 결과를 만들겠네요. 음... 조금 복잡하네요. 왜 이런 표현을 해야했을까요? 다음 예시를 보면서 이해해봅시다.

status -= (1 << x);

이런식으로 표현을 하면, x번째 비트가 켜져있지 않을때 위와 같은 연산을 하면 의도치 않은 결과가 나올 수 있기 때문입니다. if문을 한줄 써서 해당 원소가 있는지 체크를 해준다면 위와 같은 표현을 써도 되지만, 보통 처음 소개해드린 방법 한줄로 끝내는 방법을 많이 선호합니다. 처음 소개해드린 방법은 x번째 비트가 꺼져있어도 의도치않은 결과를 초래하지 않습니다. 그리고 if문 없이 한줄로 끝낼 수 있다는 장점이 있죠!

끝내며

우리는 십진수 수체계에 익숙해져있어서, 이진수 연산을 많이 접해볼 기회가 없었죠, 문제해결할때 우리는 십진수로 추상화된 자료형들을 많이 사용하고, 큰 불편함이 없었지만 앞으로는 이런 이진수 연산의 장점을 잘 사용해야 풀수있는 문제들이 많이 접하게될 것입니다. 비트마스킹과 비트마스킹에 사용되는 연산들의 논리를 잘 이해하시고 확실히 내 것으로 만들어 PS에 있어서 비트마스킹을 본인이 가진 하나의 "툴"로 잘 사용해보시기 바랍니다.