youl

youl

푸하하-자아자 ˘◡˘

[Algorithm] 비트마스크

3 분 소요

🙋‍♀️ 비트마스크(BitMask)?

이진수를 사용하는 컴퓨터 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법

  • 이진수는 0 또는 1을 사용하며, 하나의 비트는 이 두 경우로 표현된다.
  • 1일 경우에는 커져 있다, 0일 경우에는 꺼져 있다고 말한다.

🙋‍♀️ 비트마스크의 장점?

  1. 수행 시간이 빠르다.
    • 비트 연산의 경우 O(1)로 구현되는 것이 많아 빠르게 동작할 수 있다.
    • 연산 횟수가 적은 경우에는 속도 차이가 별로 없지만, 연산 횟수가 늘어날 경우 속도 차이가 커지게 된다.

  2. 코드가 짧다.

  3. 메모리 사용량이 더 적다.
    • 비트의 개수만큼 원소를 다룰 수 있다. 즉, 하나의 정수로 매우 많은 경우의 수를 다룰 수 있기 때문에 메모리 측면에서 효율적이다.
    • 예로 bit가 10개인 경우에는 각 비트마다 두 가지 경우가 존재하므로 2^10 경우를 표현 가능하다. * 비트에 값을 미리 계산에 저장해 둘 수 있기 때문에 DP에도 매우 유용하다.


🙃 비트 연산자

연산 비트 연산자 결과
AND a&b 각 비트마다 둘다 1일 경우 1, 아닐 경우 0
OR a|b 각 비트마다 하나라도 1일 경우 1, 아닐 경우 0
XOR a^b 각 비트마다 둘이 다를 경우 1, 같다면 0
NOT ~a 각 비트가 0이면 1로, 1이면 0으로
« a«b a를 b비트 만큼 왼쪽으로 시프트
» a»b a를 b비트 만큼 오른쪽으로 시프트

그렇다면 각각의 예를 살펴보자!! a= 111011, b= 011011 경우 각 연산의 결과를 살펴보자!

연산 비트 연산자 결과
AND a&b 011011
OR a|b 111111
XOR a^b 100111
NOT ~a 000100
« a«1 110110
» a»1 011101


🙋‍♀️ 집합과 비트

집합을 비트마스크를 이용해 쉽게 표현할 수 있다. 또한, 집합의 다양한 연산을 비트 연산을 통해서 빠르게 수행할 수 있다.

1부터 n까지의 원소가 있다면 각 원소가 비트의 한 자리로 표현이 된다. 그리고 자리의 비트가 1일 경우에는 집합에 포함, 0일 경우에는 집합에 불포함을 의미한다.

예를 들어 {1, 2, 3, 4, 5}의 집합의 경우를 생각해보자!!

  • 원소의 개수가 5개이므로 총 5bit로 해당 집합을 표현할 수 있다.
  • 부분집합 {3, 4, 5}는 다음과 같이 표현된다.
    • 각 원소마다 비트 자리 하나를 대응시켜 1, 0으로 표현한다.
    • 위 부분 집합은 00111로 표현이 된다.


🙃 집합 연산

연산 비트 연산자
원소 추가 val |= (1«p)
원소 삭제 val &= ~(1«p)
원소 토글 val ^= (1«p)
공집합 val = 0
꽉찬 집합(10개 원소) val = (1«10) -1


🙃 두집합 연산

연산 집합 연산자  
합집합 A// B
교집합 A&B  
차집합 A&(~B)  
두집합 중 하나에 포함된 원소들의 집합 A^B  


🙃 집합의 크기 구하기

집합의 크기는 비트 속 1의 개수이다. 따라서 모든 비트를 순회해야 하며, 다음과 같은 재귀적인 방식으로 구현할 수 있다.

def getSize(val):
  if val == 0:
    return 0
  
  return val%2 + getSize(val/2)


🙃 최소 원소

  • 최소 원소 얻기 
    first = val & (~val - 1)10010011

or

first = val & -val
    • 비트에서 가장 오른쪽에 있는 1의 원소를 찾는 과정이다.
  • 최소 원소 지우기 
    val &= (val-1)


🙋‍♀️ 모든 부분집합 순회하기

val = int('0b1011', 2)
subset = val

while 1:
  subset = (subset-1) & val

  if subset == 0:
    break

  print(bin(subset))
  #0b1010
  #0b1001
  #0b1000
  #0b11
  #0b10
  #0b1

🙌 예제) 백준: 집합

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

  • add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
  • remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
  • check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
  • toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
  • all: S를 {1, 2, …, 20} 으로 바꾼다.
  • empty: S를 공집합으로 바꾼다.


✍️ 풀이

해당 문제를 set()을 이용해 풀이할 수 있지만 집합 연산보다 훨 빠른 비트 연산을 이용해 문제를 풀이해보고자 한다!

비트마스크 적용하기

import sys

s = 0
n = int(input())
answer = 0

for _ in range(n):
  command = sys.stdin.readline().rstrip()

  if command == "all":
    answer = (1<<20)-1
  elif command == "empty":
    answer = 0
  else:
    op, val = command.split()
    val = int(val)-1
    if op == "add":
      answer |= (1<<val)
    elif op == "remove":
      answer &= ~(1<<val)
    elif op == "check":
      if answer & (1<<val) != 0:
        print(1)
      else:
        print(0)
    else:
      answer ^= (1<<val)


📝 참고 자료

댓글남기기

참고