오늘 알고리즘 문제를 푸는데 집합을 구현해야 하는 문제였다. (문제) 비트 마스크를 이용하면 집합을 쉽게 표현할 수 있다는 건 알았지만 정작 공부해보려고 한 적은 없는데 이번 참에 비트 마스킹에 대해 공부해보았다.
비트 마스크란? 우선, 컴퓨터는 내부적으로 모든 자료를 이진수로 표현한다. 이와 같은 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법을 비트 마스크라 한다.
우선! 비트 연산자
비트 마스킹은 기본적으로 비트를 다루는 기법이기 때문에 비트 연산자를 알고 있으면 좋다. 따라서 우선 비트 연산자를 정리하고 가겠다!
AND, OR, XOR
- AND 연산 (&): 대응하는 두 비트가 모두 1일 때, 1 반환
- OR 연산 (|): 대응하는 두 비트가 하나라도 1일 때, 1 반환
- XOR 연산 (^): 대응하는 두 비트가 서로 다르면, 1 반환
1010 & 1111 = 1010
1010 | 1111 = 1111
1010 ^ 1111 = 0101NOT
- NOT 연산 (~): 비트의 값을 반전하여 반환
~1010 = 0101왼쪽, 오른쪽 Shift
- 왼쪽 Shift (<<): 왼쪽으로 비트를 옮긴다. (A * 2^B) 의미
- 오른쪽 Shift (>>): 오른쪽으로 비트를 옮긴다. (A / 2^B) 의미
00001010 << 2 = 101000
00001010 >> 2 = 000010비트 마스크의 개념
컴퓨터는 내부적으로 bit 단위로 연산을 한다. bit는 모두 익히 알 듯이 0과 1로만 이루어져 있는데 이 특징을 이용해서 다양한 알고리즘 문제에서 간결한 코드와 빠른 속도로 활용이 가능하다.
가령, 10개의 방문을 체크해야 한다면 보통 check = [False] * 10와 같이 리스트를 많이 사용한다. 비트 마스킹은 아래와 같이 표현해서 하위 주소인 오른쪽부터 0인지 1인지 확인하면 된다.
check = 0b0000000000비트 마스크와 집합
비트 마스크는 비트의 특징을 살려 집합 개념의 문제에서 활용이 가능하다. 백준 11723 집합 문제가 비트 마스킹으로 집합을 구현하는 문제인데, 이 문제를 기준으로 설명하겠음!
문제를 보면 알 수 있듯이, x의 범위는 1부터 20이다. 따라서 0번째는 0이라 생각하고, 길이가 21인 비트를 생각하면 된다.
원소 추가
S에 num을 추가한다면, S의 num번 비트만 1을 만들어주면 된다. 이 부분은 아래에서 계속 나올 텐데 (1 << num)은 num번째를 1로 세팅해주는 거라고 생각하면 쉽다.
S |= (1 << num)원소 삭제
S에서 num을 삭제한다면, S의 num번 비트를 0으로 만들어주면 된다. ~(1 << num)는 num번 비트만 0으로 만들고 나머지는 1로 만들어 주는 거다. 이렇게 하고 and 연산을 하면 num을 제외한 나머지 비트는 동일한 상태를 유지할 수 있다.
S &= ~(1 << num)원소 토클
S에 num이 없다면 추가, 있다면 삭제하는 연산이다. xor 연산은 두 비트가 서로 다를 때 1을 반환하므로 토글 개념을 구현할 수 있다.
S ^= (1 << num)원소 체크
S에 num이 있으면 1, 없으면 0을 출력해주는 연산이다. 앞서 언급한 거 처럼, and 연산은 두 비트가 모두 1이어야 1을 반환한다는 성질을 이용해주면 된다.
print(1 if S & (1 << int(op[1])) != 0 else 0))원소 비우기 및 채우기
원소를 비우기 위해선 S의 모든 비트를 0으로 만들어주면 된다. 그리고 채우기 위해선 모든 비트를 1로 만들어준다. (1 << 21)만 하면 1000000000000000000000이다. 그럼 한자릿수 줄이면서 모두 1로 하려면? 1을 빼주면 된다.
S = 0 #비우기
S = (1 << 21) - 1 #채우기비트 마스크와 집합 (추가)
원소를 다루는 것 뿐만 아니라 집합 자체의 연산 등도 비트 마스킹을 이용해서 구현이 가능하다. 내가 예전에 [Python] 순열, 조합 구현하기 라는 글을 올린 적이 있는데 비트 마스킹으로도 순열과 조합을 구현할 수 있다. (이건 나중에 올리겠음)
집합 끼리의 연산
우선, 아래는 집합 끼리의 연산이다. 물론 아래 A와 B는 비트!
A | B # 합집합
A & B # 교집합
A & ~B # 차집합 (A - B)
A ^ B # A와 B 중 하나에만 포함된 원소들의 집합집합의 크기
집합의 크기를 구하기 위해선, 비트에서 1인 비트 수를 세주면 된다. 이는 재귀 함수로 구현할 수 있다. x % 2는 마지막 비트를 의미, x // 2는 마지막 비트의 삭제를 의미한다.
def bitCount(x):
if x == 0: return 0
return x % 2 + bitCount(x//2)레퍼런스
