[BIT] Bit Mask

[BIT] Bit Mask

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

왜 Bit Mask를 사용하는가?

• DP나 순열 등 배열 활용 만으로 해결할 수 없는 문제
• 작은 메모리와 빠른 수행 시간으로 해결 가능 (원소 개수 많으면 안 됨)
• 집합을 배열인 인덱스로 표현 가능
• 코드가 간결해짐

Bit?

컴퓨터에서 사용하는 데이터의 최소 단위(0과 1, 2진법)

BitMask 활용

0과 1의 flag로 사용

• [0, 1, 2, 3, 4, 5] 라는 집합이 있다고 하자.
• 위의 집합의 부분 집합은 아래와 같다.

  {0}, {0, 1}, {0, 2}, … , {0, 1, 2}, … , {0, 1, 2, 3, 4}, … , {0, 1, 2, 3, 4, 5}

• loop를 통해 경우의 수를 구할 수 있다.
• 하지만 아래와 같이 Bit Masking을 한다면?

  0 = 000001 1 = 000010 2 = 000100 3 = 001000 4 = 010000 5 = 100000

  {0, 2} > 000101 {0, 1, 2} > 000111 {0, 1, 2, 3, 4, 5} > 111111

• i라는 요소를 추가하고 싶으면 i + 1번째 비트를 1로 바꾸고, 빼고 싶으면 i + 1번째 비트를 0으로 바꾸면 된다!
• 또한, 2진법을 10진법으로 바꿔 부분 집합을 정수로 나타낼 수 있다.

비트 연산 (기본)

and, or, xor, not, shift

• and(‘&’) : 두 비트가 모두 1일 때 1 반환.

• or(‘	’) : 두 비트 중 하나라도 1일 때 1 반환.

• xor(‘^) : 두 비트가 서로 다를 때 1 반환.
• not(‘~’) : 비트의 1과 0을 반대로 반환.
• shift(‘»’, ‘«’) : 왼쪽 혹은 오른쪽으로 비트를 옮겨 반환.

비트 연산 (심화)

삽입, 삭제, 조회

• 삽입 (shift, or)
  • 현재 이진수가 10101일 때 i번째 비트 값을 1로 변경하려 한다.
  • i = 3이면 아래와 같이 연산을 활용한다. 10101 | 1 « 3

  • 1 « 3을 하면 $01000$이 되고, 이를

    연산을 활용하면 $11101$이 된다.

• 삭제 (shift, not, and)
  • 현재 이진수가 11101일 때 i번째 비트 값을 0으로 변경하려 한다.
  • i = 3이면 아래와 같이 연산을 활용한다. 11101 & ~1 « 3
  • ~1 « 3을 하면 $10111$이 되고, 이를 & 연산을 활용하면 $10101$이 된다.
• 조회 (shift, and)
  • i번째 비트의 값을 알기 위해선 아래와 같은 연산을 하면 된다. 11101 & 1 « 3
  • 만일 3번째 비트가 1이라면 1, 0이라면 0이 반환될 것이다.