[Algorithm] 비트마스크

비트마스크는 정수의 이진수 표현을 자료 구조로 쓰는 기법입니다. 비트마스크를 사용하는 코드는 다음과 같은 장점이 있죠.

1. 더 빠른 수행 시간 : 보통 O(1)에 실행됨

2. 더 간결한 코드 : 복잡한 코드를 한 줄에 작성 가능

3. 더 적은 메모리 사용량 : 예시로, 32개의 아이템의 유무를 나타내는 배열을 32bit 자료형으로 대체 가능  

4. 연관 배열을 배열로 대체 : c++ 경우, map<vector<bool>, int>를 사용한다고 하면 이를 단순 int[] 배열로 대체 가능 

만일 비트마스크로 코드를 작성 시, c++이나 java같은 자료형의 데이터 범위가 정해져 있는 언어에서는 오버플로우나 언더플로우에 주의해야합니다.

bool is_bit_set(unsigned long long a, int b){
    return ( a & ( 1<< b) ) > 0;
}

 

a를 이루고 있는 64bit 셋의 b번째 bit가 켜져있는 지 꺼져있는 지 확인하는 함수입니다. 하지만 여기서 주의할 것은 기본적으로 c++에서는 1은 부호있는 32bit 상수로 취급하기 때문에 위의 경우처럼 작성 할 때, b>=32 이상일 시 오버플로우가 일어나게 됩니다. 이 때는 1에다가 64bit라는 표현으로 1ULL이라든 지 (long long)을 붙여야 합니다. 그리고 자잘한 버그를 피하고 싶다면 unsigned형을 쓰시는 것이 좋습니다.

다음은 비트마스크로 할 수 있는 연산들을 모아 봤습니다.

공집합

0으로 표현

n개의 꽉 찬 집합

int set = (1 << n) - 1;

원소 추가

set |= (1 << n);

 원소 포함 여부

return set & (1 << n);

원소의 삭제

set &= ~(1<<n);

원소의 토글

set ^= (1<<n)

두 집합의 연산

int added = (a | b);
int intersection = ( a & b);
int removed = (a & ~b);
int toggled = (a ^ b);

집합의 크기

int bit_count(int set){
    if( set == 0) return 0;
    return x % 2 + bit_count( set / 2 );
}

 빌트인 함수로도 찾을 수 있습니다. 

gcc/g++ -> __builtin_popcount(set) 

Visual C++ -> __popcnt(set)

최소 원소 찾기

빌트인 함수로 찾을 수 있습니다. 

gcc/g++ -> __builtin_ctz(set) 

Visual C++ -> _BitScanForward(&index, set)

최하위 비트

int first_pop = (set & -set);

최소 원소 지우기

set &= (set -1);

모든 집합 순회

for(int subset = set; subset; subset = (subset - 1) & set) ){
    //code
}

크기가 N인 집합의 모든 부분 집합을 순회하고 싶다면

pre class="brush:cpp;">for(int subset = 0; subset < (1 << n); subset++ ){ //code }

참고 :  알고리즘 문제해결 전략 2권