Python 문법 & 비트마스킹

비트마스킹(Bitmasking)이란, 컴퓨터 과학에서 비트 연산을 사용하여 특정 비트의 상태를 확인하거나, 변경하는 기법을 말한다.

백준 알고리즘 문제를 풀다가, 다른 사람의 비트마스킹 문제풀이가 멋지다 느껴 공부하게 되었다.

 

비트마스킹의 장점

• - bit 연산이기 때문에, 시간 복잡도에서 유리. (일반적으로 O(1)로 동작)
• - 다른 자료구조(배열 | 문자열)보다 메모리 사용량이 적음.

 

비트 연산자 종류

&	AND 연산. 비교하는 비트가 둘 다 참일 때 만족한다.	a = 6(110), b = 5(101) 일 때, a & b == 4(100)
|	OR 연산. 비교하는 비트가 둘 중 하나라도 참이면 만족한다.	a = 6(110), b = 5(101) 일 때, a | b == 7(111)
^	XOR 연산. 비교하는 비트가 둘 중 하나만 참일 때만 만족한다.	a = 6(110), b = 5(101) 일 때, a | b == 3(011)
~	NOT 연산. 보수 연산으로 비트를 반전시킨다.
<< n	좌측 이동 연산. 비트를 n 만큼 좌측으로 이동시킨다.	a = 6(110) 일 때, a = a << 2 = 24(11000) a = a << 2 는 a <<= 2 로 축약해서 사용이 가능하다.
>> n	우측 이동 연산. 비트를 n만큼 우측으로 이동시킨다.	a = 6(110) 일 때, a = a >> 2 = 1(1) a = a >> 2 는 a >>= 2 로 축약해서 사용이 가능하다. 이때, 기존 좌측에 있던 n개의 비트는 사라진다.

 

비트 마스킹을 활용한 집합 표현

밑에 들 예시는 단축한 식으로 표현한다.

한 가지를 먼저 설명하면, (1 << n)이란 식은 우측에서부터 n + 1번째 비트에 1이 채워진 수라고 이해하면 좋다. (첫 번째는 0)

예를 들어, (1 << 4) 이라는 식은 2진수 1000 & 십진수 4와 같다.

 

더 나아가 집합 A에 원소를 추가하는 식은 A |= (1 << n) 이라고 쓸 수 있는데, 이는  A = A | (1 << n) 을 의미한다.

즉, | 연산자는 비교하는 비트가 둘 중 하나라도 참이면 만족하는 값을 반환하기에 위와 같은 식이 만들어질 수 있는 것이다.

만약 집합 A가 16(10000)이고, 오른쪽에서 2번째 위치에 1을 추가하고 싶다면,

A = 16(10000) | (1 << 1)(10) ==> 18(10010) 이라는 값을 얻을 수 있다는 의미.

원소 추가	A |= (1 << n)	집합 A의 n번째 원소를 추가
원소 삭제	A &= ~(1 << n)	집합 A의 n번째 원소를 삭제 (보수로 변환하여 구함)
원소 토글링	A ^= (1<< n)	집합 A의 n번째 원소가 1이면 0, 0이면 1로 변환