비트마스크(BitMask)

비트마스크(BitMask)

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

사용 이유

• DP나 순열 등, 배열 활용만으로 해결할 수 없는 문제를 해결하기 위해서.
• 작은 메모리와 빠른 수행시간으로 해결이 가능하다.
  • 원소의 수가 많지 않아야 한다.
• 집합을 배열의 인덱스로 표현할 수 있다.
• 코드가 간결해진다.

비트(Bit)란?

• 컴퓨터에서 사용되는 데이터의 최소 단위

비트 연산

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

1. 삽입

• 삽입의 경우 OR 연산을 활용한다.

2. 삭제

• 삭제의 경우 AND 연산과 NOT 연산을 활용한다.

3. 조회

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