비트마스크를 이용한 집합 구현은 가장 대표적이고, 중요한 사례이다. "하나의 bit가 하나의 원소"를 의미하게 된다.
bit가 켜져 있으면 해당 원소가 집합에 포함되어 있다는 의미이고, 꺼져 있으면 포함되어 있지 않다는 의미이다.
따라서 N비트 정수 변수라면 N개의 원소를 갖는 집합의 부분집합들을 모두 표현할 수 있게 된다.
원래는 N개의 boolean 원소를 갖는 배열을 선언해야 했지만, 비트마스크를 이용하면 정수 하나로 표현이 가능하기 때문에 사용하는 메모리의 크기가 많이 줄어드는 장점이 있다.
이제 비트연산자를 통해서 집합을 어떻게 효율적으로 다룰 수 있는지 알아보자.
우선, A라는 변수를 집합이라고 가정하고, 집합의 총원소의 개수를 10개라고 가정하겠다. (0번째 ~ 9번째 원소)
- 집합의 크기 구하기 int bitCount(int A){
if(A == 0) return 0;
return A%2 + bitCount(A / 2);
}
gcc/g++ → __builtin_popcount(A)
visual C++ → __popcnt(A)
Java → Integer.bitCount(A)
최소 원소 찾기 int first = A & (-A);
최소 원소 지우기 A &= (A - 1);
모든 부분 집합 순회하기 for (int subset = A ; subset ; subset = ((subset - 1) & A)){ }
반대로 꽉 찬 집합은 bit가 모두 켜진 상황이기 때문에 1111111111(2) 의 값을 가져야 하는데, 이는 (1<<10) - 1 과 동일하다. 1<<10은 10000000000(2) 이므로 1을 빼면 10개의 bit가 모두 켜진 수를 얻을 수 있다.
이미 A에 원소가 포함되어 있는 경우에는 아무런 변화가 없게 된다.
따라서 A -= (1<<k); 로 작성하면 된다. 하지만 이 경우는 A에 반드시 k번째 원소가 포함되어 있는 경우에만 가능하다. 만약 포함되어 있지 않은 경우에는 다른 원소의 포함 여부까지 바꿔버리기 때문이다.
그러므로 A에 k번째 원소의 포함 여부와 상관없이 해당 bit를 끄기 위해서는 AND연산을 이용해야 한다.
1<<k는 k번째 bit만 켜진 상태이며, 여기에 NOT을 씌우면 k번째 bit만 꺼진 상태가 된다.
그러므로 AND 연산을 적용하면 k번째 bit만 0이 되고 나머지 bit는 변함이 없다.
컴퓨터는 2의 보수를 이용하여 음수를 표현하기 때문에 -A를 표현하기 위해서 ~A + 1을 이용한다.
A에서 가장 오른쪽에 켜진 bit의 인덱스를 k라고 한다면, k보다 오른쪽에 있는 모든 bit는 0이다.
따라서 NOT 연산을 적용한 ~A는 k번째 bit는 0이고, 오른쪽의 모든 bit는 1이 된다.
여기서 ~A에 1을 더해주게 되면 k번째보다 오른쪽에 있는 bit는 모두 0이 되고, k번째 bit는 1이 된다. k번째 bit보다 왼쪽에 있는 bit는 아무런 변화가 없다.
따라서 -A와 A를 AND 시키면 k번째 bit만 켜진 상태로 남게 된다.
위의 설명들을 토대로 코드에 직접 예시를 넣어보면 쉽게 이해가 갈 것이다.