문제
풀이
비트마스크에 대해 알게된 문제이다.
비트마스크는 예를 들어 {E, D, C, B, A}의 부분집합 {C, A}를 00101(2)과 같이 표현하는 것을 의미한다.
비트마스크 연산자에는 다음과 같다.
- AND 연산(&),
- OR 연산(ㅣ),
- XOR 연산(^) : 같으면 0을, 다르면 1
- NOT 연산(~),
- Shift 연산(« : 오른쪽으로 이동, » : 왼쪽으로 이동)
비트 연산자에는 주의할 점이 있다고 한다.
첫째, 비트 연산자들의 우선순위는 비교 연산자보다 낮다. 그러므로, 비트 연산자에는 가급적 괄호를 이용해준다.
둘째, 오버플로우이다. int형은 32bit까지만 가능하다. 그러므로, 1«32 이상의 연산은 오버플로우 문제가 생기므로 자료형을 주의하자.
다음은 비트 마스크를 이용한 집합 구현이다.
- 공집합과 꽉 찬 집합 구하기 : A = 0 / A = (1«10)-1
- 원소 추가 : A ㅣ= (1«k)
- 원소 삭제 : A &= -(1«k)
- 원소의 포함 여부 확인 : if(A & (1«k))
- 원소의 토글(해당 원소가 포함되어 있다면 0을, 아니면 1) : A ^= (1«k)
- 최소 원소 찾기 : int first = A & (-A) (-A = ~A + 1 이다.)
- 최소 원소 지우기 : A & = (A - 1)
- 모든 부분 집합 순회하기 : for(int subset = A; subset; subset = ((subset - 1) & A)) { }
- 집합의 크기 구하기
1 2 3 4
int bitcount(int A){ if(A==0) return 0; return A%2 + bitcount(A/2); }
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
using namespace std;
int main(){
/*
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
*/
int N;
cin >> N;
string order;
int bit = 0;
int value;
while(N--){
cin >> order;
if(order == "add"){
scanf("%d", &value);
bit |= (1<<value);
}
else if(order == "remove"){
scanf("%d", &value);
bit &= ~(1<<value);
}
else if(order == "check"){
scanf("%d", &value);
if(bit & (1<<value)){
printf("1\n");
}
else printf("0\n");
}
else if(order == "toggle"){
scanf("%d", &value);
bit ^= (1<<value);
}
else if(order == "all"){
bit = (1<<21) - 1;
}
else if(order == "empty"){
bit = 0;
}
}
}
