[Algorithm] 비트마스크 이론
비트마스크란?
정수의 이진수 표현을 자료구조처럼 사용하는 기법이다. 이진수 0 또는 1로 표현되므로, 하나의 비트가 켜진 상태(1), 꺼진 상태(0)을 나타낼 수 있다.
정수 int의 경우 4byte(== 32bit)의 크기를 가진다. 이진수로 풀어서 표현하면 0000 0000 0000 0000 0000 0000 0000 0000 이다.
비트마스크의 장점
있거나 없거나 둘 중 하나의 상태를 표현할 때, bool 변수를 32개 쓰는 대신 정수 하나로 표현할 수 있으므로 메모리를 아낄 수 있다.
비트 연산이므로 O(1)에 구현할 수 있는 연산이 많아 수행 시간이 빠르다.
비트마스크를 이용한 집합 구현
공집합 만들기
- s 집합 : 0000 0000 0000 0000 0000 0000 0000 0000
1
int s = 0;
K번째 비트 켜기
(1 << K): 1을 K칸 왼쪽으로 이동한다. K가 3이라면1 > 10 > 100 > 1000이다.s |=:OR연산 후s에 대입한다. 4비트만 쓴다고 가정한다면0000 | 1000 = 1000, 이것을 s에 대입하면 0번째 비트부터 시작해서 3번째 비트만 1로 켤 수 있다.
1
s |= (1 << K);
K번째 비트 끄기
~(1 << K):1 > 10 > 100 > 1000에서 1과 0을 바꿔서0111이다.s &=:AND연산 후s에 대입한다. 4비트만 쓴다고 가정한다면0000 | 0111 = 0000, 이것을 s에 대입하면 0번째 비트부터 시작해서 3번째 비트를 끌 수 있다.
1
s &= ~(1 << K);
0번째부터 K번째까지 비트 켜기
K가 3일 때,
(1 << 3):10000 0000-1:1111 1111
1
s = (1 << K) - 1;
K번째 비트 포함 여부
- K가 3일 때,
1000 & 1000 = true,0000 & 1000 = false
1
if((s & (1 << K)))
K번째 비트 toggle
1
s ^= (1 << K);
집합의 최소 원소 끄기 가장 오른쪽에 있는 1을 0으로 바꾼다.
1
s &= (s - 1);
두 집합 연산
1
2
3
4
A | B // 합집합
A & B // 교집합
A &(~B) // A에서 B를 뺀 차집합
A ^ B // A와 B 중 하나에만 포함된 원소들의 집합
재귀를 이용해 집합의 크기 구하기
1
2
3
4
int getSetSize(int s) {
if(s == 0) return 0;
else return s%2 + getSetSize(s/2);
}