[C++] 비트마스크 (bitmask) 의 구현, 다양한 예제

비트마스크란 ?

이진수 표현을 자료구조로 쓰는 기법이다.

비트 연산자

• a & b : AND 연산
• a | b : OR 연산
• a ^ b : XOR 연산
• ~a : NOT 연산
• a << b : 정수 a를 왼쪽으로 b비트 Shift
• a >> b 정수 a를 오른쪽으로 b비트 Shift

비교 연산자 → 비트 연산자의 우선순위

집합의 구현

int noPizza = 0; // 공집합
int fullPizza = (1 << 20) - 1; // 꽉찬 피자

0부터 19까지의 번호를 가진 토핑을 가진 피자집이 있다.

20개의 토핑을 모두 올린 피자는 아래와 같이 표현할 수 있는데, 20개의 0을 가진 비트를 만들고 1을 뺴면 20개의 비트가 모두 켜진 수를 얻을 수 있다.

p번째 있는 토핑을 추가하고 싶으면, 현재 토핑 목록인 toppings에 p비트만 켜진 정수를 비트별 OR 처리하면 된다

toppings |= (1 << p); 

 

원소 포함 여부 확인

if(toppings & (1 << p)) cout << "페퍼로니 있다!" << endl;

위의 연산을 이용해서, toppings에 p가 있는지 확인하려면 & 연산자를 사용하면 된다.

이 if문의 연산 결과는 0 혹은 1<<p이다.

 

 

원소의 삭제

toppings -= (1 << p);

토핑이 없는 경우에 정상적으로 동작하도록 원소를 삭제하기 위해서는

toppings &= ~(1 << p); 

이렇게 하면 페퍼로니가 없는 경우에도 (0) AND 연산자를 적용하게 되어 동일하게 0이 된다.

 

 

원소의 토글

toppings ^= (1 << p); 

페퍼로니가 있으면 (1) XOR 연산을 통해 0이 되고, 없으면 (0) 1이 된다.

 

 

집합의 크기 구하기

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

모든 비트를 순회하면서 켜져 있는 비트의 개수를 세는 프로그램이다.

현재 비트에서 켜져있는 최하위 비트를 구하기 위해 아래 로직을 사용한다.

int firstTopping = (toppings & -toppings); 

음수를 표현할 때 2의 보수를 취하는데, 이 원리를 사용해서 toppings와 -toppings를 AND한 결괏값은 항상 켜져있는 최하위 비트를 도출한다.

 

 

최소 원소 지우기

toppings &= (toppings - 1);

특정 비트값에서 1을 뺀 값과 원래 비트값을 AND 연산하면 최하위에 켜져있는 비트가 꺼진다.

 

 

모든 부분집합 순회하기

for(int subset = pizza; subset; subset = ((subset -1) & pizza) {
    // subset은 pizza의 부분집합
}

(subset -1) & pizza 를 통해 최하위 비트가 꺼진 subset과 pizza가 AND 연산을 수행하여 pizza와 겹쳐지는 부분만 subset에 남게 된다. 이 연산을 반복하면 pizza의 모든 부분집합을 방문할 수 있다.

 

 

비트마스크를 이용한 연산 예제

1. 켜져 있는 비트의 개수 세기 

int countBitsSet(int n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

 

2. 비트의 전체 길이 세기

int countBitsLength(int n) {
    int count = 0;
    while (n) {
        count++;
        n >>= 1;
    }
    return count;
}

 

3. 부분집합 구하기

int getUnion(int a, int b){ // 합집합
	return a | b; 
}

int getIntersection(inta , int b){
	return a & b; 
}

int getDifference(int a, int b){
	reutrn a & (~b); 
}

 

4. 모든 집합을 생성하고 탐색

void generatePermutations(int n) {
    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {
                std::cout << j << " ";
            }
        }
        std::cout << "\n";
    }
}