비트마스크

집합의 요소들의 구성 여부를 표현할 때 유용한 테크닉

왜 비트마스크를 사용하는가?

• DP나 순열 등, 배열 활용만으로 해결할 수 없는 문제
• 작은 메모리와 빠른 수행시간으로 해결이 가능 (But, 원소의 수가 많지 않아야 함)
• 집합을 배열의 인덱스로 표현할 수 있음
• 코드가 간결해짐

비트마스크는 2진법으로 사용하는 것을 비트마스크라고 합니다.

 

예시)

[1,2,3,4,5]라는 집합이 있을때 임의로 몇개를 골라서 뽑는 경우를 구한다고 해보자.

 

원래라면 각 배열의 요소를 for문을 통해 접근하면서 확인해야 할 것이다. 하지만 비트마스킹으로 구현하게 되면 int 하나로 표현이 가능하다.

 

[1,2,3,4,5] => 11111 => 31

[1,2,3] => 00111 => 7

[1,2,5] => 10011 => 19

 

이로써, 해당 부분집합에 i를 추가하고 싶을때 i번째 비트를 1로만 바꿔주면 표현이 가능해졌다.

이런 행위는 비트 연산을 통해 제어가 가능하다.

 

비트연산

• AND(&): 대응하는 두 비트가 1일때, 1반환
• OR(&): 대응하는 두 비트중 적어도 하나가 1일때 1반환
• XOR(^): 대응하는 비트가 다를때 1반환
• NOT(~): 비트값을 반전
• SHIFT(<<, >>): <<의 경우 왼쪽으로 해당수만큼 비트를 옮김(2의 배수만큼 곱해짐). >>의 경우 해당수만큼 오른쪽으로 비트를 옮김.(2의배수만큼 나눠짐)

1.삽입
현재 이진수로 10101로 표현되고 있을 때, i번째 비트 값을 1로 변경하려고 한다.

i = 3일 때 변경 후에는 11101이 나와야 한다. 이때는 OR연산을 활용한다.

10101 | 1 << 3
1 << 3은 1000이므로 10101 | 01000이 되어 11101을 만들 수 있다.

2.삭제
반대로 0으로 변경하려면, AND연산과 NOT 연산을 활용한다.

11101 & ~1 << 3
~1 << 3은 10111이므로, 11101 & 10111이 되어 10101을 만들 수 있다.

3.조회
i번째 비트가 무슨 값인지 알려면, AND연산을 활용한다.

10101 & 1 << i

3번째 비트 값 : 10101 & (1 << 3) = 10101 & 01000 → 0
4번째 비트 값 : 10101 & (1 << 4) = 10101 & 10000 → 10000

이처럼 결과값이 0이 나왔을 때는 i번째 비트 값이 0인 것을 파악할 수 있다. (반대로 0이 아니면 무조건 1인 것)

이러한 방법을 활용하여 문제를 해결하는 것이 비트마스크다.

 

 

2098번 외판원 순회

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

2098번: 외판원 순회

 

 

 

 

14257번

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

14257번: XOR 방정식

 

 

 

 

1106번

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

1106번: 호텔

 

2234번

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

2234번: 성곽