비트마스크

비트

컴퓨터에서 사용되는 데이터의 최소 단위 (0과 1)

비트마스크 사용이유

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

비트 연산

• AND(&) : 대응하는 두 비트가 모두 1일 때, 1 반환
• OR(|) : 대응하는 두 비트 중 모두 1이거나 하나라도 1일때, 1 반환
• XOR(^) : 대응하는 두 비트가 서로 다를 때, 1 반환
• NOT(~) : 비트 값 반전하여 반환
• SHIFT(>>, <<) : 왼쪽 혹은 오른쪽으로 비트 옮겨 반환
  • i >≥ 1 은 i = i >> 1과 같음
  • i<≤ 1 은 i = i << 1과 같음

왼쪽 시프트 : A * 2^B
오른쪽 시프트 : A / 2^B
[왼  쪽] 0001 → 0010 → 0100 → 1000 : 1 → 2 → 4 → 8
[오른쪽] 1000 → 0100 → 0010 → 0001 : 8 → 4 → 2 → 1

비트마스킹 활용

• 0과 1로, flag 활용하기
  • 집합 : [1, 2, 3, 4 ,5]의 부분집합 구하기

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

• 집합의 i번째 요소가 존재하면 1, 그렇지 않으면 0을 의미 (맨오른쪽부터 1번째 인덱스)