[Algorithm] C++ Bitmask란?

Bitmask란 비트위에 마스크를 씌우는 방식을 통해서

어떤 위치에 집합의 원소가 존재하는지 아닌지, 추가하는 등의 행위를 말합니다.

주로 이를 마스크와 같다고 하여, 비트마스크라고 말합니다.

 간단한 예시를 들자면, 네가지 원소를 가질 수 있는 집합이 있습니다.

우리는 이를 {1,2,3,4}로 나타낼 수 있습니다.

 이 집합을 보다 효율적이고 간결하며 가독성있게 나타낼 수 있는 것이, 바로 비트표기이며

 우리는 이를 1111(2)로 나타낼 수 있습니다. (오른쪽부터 원소 1입니다)

 이 집합의 원소 중, 세번째 원소가 존재하는 지 확인하고자 한다면, 우리는 마스크를 씌울 수 있는데

 이것이 비트마스크입니다.

 1111(2) & 0100(2) => 0100(2) > 0 으로 세번째 원소가 존재하게 됨을 알 수 있습니다.

#include<iostream>
#include<bitset>
 
using namespace std;
 
int main(){
    unsigned int data = 0x1234;
    /* 
        0x1234 = 16^3 + 2*16^2 + 16*3 + 4
        = 4096 + 512 + 48 + 4
        = 4660
        = 0001 0010 0011 0100
        집합원소로 표현 가능!
        1부터 16까지 원소가 존재한다고 가정하면
        현재 집합의 원소는 3 5 6 10 13이 존재한다. 
    */
    cout << bitset<16>(data) << endl;
}

비트마스크를 사용하는 방법은.

1. i번째 요소를 추가

data | (1<<i)

2. i번째 요소를 검사

data & (1 << i)    // 존재하지 않으면 음수입니다.

3. i번째 요소를 제거

data & ~(1<<i)   

ex) 0011 & ~(0010) => 0011 & 1101 => 0001

4. i번째 요소 변경

data ^ (1 << i)

아래의 예시를 참고로, 이해가 충분히 가능할 것 같습니다!!

#include<iostream>
#include<bitset>        // bit 출력 STL 
 
using namespace std;
 
int main(){
    // data는 1111 1111 1111 1111이며
    // 이때 모든 비트는 1이기 때문에
    // 모든 원소가 존재하는 집합이라고 말할 수 있다.
    unsigned int data = 0xffff;
    cout << bitset<16>(data) << endl;
    
    // 두번째 원소 제거하기 
    data = data & ~(1<<1);                                // 집합의 원소를 제거 
    cout << bitset<16>(data) << endl;                    // 1111 1111 1111 1101
    
    // 두번째 원소 추가하기 (이미 존재하면 그대로) 
    data = data | (1<<1);            
    cout << bitset<16>(data) << endl;                    // 1111 1111 1111 1111
    
    // 두번째 원소가 포함되어 있는지 검사
    data = data & (1<<1); 
    cout << bitset<16>(data) << endl;                    // 존재하면 > 0, 존재하지 않으면 < 0 
    
    // 두번째 원소를 바꾸기 1 -> 0, 0 -> 1
    data = data ^ (1<<1);
    cout << bitset<16>(data) << endl; 
    
    // 두번째 원소가 포함되어 있는지 검사
    data = data & (1<<1); 
    cout << bitset<16>(data) << endl;                    // 존재하면 > 0, 존재하지 않으면 < 0 
    
    return 0;
} 

※ 본 글은 개인 포트폴리오 혹은 공부용으로 사용하기 때문에, 무단 복사 유포는 금지하지만, 개인 공부 용도로는 얼마든지 사용하셔도 좋습니다.