비트 연산자
비트 마스크를 알아보기 전에 비트 연산자 먼저 훑고 가보자.
- & (AND)
- 비교하는 비트가 둘 다 참일 때 만족
- 0011 & 0110 = 0010
- | (OR)
- 비교 하는 비트 둘 중 하나라도 참이면 만족
- 0011 | 0110 = 0111
- ^ (XOR)
- 비교 하는 비트가 서로 달라야 만족
- 0011 ^ 0110 = 0101
- ~ (NOT)
- 보수 연산 0->1, 1->0
- a가 0011일 때, ~a는 1100
<<(왼쪽 shift)
- 특정 값 n만큼 왼쪽으로 비트 이동
- a가 0011일 때, a << 2는 1100
- 2^n를 곱한만큼 값이 증가
>>(오른쪽 shift)
- 특정 값 n만큼 오른쪽으로 비트 이동
- a가 0110일 때, a << 1는 0011
- 2^n을 나눈만큼 값이 감소
비트 마스크
비트(bit)는 익히 알듯이 0과 1로만 이루어져 있는데, 이러한 특징을 이용해서 다양한 알고리즘 문제에서 빠르고 간결하게 코드를 작성할 수 있다.
예시로 우리가 10개의 방문을 체크할 때 보통 visited = [0] * (n+1) 과 같은 리스트를 많이 이용한다. 한편, 비트 마스킹은 아래와 같이 표현해서 하위 주소인 오른쪽부터 저장된 0과 1을 통해 방문여부를 체크할 수 있다.
check = 0b000110000
방문 여부를 확인할 때 말고도 특정 원소의 존재 여부를 확인할 때에도 집합 자료구조로써 활용할 수 있다.
cf. 파이썬에서 2진수를 직접 입력할 때에는 맨 앞에 0b를 붙여 표현한다(binary의 b를 의미). 또한 10진수를 2진수로 변환하고자 할 때는 bin(정수)를 사용한다.
비트 마스크를 통한 집합 (원소)
python에서 집합은 set()을 통해 쉽게 사용 가능하지만, 비트마스크를 이용할 수도 있다. 원소의 개수가 n인 집합이 있다고 했을 때, 각 원소에 대하여 0에서 n-1까지의 번호를 부여 하여 부분집합을 나타낼 수 있다. 번호에 해당하는 비트 하나하나가 원소의 존재 여부를 의미한다. 비트가 1이면 해당 원소가 집합에 포함되어 있다는 것이고, 0이면 포함되지 않았다는 것이다.
원소 추가
앞으로 집합은 S, 특정 원소의 값은 num이라고 하겠다.
S에 num을 추가한다는 것은 S의 num번 비트에 1을 채운다는 의미이다. shift 연산을 통해 비트 1을 num만큼 왼쪽으로 이동시키고, 이를 S와 or 연산해주면 S의 num번 비트에 1이 채워진다.
S |= (1<<num)
원소 삭제
S에서 num을 삭제한다는 것은 S의 num번 비트에 0을 채운다는 의미이다. shift 연산을 통해 비트 1을 num만큼 왼쪽으로 이동시키고 not 연산을 진행한다. 그러면 모든 비트가 반전되기 때문에 num번 비트는 0, num번 비트를 제외한 모든 비트가 1이 된다. 이를 S와 and 연산해주면 S의 num번 비트만 0이 된다.
S &= ~(1<<num)
원소 토글
S에 num이 없다면 추가, 있다면 삭제하는 연산이다. 비교하는 비트가 서로 다를 때 1을 반환하는 연산인 xor을 활용하면 쉽게 구현 가능하다. shift 연산을 통해 비트 1을 num만큼 왼쪽으로 이동시키고, 이를 S와 ^연산을 해주면 된다.
S ^= (1<<num)
원소 조회
S에 num의 존재 여부를 확인해 있다면 1, 없다면 0을 출력해준다. 이는 두 비트가 모두 1이여야 1을 반환하는 and 연산을 활용하면 된다. shift 연산을 통해 비트 1을 num만큼 왼쪽으로 이동시킨 뒤, 이를 S와 and 연산을 통해 값이 존재한다면 1을, 존재하지 않다면 0을 반환한다.
print(1 if S & (1<<num) != 0 else 0)
원소 비우기 & 채우기
S의 모든 원소를 비우는 것은 단순히 0으로 초기화하여 모든 비트를 0으로 만들어주면 된다. S의 모든 원소를 채울 땐 모든 비트를 1로 만들어 주어야하는데, 이는 shift 연산을 통해 비트 1을 집합의 크기 + 1 만큼 왼쪽 이동시킨 뒤 1을 빼준다. 이렇게 되면 비트의 자릿수가 하나 줄게 되면서 집합의 크기만큼 공간이 생기고, 그 공간들엔 모두 비트 1로 채워질 것이다. (1000000-1=111111)
S=0
S=(1<<S의 집합크기+1) -1
비트 마스크를 통한 집합 (집합)
원소 뿐만 아니라 집합 자체의 연산도 비트마스킹을 이용해서 구현이 가능하다.
집합끼리의 연산
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)
print(bitCount(0b01110101011)) #답은 7!비트마스크 기법을 사용하면
- 수행 시간이 빠르다.
- 메모리 사용량이 적다.
비트마스크 연산은 bit 연산이기에 O(1)의 시간 복잡도를 가지며, 종종 문제를 풀다 보면 비트마스킹을 사용하지 않으면 시간 내에 풀지 못하는 문제들이 존재한다. 그러니 비트마스킹과 관련된 다양한 연산 기법들을 잘 알아두자 !
