비트마스크를 이용한 집합의 구현

비트마스크의 가장 중요한 사용 사례는 집합을 구현하는 것이다. 이 표현에서 N비트 정수 변수는 0부터 N-1까지의 정수 원소를 가질 수 있는 집합이 된다. 이때 원소 i가 집합에 속해 있는지 여부는 2^i을 나타내는 비트가 켜져 있는지 여부로 나타낸다.

 

예를 들어 여섯 개의 원소를 갖는 집합 {1, 4, 5, 6, 7, 9}을 표현하는 정수는 754임을 다음과 같이 알 수 있다.

 

2^1 + 2^4 + 2^5 + 2^6 + 2^7 + 2^9 = 10 1111 0010(2) = 754

 

비트마스크 연산을 이용해 이 집합을 어떻게 조작할 수 있는지 알아보자.

 

---

 

피자집 예제

토핑을 골라 주문할 수 있는 피자집의 주문 시스템이 있다. 이 피자집에는 0부터 19까지의 번호를 갖는 스무 가지의 토핑이 있으며, 주문시 토핑을 넣기/넣지 않기를 선택할 수 있다. 그러면 한 피자의 정보는 스무 종류의 원소만을 가지는 집합이 되고, 비트마스크를 이용해 표현할 수 있다. 물론 크기 20인 bool 배열을 사용해도 해결 할 수 있지만 비트마스크를 이용하면 다양한 비트 연산을 이용해 집합 연산을 빠르고 간단하게 구현할 수 있다.

 

 

▶ 공집합과 꽉 찬 집합 구하기

토핑을 올리지 않는 피자와 모든 토핑을 올린 피자를 표현한다고 한다. 비트마스크를 이용해 집합에서 공집합을 표현하는 것은 너무 간단하다. 상수 0이 공집합을 나타낸다. 꽉 찬 집합을 구하는 것 또한 매우 간단하다. 스무 개의 토핑을 모두 포함하는 집합은 마지막 20개의 비트가 모두 켜진 숫자인데, 이것을 다음과 같은 코드로 얻을 수 있다.

 

int fullPizza = (1 << 20) - 1;

 

1 << 20은 이진수로 1 뒤에 20개의 0이 있는 정수로 표현되고, 여기서 1을 빼면 20의 비트가 모두 1이 된 수를 얻을 수 있다.

 

 

▶  원소 추가

집합의 가장 기초적인 연산은 원소를 추가하고 삭제하는 것이다. 비트마스크를 사용한 집합에서 원소를 추가한다는 것은 해당 비트를 1로 킨다는 것이다. 토핑 목록에 페페로니를 추가한다고 가정하자. 페페로니의 번호가 p(0<=p<20)에 주어질 때, 다음 코드로 집합 toppings에 페페로니를 추가할 수 있다.

 

toppings |= (1 << p);

 

1을 왼쪽으로 p비트 shift하면 p번 비트만 켜진 정수가 되므로 이 값과 toppings를 비트별 OR하면 해당 비트는 반드시 켜지게 된다. toppings에 이미 페페로니가 들어가 있을 경우 값은 변하지 않는다.

 

 

 

▶  원소의 포함 여부 확인

토핑 목록에 페페로니가 잘 추가되었는지 확인해보자. 집합 toppings에 페페로니가 포함되어 있는지를 다음 코드로 알 수 있다.

 

if(toppings & (1 << p)) cout << "Is In !" << endl;

 

& 연산의 결과값이 0 또는 1 << p라는 점에 유의한다. 대부분의 논리 연산처럼 원소가 포함되어 있는 경우 1, 혹은 true가 반환된다고 생각하면 아래와 같은 코드를 작성하는 실수를 범한다.

 

// 제대로 동작하지 않는 코드
if((toppings & (1 << p)) == 1) cout << "Is In !" << endl;

 

 

 

▶  원소의 삭제

마음이 변해서 토핑 목록에서 페페로니를 삭제한다고 하자. 한 가지 방법은 1 << p를 toppings에서 빼는 것이다.

 

toppings -= (1 << p);

 

하지만 이 코드는 이미 페페로니가 토핑 목록에 있을 때만 사용 가능하다, 만약 토핑 목록에 페페로니가 없다면 정상적으로 동작하지 않는다. 토핑이 없을 때도 정상적으로 동작하는 방법은 다음과 같은 코드를 사용하는 것이다.

 

toppings &= ~(1 << p);

C++의 ~ 연산자는 비트별 NOT 연산을 수행하므로, ~(1<<p)는 해당 비트만 꺼지고 나머지는 다 켜진 숫자가 된다. 이 숫자와 비트별 AND연산을 수행하면 toppings의 나머지 비트는 유지되고 p번 비트는 항상 꺼지게 된다.

 

 

 

▶  원소의 토글

또 하나 종종 유용하게 사용되는 것은 토글(toggle)이다. 해당 비트가 켜져 있으면 끄고, 꺼져 있으면 켜는 것이다. XOR 연산이 이와 같은 일을 할 수 있다. 따라서 p번 토핑이 들어가 있는 경우 빼고, 빠져 있는 경우 넣는 코드를 다음과 같이 작성할 수 있다.

 

toppings ^= (1 << p);

 

 

 

▶  두 집합에 대해 연산하기

