[알고리즘] 비트마스크

비트마스크이란? 

비트마스크는 이진수 표기법의 특징을 활용한 비트 연산을 이용해 부분집합을 표현하는 것이다.

비트 마스크를 이용하면 더 빠른 수행 시간, 더 간결한 코드, 더 적은 메모리 사용이라는 효과를 얻을 수 있다.

비트의 연산

A		1	0	1	0	10
B		0	1	1	0	6
A & B	AND 연산 : 둘다 1이면 1, 아니면 0	0	0	1	0	2
A | B	OR 연산 : 둘다 0이면 0, 아니면 1	1	1	1	0	14
A ^ B	XOR 연산 : 둘이 다르면 1, 아니면 0	1	1	0	0	12
~A	NOT 연산 : 0이면 1, 1이면 0	0	1	0	1	5
B << 1	왼쪽 시프트 : X비트 만큼 왼쪽으로 이동	1	1	0	0	12
A >> 1	오른쪽 시프트 : X비트 만큼 오른쪽으로 이동	0	1	0	1	5

시프트 연산은 X비트만큼 2를 곱하고 나누는 것과 같다. (2의 X제곱을 곱하고 나누는 것과 동일)

비트마스크의 집합의 표현

1. 비트마스크를 통해 집합을 정수로 나타낼 수 있다.
2. 집합에 저장할 수 있는 수의 범위가 정해져 있어야 한다. (최대 값)
3. 0부터 N - 1까지 N 개의 정수로 이루어진 집합을 나타낼 때 사용한다. 

7	6	5	4	3	2	1	0
1	0	1	0	1	1	1	0

• 집합 {1, 2, 3, 5, 7}를 이진수표기법을 이용해 10101110(2)으로 표기하면 174이라는 정수 하나로 표기가 가능하다. 
• 집합 {A, B, C, D, E, F, G, H}에서 {B}을 부분집합을 01000000(2) = 64, {F, H}를 00000101(2) = 5로 표기가 가능하다.

비트마스크의 연산

1. 원소 확인

• S | (1 << X)
• X번째 비트만 1로 두고 AND 연산을 해서 S의 X번째 비트가 1인지 0인지 확인한다.

2. 원소 추가

• S | (1 << X)
• X번째 비트만 1로 두고 OR 연산을 해서 S의 X번째 비트를 1로 변경해 추가한다.

3. 원소 삭제

• S & ~(1 << X)
• X번째 비트만 0로 두고 AND 연산을 해서 S의 X번째 비트를 0으로 변경해 삭제한다.

4. 원소 토글

• S ^ (1 << X)
• X번째 비트만 1로 두고 XOR 연산을 해서 S의 X번째 비트가 1이면 0으로 0이면 1로 변경해 상태를 변경해 준다.

정리

• 하나의 집합 덩어리를 하나의 정수로 사용해 더 적은 메모리를 사용한다.
• 비트 하나를 가지고 연산하기 때문에 시간복잡도가 O(1)로 빠르다.

활용 문제

• 백준 1094번 문제 : https://www.acmicpc.net/problem/1094
• 백준 1052번 문제 : https://www.acmicpc.net/problem/1052
• 백준 9527번 문제 : https://www.acmicpc.net/problem/9527