비트마스크란 무엇인가?
용어 그대로 비트(bit)에 관한 것이다.
알고리즘보다 테크닉 중 하나로써, 정수의 이진수 표현을 활용한 기법이다.
비트마스크를 사용한 코드의 장점
- 더 빠른 수행시간
- 더 간결한 코드
- 더 작은 메모리 사용량
- 연관 배열을 배열로 대체 : map<vector<bool>\, int> 를 비트마스크를 써서 int[]로 나타낼 수 있다. 큰 시간과 메모리 차이를 불러온다.
- C++에서 N비트 정수를 N비트 이상 왼쪽으로 시프트하면 0이 아니라 오류가 난다.
비트는 이진 숫자(binary digit)를 뜻하는 말로 컴퓨터에서 사용되는 데이터의 최소 단위이다.
비트는 0,1 의 값을 가질 수 있고, true/false 또는 on/off 라는 상태를 나타낸다.
이건 흔히 알고 있는 지식으로 컴퓨터 0,1 두가지 숫자만으로 표현하는 이진법을 의미한다.
여기까지 비트를 통해 알 수 있는 2가지 정보는 다음과 같다.
- 이진수는 0,1 만을 가지고 true/false 상태를 가진다.
- 이진수는 십진수로 표현 가능하다.
그렇다면 이를 어떻게 활용할 수 있을까?
우리는 길이가 5인 집합 {0,1,2,3,4} 가 존재한다고 가정해본다.
여기서 몇가지 요소를 뽑아 어떤 요소를 선택했는 지 표현할 수 있다.
즉, 집합의 어떤 요소를 구성하고 있는지 나타내는 부분집합을 어떻게 표현할 수 있는가?
{1,2,3,4}, {1,2,4}, {2,4}, {1}...
위와 같은 형태로, integer 형으로 인덱스를 활용할 수 있다면, 단순히 boolean 배열을 통해 구현할 수도 있다.
int[] arr1 = [1, 1, 1, 1, 0];
int[] arr2 = [1, 1, 0, 1, 0];
int[] arr3 = [1. 0. 1. 0. 0];
하지만 이건 많은 메모리를 차지하고 오버헤드가 증가한다.
비트마스크를 통해 효율적이게 할 수 있다.
{0,1,2,3,4} => 11111
{1,2,3,4} => 11110
{1,2,4} => 10110
{2,4} => 10100
{1} => 00010
각 요소는 인덱스처럼 표현할 수 있다
즉, 집합 i번째 요소가 부분집합에 존재한다면 1을 의미하고, 그렇지 않으면 0을 의미한다.
그리고 위에서 언급했었던, 2진수를 10진수로 표현할 수도 있다.
{0,1,2,3,4} => 11111 => (2^4*1)+(2^3*1)+(2^2*1)+(2^1*1)+(2^0*1)=31
{1,2,3,4} => 11110 => (2^4*1)+(2^3*1)+(2^2*1)+(2^1*1)=30
{1,2,4} => 10110 => (2^4*1)+(2^2*1)+(2^1*1)=22
{2,4} => 10100 => (2^4*1)+(2^2*1)=20
{1} => 00010 => (2^1*1)=2
부분집합을 배열이 아닌 정수를 통해 나타낼 수 있게 된다.
즉, 20이란 정수는 부분집합 {2,4}를 나타내는 것을 의미한다.
{2,4} 부분집합에서 i를 추가하고 싶으면, 단순히 i번째 비트의 값을 1로 변경해 주면 된다.
이러한 삽입, 삭제, 조회와 같은 행위는 비트 연산을 통해 쉽게 제어할 수 있다.
제어를 위해 비트 연산에 대해 간략히 설명한다.
AND, OR, XOR, NOT, SHIFT가 존재한다.
AND연산(&)
대응하는 두 비트가 모두 1일때 1을 반환
1010&1111 = 1010
OR 연산(|)
대응하는 두 비트가 모두 1 또는 하나라도 1 일떄, 1을 반환
1010|1111 = 1111
XOR 연산(^)
대응하는 두 비트가 서로 다르면 1을 반환
1010|1111 = 0101
NOT 연산(~)
비트의 값을 반전하여 반환
~1010 = 0101
시프트(shift) 연산(>>,<<)
왼쪽 또는 오른쪽으로 비트를 옮긴다.
00001010 << 2 = 101000
00001010 >> 2 = 000010왼쪽 시프트는 * 2, 오른쪽 쉬프트는 /2 를 의미한다.
(A+B)/2를 (A+B)>>2로 사용할 수도 있듯이 많은 곳에서 일반적인 사칙연산을 더 효율적으로 할 수 있다.
이제 어떻게 비트 연산을 통해 삽입, 삭제, 조회를 할 수 있는가?
1010로 표현하고 있을 때, i번째 비트의 값을 1로 어떻게 변경할 수 있을까?
i=2라고 가정할 때, 결과는 1110을 원한다
2번째 비트를 1로 변경할 수 있는 방법은 다음과 같다.
1010 | 1 << 2
1010 | 0100 => 1110
시프트 연산을 통해 2번째 비트만 1로 할당되어 있는 이진수를 만든다.
그리고 or 연산을 통해 원하는 결과를 만들 수 있다.
반대로 2번째 비트의 값을 0으로 어떻게 변경할 수 있을까?
1110 & ~1 << 2
1110 & 1011 => 1010
그리고 i번째 비트의 값을 알 수 있는 방법은 다음과 같다.
A & (1<<i)
2번째 비트 - 1010 & (1 << 2) = 1010 & 0100 => 0
3번째 비트 - 1010 & (1 << 3) = 1010 & 1000 =? 1000
AND 연산과 시프트 연산을 통해 i번째 비트의 값이 0이라면 값이 0이라는 것을 알 수 있다.
이렇게 비트를 활용한 테크닉을 통해 접근하는 것이 비트마스크 인 것이다.
[백준 12813번]
#include <iostream>
#include <cstdio>
using namespace std;
#define LENGTH 10
int A[LENGTH];
int B[LENGTH];
int C[LENGTH];
int main() {
for (int i = 0; i < LENGTH; i++) {
scanf("%1d", &A[i]);
}
for (int i = 0; i < LENGTH; i++) {
scanf("%1d", &B[i]);
}
//and
for (int i = 0; i < LENGTH; i++) {
if (A[i] == 1 && B[i] == 1) {
C[i] = 1;
}
else
C[i] = 0;
printf("%d", C[i]);
}
printf("\n");
//or
for (int i = 0; i < LENGTH; i++) {
if (A[i] == 1 || B[i] == 1) {
C[i] = 1;
}
else
C[i] = 0;
printf("%d", C[i]);
}
printf("\n");
//xor
for (int i = 0; i < LENGTH; i++) {
if (A[i] != B[i]) {
C[i] = 1;
}
else
C[i] = 0;
printf("%d", C[i]);
}
printf("\n");
// ~a
for (int i = 0; i < LENGTH; i++) {
if (A[i] == 1) {
C[i] = 0;
}
else
C[i] = 1;
printf("%d", C[i]);
}
printf("\n");
//~b
for (int i = 0; i < LENGTH; i++) {
if (B[i] == 1) {
C[i] = 0;
}
else
C[i] = 1;
printf("%d", C[i]);
}
printf("\n");
return 0;
}
