tech blog

1 분 소요


비트 마스크란?

컴퓨터는 내부적으로 모든 연산을 이진수로 표현하고 처리한다. 이런 특성을 이용해서 정수의 이진수 표현을 자료구조로 쓰는 기법을 비트 마스크 라고 한다.



비트 연산자

파이썬의 기본 비트 연산자를 먼저 살펴보자.

AND, OR, XOR

  • AND 연산 (&) : 두 비트가 모두 1일 때, 1을 반환한다.
  • OR 연산 (l) : 두 비트가 하나라도 1이면, 1을 반환한다.
  • XOR 연산 (^) : 대응하는 두 비트가 서로 다르면 1을 반환한다.
1100 & 1011 = 1000
1010 | 1111 = 1111
1010 ^ 1111 = 0101


NOT

  • NOT 연산 (~) : 비트의 값을 뒤집어서 반환
~1010 = 0101


Shift 연산

  • left shift («) : 왼쪽으로 비트 이동 (X * 2^Y)
  • right shift (») : 오른쪽으로 비트 이동 (X / 2^B)
00001010 << 2 = 101000
00001010 >> 2 = 000010


집합과 비트마스크

비트 마스크를 사용하면 집합을 굉장히 효율적으로 표현할 수 있다. 예를 들어 10개의 방문 체크를 해야 하는 상황이라고 가정하자.
그러면 check = [False] * 10 와 같이 리스트로 표현하는 것이 일반적일 것이다.
그런데 비트 마스크를 사용하면 check = 0b0000000000 와 같이 표현할 수 있다. 메로리를 훨씬 적게 사용하고 연산도 모두 O(1) 이기 때문에 굉장히 효율적이다.

집합의 연산과 비트 마스크

이제 비트 마스크를 활용한 집합의 연산에 대해서 알아보자.

  • 원소 추가
S |= (1 << x)

집합 S에 x를 추가하려고 할 때, S의 x번 비트만 1로 만들어주면 된다.


  • 원소 삭제
S &= ~(1 << x)

집합 S에서 x를 삭제할 때, S의 x번 비트를 0으로 만들어주면 된다.


  • 원소 토글
S ^= (1 << x)

집합 S에 x가 있다면 삭제하는 연산이다.


  • 원소 체크
1 if S & (1 << int(li[1])) != 0 else 0

집합 S에 원소가 있으면 1을 반환, 없으면 0을 반환해주는 연산이다.


  • 원소 비우기, 채우기
S = 0 # 비우기
S = (1 << 21) - 1  #채우기

원소를 비우기 위해서 S의 모든 비트를 0으로 만들어주면 된다. 채울때는 모든 비트를 1로 만들어주면 된다. 1 « 21 을 통해서 집합 수보다 1만큼 큰 비트 sequence를 만들어주고 1을 빼면 집합길이(20) 만큼의 1로 채워진 집합이 된다.


집합 연산

당연히 집합간의 연산도 가능하다. 

A | B # 합집합
A & B # 교집합
A & ~B # 차집합 (A - B)
A ^ B # A와 B중 하나만 속한 원소



참고 사이트 출처

  • https://velog.io/@1998yuki0331/Python-%EB%B9%84%ED%8A%B8-%EB%A7%88%EC%8A%A4%ED%82%B9-%EC%A0%95%EB%A6%AC

참고