[ Algorithm ] BitMask 비트마스크

비트마스크

알고리즘 문제를 풀다보면 비트마스크의 개념을 알고 있으면 도움이 될 때가 있다 !

그렇다면 비트마스크는 무엇일까 ?!

 

컴퓨터의 최소 연산 단위는 bit 이다 내부적으로 모든 자료를 이진수로 표현한다

bit 는 이진수를 나타내기 위해 0과 1로 이루어져 있고

정수의 이진수 표현을 자료구조로 쓰는 기법을 비트 마스크라 한다

---

비트연산자

비트연산자에는 AND, OR, XOR, NOT, SHIFT 가 존재한다

 

AND (&)

# 대응하는 두 비트가 모두 1일 때 1을 반환한다
1010 & 1111 = 1010

OR (|)

# 대응하는 두 비트가 모두 1 또는 하나라도 1인 경우 1을 반환한다
1010 | 1111 = 1111

XOR (^)

# 대응하는 두 비트가 서로 다르면 1을 반환한다
1010^1111 = 0101

NOT (~)

# 비트의 값을 반전하여 반환한다
~1010 = 0101

SHIFT (>>,<<)

# 왼쪽 Shift (<<): 왼쪽으로 비트를 옮긴다. (A * 2^B)
# 오른쪽 Shift (>>): 오른쪽으로 비트를 옮긴다. (A / 2^B)
00001010 << 2 = 101000
00001010 >> 2 = 000010

---

비트마스크 활용

예를 들어 알고리즘에서 방문을 체크하는 리스트가 존재할 때

보통 리스트를 이용하여 아래와 같이 표현한다

vistied = [False]*10

비트마스킹으로 표현하면 아래와 같이 표현하고

각 비트는 하위주소 ( 오른쪽 ) 부터 인덱스를 세면 된다

visited = 0b0000000000

집합의 표현

비트 마스크를 이용하면 집합을 쉽게 표현할 수 있는데

원소를 추가, 삭제하는 등 다양한 연산을 굉장히 빠르게 수행할 수 있다

 

원소의 개수가 N 인 집합이 존재할 때 각 원소에 0부터 n-1 까지 번호를 부여하고

번호에 해당하는 비트가 1이면 원소가 포함, 0이면 불포함으로 집합을 표현할 수 있다

 

원소추가

# p번 원소를 추가 / p번 비트를 1로 바꾸어주면 된다
cur = cur|(1<<P)

원소삭제

# p번 원소를 삭제할 경우 비트를 0으로 바꾸어주면 된다
cur = cur&~(1<<p)

원소토글

# p번 비트가 1이면 0, 0이면 1로 바꾸는 토글 연산
cur = cur^(1<<p)

집합연산(합집합)

a|b # a와 b 의 합집합
a%b # a와 b 의 교집합
a&~b # a 에서 b를 뺀 차집합
a^b # a 와 b 중 하나에만 포함된 원소들의 집합

 

집합의 크기는 아래와 같이 재귀적으로 모든 비트를 순회하면서 

현재 1로 켜져있는 비트의 수를 count 하면 된다

---

장점

• 비트 연산은 삽입, 삭제, 조회가 빠르다
• 코드가 간결해진다
• 빠른 속도 !
• 정수 표현으로 DP 문제를 해결할 수 있다