16장 비트마스크

비트마스크

내부적으로 이진수를 사용하는 컴퓨터들은 이진법 관련 연산들을 아주 빨리 처리한다. 이와 같은 특성을 이용해 정수의 이진수 표현을 자료 구조로 쓰는 기법을 비트마스크(bitmask)라고 부른다.

비트마스크의 장점

• 더 빠른 수행 시간
  • 비트마스크 연산은 O(1)에 구현되는 것이 많다.
• 더 간결한 코드
  • 다양한 집합 연산들을 반복문 없이 한 줄에 쓸 수 있기 때문에 짧은 코드를 작성할 수 있다.
• 더 작은 메모리 사용량
  • 같은 데이터를 더 적은 메모리를 사용해 표현할 수 있다.

비트 연산자

• AND
  • a & b
• OR
  • a | b
• XOR
  • a ^ b
• NOT
  • ~a
• shift
  • a << b
  • a >> b

유의할 점들

1. 연산자간 우선순위 혼동
   • 비트마스크를 사용하는 식에서는 가능한 괄호를 자세하게 추가하자.
2. 64비트 정수를 비트마스크로 사용할 때
   • c++에서 1은 부호 있는 32비트 상수로 취급하기 때문에 오버플로우가 발생할 수 있다. 따라서 1ull을 사용한다.
3. N비트 정수를 N비트 이상 왼쪽으로 시프트 하는 경우
   • C++ 언어 명세에 정의되어 있지 않으므로 환경에 따라 결과가 다르다.

---

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

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

• 공집합과 꽉 찬 집합 구하기

  • int fullPizza = (1 << 20) - 1

• 원소 추가

  • toppings |= (1 << p)

• 원소의 포함 여부 확인

  • toppings & (1 << p )

• 원소 삭제

  • toppings &= ~(1 << p)

• 원소 토글

  • toppings ^= (1 << p)

• 합집합

  • (a | b)

• 교집합

  • (a & b)

• 차집합

  • (a & ~b)

• a와 b중 하나에만 포함되는 원소의 집합

  • (a ^ b)

• 집합의 크기

  • Visual C++ : __popcnt(toppings)
  • gcc/g++ : __builtin_popcount(toppings)

• 최소 원소 찾기

  • 켜져 있는 최하위 비트의 번호를 반환한다.
  • Visual C++ : _BitScanForward(&index, toppings)

• 최소 원소 지우기

  • toppings &= (toppings - 1)

• 모든 부분 집합 순회하기

  • 주어진 집합의 모든 부분 집합을 순회하기

  •  for(int subset = pizza; subset; subset=((subset - 1) & pizza){
    	//subset은 pizza의 부분집합
    }

---

비트 마스크 응용 예제

지수 시간 동적 계획법

에라토스테네스의 체

• 14.2

15퍼즐 상태 표현하기

• 29.6

O(1) 우선순위 큐

예제: 극대 안정 집합

---

문제: 졸업 학기(GRADUATION, 중)

• 다시읽기