BitMask

정수의 각 비트를 활용하여 알고리즘 문제를 해결하는 방법을 알아보겠습니다.

배열처럼 사용하기

32비트 정수형인 int를 사용하여 32개의 bool값을 저장할 수 있습니다.
정확히는 unsigned int 형을 사용해야 32개의 비트를 모두 사용할 수 있습니다.
만약 signed int 형을 사용한다면 signed-bit 하나를 제외한 31개까지만 사용해야 합니다.
이렇게 정수하나를 배열처럼 사용하게되면 메모리를 매우 효율적으로 사용할 수 있습니다.

비트 연산에는 AND연산, OR연산, XOR연산, SHIFT연산이 주로 사용됩니다.
AND연산자, OR연산자, XOR연산자는 각각 &, |, ^ 에 대응되고, 쉬프트 연산자에는 << 와 >> 가 있습니다.

값 저장

unsigned int arr;
arr |= 1 << k; //k 번째 항목 1저장
arr &= ~(1 << m); //m 번째 항목 0저장

값 확인

arr >> k & 1; //k 번째 항목의 값

값 토글

arr ^= 1 << k; //k 번째 항목 값 토글

활용

완전탐색 문제에서 활용되기도 합니다.
1인 경우 선택하고 0인 경우 비선택한다면, 0부터 해당비트수가 전부 1이 될때까지 탐색하여 해결할 수 있습니다.
아래 문제는 다양한 방법으로 해결이 가능하지만, 이러한 개념을 응용하여 더 쉽게 풀 수 있습니다.
백준 16938 - 캠프 준비

더 많이 저장하기

unsigned long long 자료형을 사용하면 한번에 64개의 값을 저장할 수 있습니다.
혹은 정수를 배열로 묶어서 사용하는 방법도 있습니다.

unsigned int arr[10] = {0}; //32개씩 10개를 묶어서 320개 항목 저장가능
arr[k >> 5] |= 1 << (k & 31); //k 번째 항목에 1 저장
arr[k >> 5] &= ~(1 << (k & 31)); //k 번째 항목에 0 저장
arr[k >> 5] >> (k & 31) & 1; //k 번째 항목의 값
arr[k >> 5] ^= 1 << (k & 31); //k 번째 항목 값 토글

연산 최적화

비트연산은 매우 빠르기 때문에 적절하게 사용해주면 연산속도를 개선할 수 있습니다.

홀짝 판별

if(num & 1) {
    // odd
}
else {
    // even
}

2의 거듭제곱으로 나누기

int divByTwo = num >> 1;
int divByFour = num >> 2;
int divByEight = num >> 3;

2의 거듭제곱의 나머지 계산

int remByTwo = num & ((1 << 1) - 1);
int remByFour = num & ((1 << 2) - 1);
int remByEight = num & ((1 << 3) - 1);

'올림' 을 기준으로 2로 나누기

int ceiled = (num >> 1) + (num & 1);