[알고리즘] 비트마스크(BitMask)

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

왜 사용할까?

• DP, Permutation 등 배열 활용으로만 해결이 불가한 문제
• 작은 메모리와 빠른 수행시간으로 해결 가능(원소가 적다는 가정 하)
• 집합을 배열의 인덱스로 표현 가능
• 코드가 간결해짐

Bit?

• 컴퓨터에서 사용되는 데이터의 최소 단위(0,1) - 2진법을 생각하자

우리가 사용하는 10진수를 2진수로 바꾸면?

9(10진수) -> 1001(2진수)

비트마스킹 활용

0과 1로, flag 활용하기

[1,2,3,4,5]라는 집합이 있다.
여기서 임의로 몇 개를 골라 뽑아서 확인을 해야하는 상황이 주어졌다. (즉, 부분집합을 의미)
{1}, {2} , ... , {1,2} , ... , {1,2,5} , ... , {1,2,3,4,5}

물론, 간단히 for문을 돌려가며 배열에 저장하며 경우의 수를 구할 순 있다.
하지만, 비트마스킹을 하면, 각 요소를 인덱스처럼 표현하여 효율적인 접근이 가능하다.

[1,2,3,4,5] → 11111
[2,3,4,5]   → 11110
[1,2,5]     → 10011
[2]         → 00010

집합의 i번째 요소가 존재하면 1, 그렇지 않으면 0을 의미한다.
이러한 2진수는 다시 10 진수로 변환도 가능하다.

11111은 10진수로 31이므로, 부분집합을 정수를 통해 나타내는 것이 가능하다는 것을 알 수 있다.

• 31은 [1,2,3,4,5] 전체에 해당하는 부분집합에 해당한다는 것!

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

비트 연산

AND, OR, XOR, NOT, SHIFT

• AND(&) : 대응하는 두 비트가 모두 1일 때, 1 반환
• OR(|) : 대응하는 두 비트 중 모두 1이거나 하나라도 1일때, 1 반환
• XOR(^) : 대응하는 두 비트가 서로 다를 때, 1 반환
• NOT(~) : 비트 값 반전하여 반환
• SHIFT(>>,<<) : 왼쪽 혹은 오른쪽으로 비트 옮겨 반환
  • 왼쪽 시프트 : A * 2^B
  • 오른쪽 시프트 : A / 2^B

[왼  쪽] 0001 → 0010 → 0100 → 1000 : 1 → 2 → 4 → 8
[오른쪽] 1000 → 0100 → 0010 → 0001 : 8 → 4 → 2 → 1