비트마스크

비트마스크란

정수로 집합을 나타내는 방법이다.

포함이 되어있을 땐 1로 포함 되어있지 않을 땐 0으로 나타낸다.

570 같은 경우엔 2진수로 표현하면 1000111010(2)이다.

인덱스로 나타내면

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

570 = {9, 5, 4, 3, 1}을 포함하고 있는 집합이라고 할 수 있다.

길이가 N인 이진수는 0~N-1까지의 부분집합을 나타낼 수 있다.

1부터 ~ N까지의 부분집합을 나타내고 싶다면

add, remove, check, toggle을 할때 어떤 수 X를 -1 해주도록 하자.

 

* 어떤 수X가 집합에 포함되어 있는지를 검사할 때(check)

N & (1<<X)

1은 이진수로 1이다.

X가 1일 때

1<<X는 10이 된다.

N이 570일때 &연산을 하면

1000111010

             10

--------------&

              10

10진수로 바꾸면 2로 1이상이다.

if((570 & (1 << 1)) > 0)은 true로 570에 1이 포함되어 있다는 뜻이 된다.

 

비트마스크를 사용하는 이유는

어떤 집합을 배열의 인덱스로 표현할 수 있기 때문

이다.

상태 다이나믹에서도 자주 사용되며

완전탐색을 할 때도 모든 경우를 살펴볼 때 재귀호출 없이 for문 하나만으로도

모든 경우를 살펴볼 수 있기 때문이다.

 

* 어떤 수X를 집합에 추가할 때(add)

위와 똑같은 방식으로 비트연산자인 ' | ' 를 사용하면 된다.

N = N | (1<<X)

 

* 어떤 수X를 집합에서 제거할 때(remove)

위와 똑같은 방식으로 비트연산자인 ' & '과 '~' 을 사용하면 된다.

N = N & ~(1<<X)

 

* 어떤수 x가 있으면 x를 제거하고, 없으면 x를 추가한다(toggle)

비트연산자인 ' ^ ' 을 사용하면 된다. (XOR)

N = N ^ (1<<X)

 

* 전체집합

1부터 N까지의 전체 집합이 얻고싶다면

(1<<N) -1

만약 어떤 수 X를 -1하지않고 0~N-1의 부분집합을 사용하고 있다면

(1<<N+1) -1이 된다.

 

* 공집합으로 만들고 싶다면

0

 

https://www.acmicpc.net/problem/11723

11723번: 집합

이 문제를 통해 비트마스크를 복습하도록 하자.