알고리즘 문제 해결 전략2 16장 비트마스크(2)

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

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

피자집 예제

한 피자의 정보는 스무 종류의 원소만을 가지는 집합이 되고, 비트마스크를 이용해 표현할 수 있음. 

공집합과 꽉 찬 집합 구하기 : 1<<20은 이진수로 1 뒤에 20개의 0이 있는 정수임, 여기서 1을 빼면 20개의 비트가 모두 켜진 수를 얻을 수 있음. 

원소의 포함 여부 : if(toppings & (1<<p)) cout << "pepperoni is in" << endl; & 연산의 결과값이 0 또는 1<<p 라는 점을 유의하세요. 대부분의 논리 연산처럼 원소가 포함되어 있는 경우 1, 혹은 true가 반환된다고 생각하면 실수를 범하게 됨.

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

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

집합의 크기 구하기 : 비트마스크를 이용할 때 집합에 포함된 원소의 수를 구하는 쉬운 방법은 없음. 각 비트를 순회하면서 켜져 있는 비트의 수를 직접 세는 수밖에 없음. 

32비트 부호 없는 정수 toppings에 켜진 비트의 수를 구하는 코드는 gcc/g++ 일 때 __builtin_popcount(toppings), visual C++ 일 때, __popcnt(toppings), Java는 Integer.bitCount(toppings) 이렇게 사용할 수 있음.

최소 원소 찾기 : 집합에 포함된 가장 작은 원소를 찾는 것. 켜져 있는 최하위 비트 밑의 비트들은 전부 0임. 이 연산은 켜져 있는 최하위 비트의 번호를 반환하게 됨. 최하위 비트의 번호 대신 해당 비트를 직접 구하고 싶으면 어떻게 해야함? 음수를 표현하기 위해 2의 보수를 사용한다는 점을 이용함. 2의 보수를 사용하는 시스템에서는 음수를 표현하기 위해 비트별 NOT연산을 적용하고 그 결과에 1을 더함. 이 기법은 24.6절에서 다루는 자료 구조인 펜윅 트리에서 유용하게 사용됨

최소 원소 지우기 : toppings &= (toppings - 1); toppings -1의 이진수 표현은 toppings에서 켜져 있는 최하위 비트를 끄고 그 밑의 비트들을 전부 켠 것입니다. 이 방법은 어떤 정수가 2의 거듭제고 값인지 확인할 때도 유용하게 쓰임. 2의 거드제곱 값들의 이진수 표현에는 켜진 비트가 하나밖에 없기 때문에, 최하위 비트를 지웠을 때 0이 된다면 주어진 수는 2의 거듭제곱임. 

모든 부분 집합 순회하기 : 다음 부분 집합을 구하는 식(subset-1)&pizza. for문은 subset=0인 시점에서 종료하므로 공집합은 방문하지 않는다는 점을 주의해야 함.