비트마스킹

비트마스킹

컴퓨터는 내부적으로 모든 자료를 이진수로 표현한다. 이런 특성을 이용해 정수의 이진수표현을 자료구조로 쓰는 기법

비트마스크를 이용하면 더 빠른 수행시간, 더 간결한 코드, 더 적은 메모리 사용이 가능하다.

 

비트 연산자

비트마스킹은 기본적으로 비트를 다뤄야 하므로, 비트 연산자에 대해서 먼저 알아보자.

a & b	a의 모든 비트와 b의 모든 비트를 AND 연산한다. 둘다 1이라면 1, 아니면 0	ex) 100 & 111 = 100
a | b	a의 모든 비트와 b의 모든 비트를 OR 연산한다. 둘다 0이라면 0, 아니면 1	ex) 010 | 111 = 111
a ^ b	a의 모든 비트와 b의 모든 비트를 XOR 연산한다. 둘이 다르다면 1, 아니면 0	ex) 011 ^ 101 = 110
~a	a의 모든 비트에 NOT 연산을 한다. 0이면 1, 1이면 0	ex) a = 011 ~a = 100
a << b	a를 b비트 만큼 왼쪽으로 시프트	ex) a = 001 a << 2 = 100
a >> b	a를 b비트 만큼 오른쪽으로 시프트	ex) a = 100 a >> 2 = 001

 

집합의 표현

비트마스크를 표현하면 집합을 쉽게 표현할 수 있다.

또한, 집합에 원소를 추가, 삭제하는 등 다양한 연산을 빠르게할 수 있다.

 

원소의 개수가 N인 집합이 있다고 하면, 각 원소를 0 ~ (N-1)번까지 번호를 부여하고

번호에 해당하는 비트가 1이면 원소 포함, 0이면 불포함이라고 한다면 비트를 이용해 표현할 수 있다.

 

예를 들어, { A, B, C, D, E, F, G } 집합이 있다고 해보자.

 

총 7개 원소가 존재하니까 우리는 7개의 비트로 집합을 표현할 수 있다. 1011011 이런식으로..

각 원소마다 비트를 하나씩 대응시켜서 원소가 존재하면 1, 아니면 0으로 표현해보자.

{A} 라는 부분집합은 64 - 1000000(2)로 표현하고 { C, F } 는 18 - 0010010(2) 로 표현할 것이다.

 

원소 추가

현재 상태 cur이 있을 때, p번 원소를 추가한다고 해보자.

그렇다면 현재 상태 cur에서 p번 비트를 1로 바꿔줘야한다.

비트연산자 '|' 를 활용하면 쉽게 해결할 수 있다.

cur = cur | (1<<p)

3번째 원소 추가

 

원소 삭제

원소 삭제는 p번 비트를 0으로 바꿔줘야한다.

cur = cur & ~(1 << p)

 

1<<p를 통해서 p번 비트만 1, 나머지는 0으로 만든다.

그 후, ~연산을 통해 p번 비트만 0, 나머지는 1로 만들고 & 연산을 진행하면 p번 비트만 0으로 바뀌고 나머지는 cur과 동일하게 유지한다.

 

 

원소 토글

원소 토글은 p번 비트가 1이면 0, 0이면 1이다.

현재 상태에서 p번 원소가 있다면 삭제하고, 없다면 추가한다.

cur = cur ^ (1<<p)

^ 연산은 다르다면 1 같으면 0으로 연산한다. 비교할 값(1<<idx)은 00100이다.

3번째 원소가 0이었기 때문에 1로 바뀌었다.

 

집합 연산

비트마스킹을 이용하면 합, 교, 차집합 등을 쉽게 구할 수 있다.

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

 

집합의 크기 구하기

집합의 크기를 구하려면, 현재 1로 켜져있는 비트의 수를 count해야한다.

따라서, 모든 비트를 순회해야하고 재귀적으로 다음과 같이 구현할 수 있다.

 

func countBit(_ x: Int) -> Int {
	if x == 0 { return 0 }
    return x % 2 + countBit(x / 2)
}

 

모든 부분집합 순회하기

어떤 집합의 모든 부분집합을 순회하는 과정도 간단하게 구현할 수 있다.

func processSubsets(of set: Int) {
    var subset = set
    while subset != 0 {
        // subset은 set의 부분집합 중 하나.
        
        // 여기에 부분집합 처리 로직을 작성한다.
        
        subset = (subset - 1) & set
    }
}

 

예를 들어 집합원소 A, B, C, D 중 { A, B, D } 를 포함한 집합을 생각해보자.

모든 부분 집합은 공집합을 제외하고 {A}, {B}, {D}, {A, D}, {B, D}, {A, B, D} 가 존재한다.

비트로 표현하면 아래와 같다.

• {A, B, D} : 1101
• {A, B} : 1100
• {A, D} : 1001
• {B, D} : 0101
• {A} : 1000
• {B} : 0100
• {D} : 0001

 

이제 구현한 코드를 따라가보자.

	subset	(subset-1)	(subset-1) & set(1101)
A B D	1101	1100	1100
A B	1100	1011	1001
A D	1001	1000	1000
A	1000	0111	0101
B D	0101	0100	0100
B	0100	0011	0001
D	0001	0000	0000

while 문을 통해 부분집합을 다 순회하는 것을 볼 수 있다.