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

비트 마스크

비트 마스크는 비트 연산을 사용하여 데이터를 효율적으로 처리하는 기법이다. 특정 비트 패턴을 사용해 데이터를 조작하거나 필터링할 수 있기 때문에 메모리 사용량을 줄이고 계산 속도를 높일 수 있다.

비트 연산

비트 단위로 연산을 수행한다. AND(’&’) OR(’|’) XOR(’^’) NOT(’~’) 등이 있다. 이진수 단위로 연산을 수행해야 하기 때문에 unsigned 키워드를 사용하곤 한다.

사용법

int a = 9;  //1001
int b = 10; //1010
int cal;

cal = a & b;  // 1000 = 8   | 둘 다 1이면 1
cal = a | b;  // 1011 = 11  | 둘 중 하나라도 1이면 1
cal = a ^ b;  // 0011 = 3   | 둘이 다르면 1
cal = a << 1; // 10010 = 10 | 옆으로 1자리 shift, 앞은 소멸
cal = ~a;     // 0110 = 6   | 비트를 반전시킴

실습

// 값이 중복되는지 확인
vector<int> v = {5, 5, 5, 5};

// 0이면 같고 0이 아니면 다름으로 분별
int a = v[0]^v[1];           // 1001 ^ 1001 = 0000 = 0 
int b = v[0]^v[1]^v[2];      // 0000 ^ 1001 = 1001 = 5
int c = v[0]^v[1]^v[2]^v[3]; // 0000 ^ 0000 = 0000 = 0

// 홀짝 판별
int n = 7; 
string a = (n & 1) ? "홀":"짝"; // 111 & 001 = 001
cout << s; // 홀

// 플래그 설정
const int aBuff = 1 << 0; // 0001
const int bBuff = 1 << 1; // 0010
int status = 0;           // 0000

// 플래그 넣기
status |= aBuff;  // 0000|0001 = 0001
status |= bBuff;  // 0001|0010 = 0011

//플래그 빼기
status &= ~aBuff; // 0011&1110 = 0010