Bitmask 에 대해

---

[서론]

스위치 4개가 있다고 생각해 보자. 

이 스위치가 각각 켜져 있거나, 꺼져 있는 경우를 나타내려면 어떻게 해야 할까? 

 

단순하게 생각해 보면 각 스위치마다 켜져 있는지, 꺼져 있는지에 대한 bool 값을 지정해 bool의 배열 형태로 나타내면 될 것이다.   

 

하지만 스위치가 백만 개, 천만 개라면 어떻게 스위치들의 상태를 나타낼 수 있을까?   

또한, 특정 스위치가 켜져 있는지 확인하려면 어떻게 해야 할까?   

 

이런 경우에도 앞서 말한 4개의 스위치가 있는 상황처럼 bool 배열을 이용해서 확인할 수는 있지만, 차지하는 메모리가 너무 많고 비효율적이다.

 

---

[개념]

전체 원소 집합 중, 각 원소들을 on/off 형태로 구분할 수 있을 때,

특정 원소들의 포함 여부를 한 번에 나타내고 싶은 경우 사용한다.

 

예를 들어, 스위치 5개에 대해 켜져 있는 상태를 1, 꺼져 있는 상태를 0이라 하자.   

이 때 스위치 1, 2, 5번이 켜져 있는 상태를 이진수 10011로 나타낼 수 있다.

(가장 오른쪽이 1번 스위치이다.)

 

[1, 4, 5번 스위치가 켜진 상태를 비트마스크로 나타낸 그림]

 

즉, 위 그림처럼 3개의 스위치가 각각 켜져 있는 상태를 하나의 정수로 표현할 수 있다.

 

이러한 특징은 문제 해결에서 인덱싱에 매우 유리하다.

특히 어떠한 상태마다 값을 저장해 문제를 해결하는 DP문제에서 종종 등장한다.

 

---

[사용]

상태를 비트로 나타내므로, 상태를 변화시키는 행동 역시 비트 연산을 통해 수행할 수 있다.

 

1. 위의 경우에서 3번 스위치를 켠 상태를 나타내고 싶은 경우

3번 스위치를 켰다면, 00100과 OR 연산을 한 결과가 새로운 상태가 된다.

 

2. 1의 결과에서 5번 스위치를 끈 상태를 나타내고 싶은 경우

변화시킬 특정 원소의 위치를 j라고 할 때,

 - ON : State | (1 << (j - 1))

 - OFF : State & ~(1 << (j - 1))

를 통해 새로운 상태를 유도할 수 있다.

 

마찬가지로, 특정 원소의 상태를 확인할 때에도,

 - CHECK : State & (1 << (j - 1))

를 통해 결과 bool로 확인할 수 있다.

 

---

 

[응용 문제]

BOJ1102_발전소 :  www.acmicpc.net/problem/1102