최근 수정:
Bitmask.
비트 연산을 통해 집합을 표현. 정수로 부분집합을 표현할 수 있다.
집합을 구현할 때 int형 원소일 경우, 저장하려면 4바이트[1]가 필요하다. 하지만, 비트마스크를 사용하면 1비트면 충분하다. 이론 상으로 32배의 공간 효율.
대충 눈치 챘겠지만, 해당 원소의 값의 비트를 1로 하면 집합에 존재, 0이면 존재하지 않는 방식으로 구현 가능하다.
예를들면, 집합이 {1, 3, 5, 7, 9}이면 각각 해당 값 자리의 비트를 1로 하면 된다. 이진수로 나타내면 1010101이 된다. 이는 비트 연산 |(or)이나 &(and)로 쉽게 구현 가능하다.
특히 비트마스크의 최대 장점은 원소가 존재하는지 판별이 매우 쉽다는 것이다. &연산 한 번이면 원소가 존재하는지 알 수 있다. 예를 들어 3이 존재하는지 보려면 (1 << 3) & bitmask 이런 식이면 바로 알 수 있다. 집합을 벡터나 리스트 등으로 저장한다면 모든 인덱스를 뒤져야 하지만 비트마스크 방식은 1번 조회하면 끝난다.
위에서 말한 것처럼 집합을 표현하는데 사용하며 DP 문제를 풀 때 배열의 인덱스로 사용된다. 비트마스크는 주로 정수 (int, long long 등)으로 나타내므로 배열의 인덱스로 사용 가능하다. [2]
[1] 32비트 기준