16장 비트마스크

neptunes032·2020년 9월 14일
0

종만북

목록 보기
2/6

비트마스크

내부적으로 이진수를 사용하는 컴퓨터들은 이진법 관련 연산들을 아주 빨리 처리한다. 이와 같은 특성을 이용해 정수의 이진수 표현을 자료 구조로 쓰는 기법을 비트마스크(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, 중)

  • 다시읽기
profile
개발자가 되고싶다.

0개의 댓글