p번 토핑을 추가하거나 삭제할 때 1<<p를 사용했는데, 사실 이 값은 크기가 1인 집합으로도 볼 수 있다. 이때 크기가 더 큰 집합을 사용해도 이 연산들을 그대로 적용할 수 있다. 두 개의 토핑집합 a와 b의 합집합과 차집합 등을 다음과 같이 쉽게 구할 수 있다.

 

int added = (a | b);		// a와 b의 합집합
int intersection = (a & b);     // a와 b의 교집합
int removed = (a & ~b);		// a에서 b를 뺀 차집합
int toggled = (a ^ b);		// a와 b중 하나에만 포함된 원소들의 집합

 

이 코드의 수행 시간은 원소 하나에 대해 수행하는 것과 다를 게 없다. 집합 간의 연산을 이렇게 빠르게 할 수 있다는 것이 비트마스크를 이용한 집합 표현의 큰 장점이다.

 

 

 

▶   집합의 크기 구하기

비트마스크를 이용할 때 집합에 포함된 원소의 수를 구하는 쉬운 방법은 딱히 없다. 따라서 가장 간단한 방법은 각 비트를 순회하면서 켜져 있는 비트의 수를 직접 세는 수밖에 없다. 재귀 호출로 작성하면 다음과 같다.

 

int bitCount(int x){
    if(x==0) return 0;
    return x % 2 + bitCount(x / 2);
}

 

 

 

▶   최소 원소 찾기

최하위 비트의 번호가 아닌 해당 비트를 직접 구하고 싶으면 어떻게 해야할까. 예를 들어 40이 주어질 경우 3대신 2^3을 구하는 것이다. 비트의 위치를 구한 뒤 1을 그만큼 왼쪽으로 shift해도 되겠지만, 이것을 좀 더 간단하게 하는 방법이 있다. 

 

int firstTopping = (toppings & -toppings);

 

이것은 대부분의 컴퓨터가 음수를 표현하기 위해 2의 보수를 사용한다는 점을 이용한다. 2의 보수를 사용하는 시스템에서는

음수 -toppings를 표현하기 위해서 toppings에 비트별 NOT 연산을 적용하고 그 결과에 1을 더한다. toppings에서 켜진 최하위 비트가 2^i라고 하자. 그러면 toppings의 마지막 i+1자리는 1 뒤에 i개의 0이 있는 형태여아 한다. toppings에 비트별 NOT 연산을 적용하면 마지막 i+1자리는 0 뒤에 i개의 1이 있는 형태가 되고, 여기에 1을 더하면 다시 1과 i개의 0이 있는 형태가 된다. 2^i보다 상위 비트들에는 NOT 연산이 적용된 상태이므로 두 수를 AND하면 항상 최하위 비트만을 얻을 수 있다. 

 

 

 

▶ 최소 원소 지우기

 

종종 최소 원소가 무엇인가와 상관 없이 최소 원소를 지우는 연산이 유용할 때가 존재한다.

 

toppings &= (toppings - 1);

 

최소 원소를 얻은 뒤, 그 원소를 지우는 것보다 훨씬 간결하다. 

어떻게 이 방법이 가능할까? toppings -1의 이진수 표현을 생각해보면 쉽게 알 수 있다. toppings - 1의 이진수 표현은 toppings에서 켜져있는 최하위 비트를 끄고 그 밑의 비트들을 전부 켠 것이다. 따라서 두 값을 비트별 AND 연산하면 최하위 비트와 그 이하의 비트들은 전부 0이 된다. 그 예로 40(=10 1000(2))과 39(=10 0111(2))의 비트별 AND 연산을 하면 32(=10 1000(2))로 최하위 비트가 꺼진 것을 볼 수 있다. 

 

이 방법은 어떤 정수가 2의 거듭제곱 값인지 확인할 때도 유용하게 쓰인다. 2의 거듭제곱 값들의 이진수 표현에는 켜진 비트가 하나밖에 없기 때문에, 최하위 비트를 지웠을 때 0이 된다면 주어진 수는 2의 거듭제곱이다.

 

 

 

▶ 모든 부분 집합 순회하기 

또 하나 아주 유용한 팁은 주어진 집합의 모든 부분 집합을 순회하는 것이다. 예를 들어 pizza가 {페페로니, 소시지, 양파}라면 {페페로니}, {페페로니, 소시지}, {페페로니, 소시지, 양파}, {페페로니, 양파}, {소시지}, {소시지, 양파}, {양파}를 하나 하나 열거하는 것이다.

 

for(int subset = pizza; subset; subset = ((subset - 1) & (pizza)){
	// subset은 pizza의 부분집합
}

 

이 코드는 어떻게 동작할까, 다음 부분 집합을 구하는 식 (subset - 1)&pizza를 눈여겨보자. subset에서 1을 빼면 켜져 있던 최하위 비트가 꺼지고, 그 밑의 비트들은 전부 켜지게 된다. 이 결과와 pizza의 교집합을 구하면 그 중 pizza에 속하지 않는 비트들은 모두 꺼지게 된다. 이 연산을 반복하면 pizza의 모든 부분 집합을 방문할 수 있다. for문은 subset = 0인 시점에서 종료하므로 공집합은 방문하지 않는다는 점을 깜빡하지 않도록 한다. 

 

 

---

 

위와 같이 비트마스크를 이용해 집합을 표현할 수 있다. 본 내용은 "프로그래밍 대회에서 배우는 알고리즘 문제해결전략2 - 비트마스크"의 내용 중 일부이다.