[알고리즘] 비트마스크(Bit Mask)

비트마스크(Bit Mask)는 알고리즘이라기보다는 기법인데, 한 비트가 0 또는 1의 두 가지 값을 갖는다는 사실을 이용해 2진수 배열을 십진수로 변환하여 사용하는 테크닉이다.

예를 들어 {true, false, true, false}인 배열을 2진수로 1010으로 표현하고, 다시 십진수로 변환하면 10이 된다.

비트마스크 기법을 이용하면 bool 배열간의 연산을 간단하게 할 수 있다.

{true, false, true, false} 배열과 {true, false, false, true} 배열을 각각 & 연산으로 비교할 때, 일반적으로는 반복문을 이용해 배열의 각 인덱스마다 비교해줘야 할 것이다.

그런데 비트마스크 기법을 이용해 {true, false, true, false} 배열을 10으로, {true, false, false, true} 배열을 9로 생각하면, 10 & 9라는 식 한줄로 연산 결과가 8, 즉 {true, false, false, false} 임을 쉽게 알 수 있다.

---

기본 연산 |

 

1. AND(&) 연산

1110(2) & 1011(2) = 1010(2)

2진수의 각 비트를 & 연산으로 비교한다.

비교되는 두 비트가 모두 1이면 출력되는 비트도 1, 아닌 경우에는 0이다.

 

2. OR(|) 연산

1100(2) | 1010(2) = 1110(2)

2진수의 각 비트를 | 연산으로 비교한다.

비교되는 두 비트 중 하나가 1이면 출력되는 비트도 1, 아닌 경우에는 0이다.

 

3. XOR(^) 연산

1100(2) ^ 1010(2) = 0110(2)

2진수의 각 비트를 ^ 연산으로 비교한다.

비교되는 두 비트가 다르면 출력되는 비트도 1, 같으면 0이다.

 

4. NOT(~) 연산

~1010(2) = 0101(2)

2진수의 각 비트를 0이면 1로, 1이면 0으로 반전시킨다.

 

5. SHIFT(<<, >>) 연산

001010(2) << 2 = 101000(2)

001010(2) >> 2 = 000010(2)

비트를 각 방향으로 해당 개수만큼 민다.

---

응용 |

 

위의 기본 연산들을 다음과 같이 이용할 수 있다.

 

1. x의 n번째 비트를 1로 만들기

x |= (1 << n)

 

2. x의 n번째 비트를 0으로 만들기

x &= ~(1 << n)

 

3. x의 n번째 비트를 반전시키기

x ^= (1 << n);

 

4. x의 n번째 비트

(x >> n) & 1

 

익숙해지려면 많은 연습이 필요할 것 같다. 당분간 비트마스크 문제를 집중적으로 풀어야겠다.

---

관련 문제 |

[BOJ] 외판원 순회 (https://www.acmicpc.net/problem/2098)

[BOJ] 발전소 (https://www.acmicpc.net/problem/1102)