[Algorithm] 비트마스크 (BitMask) 알고리즘에 대해서 공부하자.

비트마스크 (BitMask) 란

컴퓨터는 내부적으로 모든 자료를 이진수로 표현한다.

이와 같은 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법을 비트 마스크라고 한다.

비트(bit) 용어 그대로 비트와 관련된 내용이라고 생각하면 편하다.

비트는 0, 1값을 갖고 이를 false/true 또는 off/on 라는 상태를 나타내기도 한다.

이를 흔히 말하는 이진법을 사용하는 것을 의미한다.

 

비트마스크의 장점

1. 수행 시간이 빠르다. 

비트마스크 연산은 bit 연산이기 때문에 O(1)에 구현되는 것이 많다. 따라서 다른 자료구조를 이용하는 것보다 훨씬 빠르게 동작하게 된다. 

다만, 비트마스크를 이용하는 경우에는 비트의 개수만큼 원소를 다룰 수 있기 때문에 연산 횟수가 적은 경우에는 속도에 큰 차이가 없지만, 연산 횟수가 늘어날수록 차이가 매우 커지게 된다. 

 

2. 코드가 짧다.

다양한 집합 연산들을 비트연산자로 한 줄로 작성할 수 있기 때문에 반복문, 조건문 등을 이용한 코드보다 훨씬 간결한 코드를 작성할 수 있다.

 

3. 메모리 사용량이 더 적다.

비트마스크를 이용하는 가장 큰 이유라고 생각한다.

하나의 정수로 매우 많은 경우의 수를 표현할 수 있기 때문에 메모리 측면에서 효율적이며, 예를 들어, bit가 10개인 경우에는 각 bit당 두 가지 경우를 가지기 때문에 210210가지의 경우를 10bit 이진수 하나로 표현이 가능하다. 더 많은 데이터를 미리 계산해서 저장해 둘 수 있는 장점이 있다. (DP에 매우 유용하다) (백준알고리즘에는 DP와 관련된 문제가 정말 많다.)

 

비트 연산자

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

 

주의할 점

1. C에서 비트 연산들의 우선순위는 비교 연산자보다 낮다. 따라서 비트 연산들 이용할 때에는 항상 연산자보다 괄호를 씌워주는 것이 바람직하다.

 

2. 오버플로우(overflow) 문제이다. 2 ^ 50을 구하기 위해서는 1 << 50 으로 표현한다면 C에는 1은 32bit 취급을 하기 때문에 50번 왼쪽으로 이동하기때문에 overflow문제가 발생하기때문에 1LL로 표현한다.

 

집합의 표현과 활용

길이가 5인 집합 { 0, 1, 2, 3, 4 }가 있다고 가정하자.

여기서 몇가지 요소를 뽑아 어떤 요소를 선택했는 지를 표현할 수 있다.

 

{ 0, 1, 2, 3, 4 } => 11111
{ 1, 2, 3, 4 } => 11110
{ 1, 2, 4 } => 10110
{ 2, 4 } => 10100
{ 1 } => 00010

 

이런식으로 말이다.

 

자 그렇다면 이러한 집합의 삽입, 삭제, 조회 등등의 다양한 연산을 해보자.

 

1. 공집합과 꽉 찬 집합 구하기

기본적으로 공집합은 bit가 모두 0인 상태이다. 반대로 꽉 찬 집합은 bit가 모두 1인 상태이다.

예를들어 1111111111(2)의 값일 경우 이는 A = (1<<10) - 1 과 동일하다. 그리고 0000000000(2) A = 0 이다.

1 << 10 은 10000000000(2) 이므로 1을 빼면 10개의 bit가 모두 켜진 수를 얻을 수 있다.

 

2. 원소 추가

A이라는 집합에서 특정 원소를 추가하는 방법이다. 원소에 해당하는 bit만 켜야 하기 때문에 해당 bit를 항상 1로 만드는 연산이 필요하다. 따라서 OR 연산을 이용한다.

이미 A에 원소가 포함되어 있는 경우에는 아무런 변화가 없게 된다. 

A |= (1 << k);

 

3. 원소 삭제

