문제
비트마스크
비트마스크에 대해서 처음 알게 된 문제다. 이전에 1«n 은 사용해서 제곱을 구현해본적은 있었지만 &,|와 같은 다양한 연산을 사용할 수 있다는 것을 알았다.
비트 마스크는 알고리즘이라기 보다는 bit를 활용한 테크닉이다.
- And 연산 (&): 대응하는 두 비트가 모두 1이면 1 반환
1010 & 1111 = 1010 - OR 연산 ( | ): 대응하는 두 비트 중 하나라도 1이면 1 반환
1010 & 1111 = 1111 - Shift 연산 («,») : 비트를 왼쪽 또는 오른쪽으로 한칸씩 이동
0011 « 2 = 1100
1010 » 1 = 0101 - XOR 연산 (^): 대응하는 두 비트가 다르면 1 같으면 0 반환
1010 ^ 1100 = 0110 - Not 연산 (~) : 비트를 반전
~1111 = 0000
풀이
비트 마스크를 사용하기 위해 이진수의 자리순서와 입력 되는 수를 매칭 시킨다. 예를 들어 add 3,add 2, add 1이 입력되면 BIT는 1000 -> 1100 -> 1110이 된다. 입력되는 수가 1<=x<=20이기 때문에 32비트의 크기인 int 형식을 사용하여 구현할 수 있다.
소스 코드
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
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <string>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int m;
cin >> m;
string order;
int val, BIT = 0; // BIT를 반드시 0으로 초기화 해준다.
while (m--)
{
cin >> order;
if (order == "add")
{
cin >> val;
// or 연산자를 통해 val번째 자리수를 1로 채운다.
BIT |= (1 << val);
}
else if (order == "remove")
{
cin >> val;
// ex) 1000 & ~(1000) = 0000
BIT &= ~(1 << val);
}
else if (order == "check")
{
cin >> val;
if (BIT & (1 << val))
cout << 1 << '\n';
else
cout << 0 << '\n';
}
else if (order == "toggle")
{
cin >> val;
// BIT의 val번째 자리가 1이라면 1^1=0이 되어 1->0이 되고
// val번째 자리가 0이라면 0^1=1 이 되어 0 -> 1이 된다.
BIT ^= (1 << val);
}
else if (order == "all")
{
// ex) 10000 - 1 = 1111
BIT = (1 << 21) - 1;
}
else if (order == "empty")
{
BIT = 0;
}
}
return 0;
}
