프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 2권 참고

비트마스크

 이진수 표현을 자료 구조로 쓰는 기법을 비트마스크(Bitmask)라고 한다.
엄밀하게 말해 자료 구조라고 할 수는 없지만 굉장히 유용하게 사용된다.

장점

• 더 빠른 수행 시간
• 더 간결한 코드
• 더 작은 메모리 사용량
• 연관 배열을 배열로 대체

비트 연산자

• AND
• OR
• XOR
• NOT
• shift

    *비트 연산자는 우선순위는 ==, !=등의 비교 연산자보다 낮다.
     int c = (6 & 4 == 4)이면 4 == 4부터 연산이 진행된다

    *shift연산 시 새로 채워지는 결과는 환경에 따라 달라질 수 있다.

비트마스크를 이용한 집합의 구현

 비트마스크의 가장 중요한 사용 사례는 집합을 구현하는 것이다.

 원소 i가 집합에 속해 있는지 여부는 2^i을 나타내는 비트가 켜저 있는지 여부를 나타낸다.

 ex {1,4,5,6,7}가 표현하는 정수는 754

  2^1+2^4+2^5+2^6+2^7+2^9 = 10 111 0010(2) = 754

활용 예

 피자집 예제) 

 0~19 까지의 번호를 갖는 20가지의 피자 토핑이있다. 이것을 비트마스크를 이용하면 다양한 비트 연산을 이용해 집합 연산을 빠르고 간단하게 구현할 수 있습니다.

스무 개의 토핑을 모두 포함 = int fullPizza = (1 << 20) - 1;
1 << 20은 이진수로 1뒤에 20개의 0이 있는 정수인데, 여기서 1을 빼면 20개의 비트가 모두 1로 바뀐다.

• 원소 추가 toppings |= (1 << p)
• 원소 포함 확인 if(toppings & (1 << p)) cout <<~~
• 원소 삭제 toppings &= ~(1 << p)
• 원소 토글 toppings ^= (1 << p)