[파이썬으로 배우는 알고리즘] 비트마스크(BitMask)

비트마스크(BitMask)란?

 

컴퓨터는 내부적으로 모든 데이터를 이진수로 표현을 합니다. 예전에 c언어로 비트 체계와 비트 연산자를 간단히 다룬 적이 있는데 비트에 대해서 궁금하신 분들은 참고하시면 될 것 같아요.

 

2020.07.17 - [프로그래밍언어/c언어] - C언어 독학 #7. 비트 체계와 비트 연산자

C언어 독학 #7. 비트 체계와 비트 연산자

 

비트의 특성을 이용해서 이진수 표현을 자료구조로 쓰는 기법을 비트마스크라고 하며 엄밀히 말하면 알고리즘이라기보다는 일종의 테크닉이라고 볼 수 있겠습니다. 

 

---

비트마스크의 장점

 

1) 빠른 수행 시간

비트마스크는 bit 연산이기 때문에 시간 복잡도가 O(1)로 동작하는 것이 많습니다. 따라서 다른 자료구조보다 빠른 것을 알 수 있습니다.

2) 간결한 코드

다양한 집합 연산을 한 줄로 표현하여 간결한 코드 작성이 가능합니다.

3) 적은 메모리 사용량

많은 수를 표현하기에 효율적입니다. 예를 들어 10개의 비트는 2^10가지의 경우를 나타낼 수 있습니다. 

---

비트 연산자

 

연산자	설명	예시
&	AND 연산. 비교하는 비트가 둘 다 참일 때만 만족	a = 0011(2) = 3 b = 0110(2) = 6 a & b = 0010(2) = 2
|	OR 연산. 비교하는 비트가 둘 중 하나라도 참이면 만족	a = 0011(2) = 3 b = 0110(2) = 6 a | b = 0111(2) = 7
^	XOR 연산. 비교하는 비트가 둘 중 하나만 참일때만 만족	a = 0011(2) = 3 b = 0110(2) = 6 a ^ b = 0101(2) = 5
~	NOT 연산. 보수 연산으로 0 -> 1, 1 -> 0	a = 0011(2) = 3 ~a = 1100(2) = 12
<<	왼쪽 시프트 연산. 변수의 값을 지정된 값의 비트만큼 왼쪽으로 이동	a = 0011(2) = 3 a << 2 = 1100(2) = 12
>>	오른쪽 시프트 연산. 변수의 값을 지정된 값의 비트만큼 오른쪽으로 이동	b = 0110(2) = 6 b >> 1 = 0011(2) = 3

 

---

비트마스크를 이용한 집합 표현

 

비트마스크를 이용하면 집합을 쉽게 표현할 수 있습니다. 원소의 개수가 n개인 집합이 있다고 하면, 각 원소에 0부터 n-1까지의 번호를 부여하여 부분집합을 나타낼 수 있습니다. 번호에 해당하는 비트 하나가 하나의 원소 상태를 의미하고, 비트가 1이면 해당 원소가 집합에 포함되어 있다는 의미이며, 0이면 포함되지 않는다는 의미입니다.

 

연산	예시	예시 설명
원소 추가	A |= (1 << k)	k번 원소를 집합 A에 추가. 왼쪽 시프트 연산으로 k번 비트만 1로 만들고 A와 OR연산을 하여 원소를 추가.
원소 삭제	A &= ~(1 << k)	k번 원소를 집합 A에서 삭제. 왼쪽 시프트 연산으로 k번 비트만 1로 만든후 NOT연산을 함. 그러면 k번 비트만 0으로 되고 나머지 비트는 1이 되므로 A와 AND 연산을 하여 원소를 삭제.
원소 토글	A ^= (1 << k)	k번 원소가 집합 A에 있으면 삭제 없으면 추가. 왼쪽 시프트 연산으로 k번 비트만 1로 만든 후 XOR연산을 함.
원소의 포함 여부 확인	if A & (1 << k):	k번 원소가 집합 A에 있는지 확인. 왼쪽 시프트 연산으로 k번 비트만 1로 만든 후 AND연산을 함.
집합 연산	A | B A & B A & ~B A ^ B	A | B -> 집합 A와 집합 B의 합집합 A & B -> 집합 A와 집합 B의 교집합 A & ~B -> 집합 A에서 집합 B를 뺀 차집합 A ^ B -> A와 B중 하나의 잡합에만 포함된 원소들의 집합
집합의 크기 구하기	def bitCount(n):   if n == 0: return 0   return n%2 + bitCount(n//2)	집합에서 1인 상태인 비트의 수를 셈. 재귀 호출을 하여 모든 비트를 순회함.