[python] 비트마스킹

***비트마스킹 : 정수로 표현된 2진수 숫자 자체를 자료구조로서 활용하는 것

일반적인 코딩테스트 문제에서, 경우의 수 30-31 가지 이상의 상황에서는 비트마스킹을 활용하기 어렵습니다.

시간복잡도의 문제로 시간초과가 나기 쉽기 때문입니다.  ( 2^30 = 1,073,741,824 )

그럼에도 불구하고 비트연산을 활용하면 다른 자료구조를 사용했을 때보다

획기적으로 연산 시간을 줄 일 수 있을 때가 많습니다.

또한 펜윅트리에서 비트마스킹은 매우 유용합니다.

1. 비트 연산자

AND	&                ( 1 & 1 == 1 )
OR	|                 ( 1 | 0 == 1 )                   ( 1 | 1 == 1 )
XOR	^                 ( 1 ^ 0 == 1 )                     ( 1 ^ 1 == 0 )
NOT	~        ( ~1010 == 0101 )
[SHIFT]  1 << num	1 << 3 == 1000
[SHIFT]  num >> 1	2 >> 10111 == 101

 

2.  활용    -    예시) 하나의 피자에 선택/취소 할 수 있는 토핑 20가지가 존재하는 상황

공집합	bit = 0	피자 토핑 20개 모두 선택 안함
꽉찬 비트 집합	bit = ( 1 << 20 ) - 1	피자 토핑 20개 모두 선택
비트 추가	bit |= ( 1 << number )	특정 토핑 추가
비트 삭제	bit &= ~ ( 1 << number )	특정 토핑 삭제하기
비트 토글	bit ^= ( 1 << number )	특정 토핑을 이미 선택했으면 취소하고  선택하지 않았으면 추가하기
켜져있는 최하위 비트 구하기 (보수 활용)	smallestbit = bit & -bit
최하위 비트 삭제	bit &= ( bit - 1 )
모든 비트 순회	for i in range( 1<<비트자리수 ) :    for j in range( 1<<비트자리수):         if i & (1 << j ) : print("exist")

 

3.  활용    -    예시) 두 집합 A와 B의 연산

합집합	result = Abit | Bbit
교집합	result = Abit & Bbit
차집합 ( A-B )	result = Abit | ~Bbit
( A - B) U ( B - A )	result = Abit ^ Bbit
집합 크기 구하기	def bitSize ( bit ) :       if  bit == 0 : return 0       ret = bit % 2 + bitSize( bit // 2 )       return ret
모든 부분 집합 순회	i = bit while i : print( i ) ; i = ( i - 1 ) & bit

 

4.  사용 빈도 높은 연산들

idx 번째 비트 끄기	bit  &= ~ ( 1<< idx )
idx 번째 비트 켜기	bit  |= ( 1 << idx )
idx 번째 비트 토글	bit  ^= ( 1 << idx )
idx 번째 비트 유무 확인	if bit & ( 1 << idx ) : print( "EXIST" )
최하위 켜져있는 idx 찾기	idx = ( bit & -bit )
크기가 n인 집합의 모든 비트 켜기	bit = ( 1 << n ) - 1

 

설명을 최소화 하고, 제 경험상 가장 유용했던 연산 중심으로 정리했습니다.

다음 게시글부터는 코드의 가독성을 고려하여 포스팅할 예정입니다.