비트마스크
비트마스크
컴퓨터와 이진수
우리가 사용하는 실제 컴퓨터는 10진수가 아닌 2진수를 사용해 계산을 한다.
그 이유는 바로, 컴퓨터가 전기신호로 작동을 하기 때문인데
컴퓨터에 전기가 통할 때는 1, 통하지 않을때는 0 으로 표기하여 계산하기 때문이다.
또한, 2진수를 이용하는 것이 컴퓨터에겐 훨씬 효율적이고 빠르다.
예를 들어, 컴퓨터가 하나의 신호를 보내는데 10진수를 이용한다고 가정해보자.
컴퓨터가 10진수를 이용해 숫자를 표현하려면 0부터 9까지의 숫자를 표현해야 하기 때문에
전선이 10개가 필요할 것이다. 하나의 신호를 보내는데 9개의 전선이 낭비가 되는 셈이다.
하지만, 2진수를 이용하게 되면 하나의 전선으로도 가능하며,
필요에 따라 이진수를 여러번 사용하여 표현할 수 있기 때문에 훨씬 효율적이라고 할 수 있다.
비트(Bit)
비트는 데이터를 나타내는 최소 단위로써, 이진수인 0 또는 1의 값을 가진다.
여기서 비트(Bit)는 Binary Digit의 약자로써, 비트가 1이면 "켜져 있다", 0이면 "꺼져 있다"고 한다.
비트마스크
위에서 설명한 이진수 표현을 자료구조로 사용하는 기법을 비트마스크 라고 한다.
즉, 컴퓨터는 이진수를 이용해 빠른 연산을 할 수 있기 때문에
모든 수를 이진수 형태로 표현하여 빠른 연산이 가능하게 하는 일종의 테크닉인 셈이다.
비트마스크의 장점
빠른 수행시간
비트마스크의 연산은 이진수 연산이기 때문에 O(1)에 구현되는 것이 많다.
따라서 다른 자료구조를 이용하는 것 보다 훨씬 빠르게 동작한다.
간결한 코드
비트 연산의 특성을 이용하면, 다양한 집합 연산들을 반복문이나 조건문 없이 한 줄에 작성할 수 있기 때문에
짧고 간결한 코드를 작성할 수 있다.
적은 메모리 사용
비트마스크를 이용하면 같은 데이터라도 더 적은 메모리를 이용해 표현할 수 있다.
예를 들어, 비트가 10개인 경우에는 각 비트당 두 가지의 경우를 가지므로 \2^{10} 가지 경우의 수를 10bit 로 표현이 가능하다.
이처럼, 적은 수의 비트로 매우 많은 경우의 수를 표현할 수 있기 때문에 메모리 사용 측면에서 굉장히 효율적이라고 할 수 있으며,
또한 더 많은 데이터를 미리 계산해서 저장해 둘 수 있는 장점이 존재한다.
그래서 DP 알고리즘에 매우 유용하다.
이렇게 적은 메모리를 사용하는 측면이 비트 마스크를 사용하는 가장 큰 이유이다.
비트 연산자
| 연산 | 표기 | 의미 |
|---|---|---|
| AND 연산 | a & b | 두 비트(a, b)가 모두 1인 경우에만 1을 반환, 나머지는 0 반환 |
| OR 연산 | a | b | 두 비트 중 하나라도 1이면 1을 반환. 나머지는 0 반환 |
| XOR 연산 | a ^ b | 두 비트가 서로 다르면 1, 같으면 0을 반환 (둘 중 하나만 1인 경우에만 1을 반환) |
| NOT 연산 | ~a | 1이면 0을, 0이면 1을 반환 ( 반대로 반환 ) |
| Shift 연산 | a << b a >> b | 정수 a를 왼쪽(<<) 또는 오른쪽(>>)으로 b비트 만큼 이동 |
쉬프트 연산 예시
a = 51
| 1 | 1 | 0 | 0 | 1 | 1 |
|---|
a << 1 = 38
| 1 | 0 | 0 | 1 | 1 | 0 |
|---|
이렇게 a << 1 은 비트로 표현된 a(51)을 왼쪽으로 1비트씩 옮긴다.
비트마스크를 이용한 집합 구현
비트마스크는 원소의 유무를 0과 1로 표현함으로써 집합을 표현할 수 있도록 한다.
여기서 하나의 bit는 하나의 원소를 의미한다.
bit가 켜져 있다면 해당 원소가 집합에 포함되었다는 의미이고 꺼져 있으면 포함되어 있지 않다는 의미이다.
예를 들어, 집합 {1, 4, 5, 6, 7, 9} 가 있다고 하자.
이진수를 이용해 0부터 9번째 원소의 존재 유무를 다음과 같이 표현할 수 있을 것이다.
\2^{1} + \2^{4} + \2^{5} + \2^{6} + \2^{7} + \2^{9} = \10 1111 0010_{2} = 754
2진수 부분을 보게되면 1, 4, 5, 6, 7, 9 번째 비트만 켜져있음을 알 수 있다.
이렇게 원소의 자리에 해당하는 비트의 값을 통해 집합을 표현할 수 있다.
그럼 비트마스크를 어떻게 사용하는지 C언어를 통해 알아보자.
공집합
기본적으로 공집합은 bit가 모두 꺼진 상황이기 때문에 상수 0으로 표현한다.
int A = 0;꽉 찬 집합
꽉 찬 집합은 비트가 모두 켜진 상황을 의미한다.
1 << 10을 하게 되면 1을 왼쪽으로 10비트 이동시키므로 \10000000000_{2} 이 되며
여기에 1을 빼게 되면 \1111111111_{2} 이 되므로 10자리가 모두 켜지게 된다.
int A = (1 << 10) -1;원소 추가
원소를 추가한다는 것은, 그 원소에 해당하는 비트를 1로 만드는 것을 같다.
A집합에 p번째 원소를 추가하는 코드는 다음과 같다.
OR 연산으로 표기하며, 이미 A에 해당 원소가 포함되어 있는 경우에는 아무런 변화가 없다.
A |= (1 << p);원소 삭제
A 집합에 포함된 특정 원소를 삭제하는 것을 의미한다.
원소에 해당하는 비트가 꺼져야 하기 때문에 해당 비트를 항상 0으로 만드는 연산이 필요하다.
그렇다면, 다음과 같은 코드를 생각해볼 수 있다.
A -= (1 << p);하지만, 이는 해당 비트가 원래 0일 경우에 문제가 발생한다.
그러므로, p번째 원소의 포함 여부와 상관없이 해당 비트를 끄기 위해서는 AND 연산을 이용해야 한다.
1<<p는 p번째 bit만 켜진 상황이며, 여기에 NOT을 하면 p번째 bit만 꺼진 상황이 된다.
이 때, AND 연산을 하게 되면, p번째 비트만 0이 되고 나머지 비트는 변함이 없게 된다.
A &= ~(1 << p);원소의 포함 여부 확인
A 집합에 특정 원소가 포함되어 있는지 확인하는 방법이다.
p번째 원소가 포함되었는지 확인하고 싶다면, p번째 비트가 켜져 있는지만 확인하면 될 것이다.
if (A & (1 << p)) printf("Yes");원소의 토글
A 집합에 해당 원소가 빠져 있는 경우에는 추가하고, 들어 있는 경우에는 삭제하는 방법이다.
이는 XOR 연산을 이용하면 된다.
A ^= (1 << p);두 집합에 대한 연산
int added = (a | b); // a와 b의 합집합
int intersection = (a & b); // a와 b의 교집합
int removed = (a & ~b); // a에서 b를 뺀 차집합
int toggled = (a ^ b); // a와 b중 하나에만 포함된 원소들의 집합최소 원소 찾기
켜져있는 비트 중 가장 오른쪽에 있는 비트를 찾는 방법으로,
집합에 포함된 가장 작은 원소(Index가 가장 작은 원소)를 찾는 것이다.
이 방법은 비트마스크 뿐만 아니라, 펜윅트리(Fenwic Tree)에서도 사용되는 기법이다.
컴퓨터는 음수를 표현할 때, 2의 보수를 이용하기 때문에 -A는 ~A + 1을 이용하게 된다.
이를 이용하여 최소 원소를 찾을 수 있다.
A에서 가장 오른쪽에 켜진 비트의 인덱스를 p라고 할 때, p보다 오른쪽에 있는 모든 비트는 0이 된다.
따라서, NOT 연산을 적용한 ~A의 p번째 비트는 0이고, 오른쪽의 모든 비트는 1이 된다.
여기에 +1을 하게 되면, p번째보다 오른쪽에 있는 비트들은 0이 되며, p번째 비트는 1이 된다.
그리고 p번째 비트보다 왼쪽에 있는 비트들은 아무런 변화가 없다.
그래서, -A와 A를 AND시키면 p번째 비트만 켜진 상태로 남게 된다.
int first = (A & ~A);최소 원소 지우기
가장 오른쪽에 켜져있는 비트를 지우고 싶다면, A와 A-1을 AND 연산하면 된다.
왜냐하면, A에서 1을 빼주게 되면 가장 오른쪽에 있던 비트는 0이 되고 그보다 오른쪽에 있는 모든 비트들이 1이 되기 때문이다.
A &= (A - 1)집합의 크기 구하기
int countBit(int x) {
if(x == 0) return 0;
return x%2 + countBit(x/2);
}
추가로 학습하면 좋을 자료
- 비트마스크를 이용한 DP(다이나믹 프로그래밍)
- 비트마스크를 이용해 공간복잡도 줄이기
- 외판원 순회 문제
참고 블로그
기여자
HongEunho
📦