A 집합에 포함된 특정 원소를 삭제하는 방법이다. 원소에 해당하는 bit가 꺼져야 하기 때문에 해당 bit를 항상 0으로 만드는 연산이 필요하다.

따라서 A -= (1<<k); 로 작성하면 된다. 하지만 이 경우는 A에 반드시 k번째 원소가 포함되어 있는 경우에만 가능하다. 만약 포함되어 있지 않은 경우에는 다른 원소의 포함 여부까지 바꿔버리기 때문이다.

그러므로 A에 k번째 원소의 포함 여부와 상관없이 해당 bit를 끄기 위해서는 AND연산을 이용해야 한다. 

A &= ~(1 << k);

 

4. 원소 포함 여부 확인

A 집합에 특정 원소가 포함되어 있는지 확인하는 방법이다. k번째 원소가 포함되어 있는지 확인하고 싶다면, k번째 bit가 켜져 있는지만 확인하면 된다.

if(A & (1 << k))

 

5. 원소의 토글

A 집합에 해당 원소가 빠져있는 경우에는 추가하고, 들어있는 경우에는 삭제하는 방법이다. XOR 연산을 이용한다.

A ^= (1 << k);

 

6. 두 집합에 대해 연산하기

두 집합을 A와 B라고 한다면 비트연산자들을 통해서 A와 B의 교집합, 합집합, 차집합 등을 구할 수 있다.

A | B       → A와 B의 합집합
A & B     → A와 B의 교집합
A & (~B) → A에서 B를 뺀 차집합
A ^ B     → A와 B중 하나에만 포함된 원소들의 집합 

 

7. 집합의 크기 구하기

집합에 포함된 원소의 크기를 구한다면 A에서 켜진 bit의 수를 구하면 될 것이다. 직접 모든 비트를 확인하면서 개수를 체크할 수도 있고, 내장 명령어를 이용할 수도 있다.

Java → Integer.bitCount(A)

 

8. 최소 원소 찾기

집합에 포함된 가장 작은 원소 (index가 가장 작은 원소)를 찾는 방법이다. 켜져 있는 bit 중에서 가장 오른쪽에 있는 bit를 찾는 것이다. 비트마스크 뿐만 아니라 펜윅 트리 (Fenwick Tree)에서도 사용되는 기법이다.

컴퓨터는 2의 보수를 이용하여 음수를 표현하기 때문에 -A를 표현하기 위해서 ~A + 1을 이용한다.

A에서 가장 오른쪽에 켜진 bit의 인덱스를 k라고 한다면, k보다 오른쪽에 있는 모든 bit는 0이다.

따라서 NOT 연산을 적용한 ~A는 k번째 bit는 0이고, 오른쪽의 모든 bit는 1이 된다.

여기서 ~A에 1을 더해주게 되면 k번째보다 오른쪽에 있는 bit는 모두 0이 되고, k번째 bit는 1이 된다. k번째 bit보다 왼쪽에 있는 bit는 아무런 변화가 없다.

따라서 -A와 A를 AND 시키면 k번째 bit만 켜진 상태로 남게 된다.

int indexFirst = A & (-A);

 

9. 최소 원소 지우기

가장 오른쪽에 켜져 있는 bit를 지우고 싶다면 A-1과 AND시키면 된다. A에서 1을 빼주게 되면 가장 오른쪽에 있던 bit는 0이 되고 그보다 오른쪽에 있는 모든 bit들이 1이 되기 때문이다.

A &= (A - 1);

 

10. 모든 부분 집합 순회하기

A의 모든 부분 집합을 탐색하는 방법이다. 

for (int subset = A ; subset ; subset = ((subset - 1) & A)){ }

 

참고

https://rebro.kr/63

비트마스크 (BitMask) 알고리즘

https://travelbeeee.tistory.com/451

[알고리즘] 비트마스킹(bitmasking) 이란

https://jooncco.com/algorithms/bitmask/

[Algorithms] 비트 마스크 (Bitmask)

https://gyoogle.dev/blog/algorithm/BitMask.html

비트마스크(BitMask) | 👨🏻‍💻 Tech Interview

https://mygumi.tistory.com/361

비트마스크(BitMask) 는 무엇인가? :: 마이구미