1. 개념

비트마스킹으로 데이터를 표현하는 것 (배열을 대체)

2. 기본 비트 연산

(1) i번째 비트 clear

s &= (1<<i);

(2) i번째 비트 set

s |= (1<<i);

(3) i번째 비트 check

if(s & (1<<i))

(4) i번째 비트 xor

s ^= (1<<i)

(5) 최하위 set 되어있는 index 찾기

i = s & -s;

(6) 크기가 n인 집합의 모든 비트를 set

(1 << n) - 1;

3. 예시

(1) 경우의 수 표현

비트마스킹은 combi 함수와 마찬가지로 NC0,NC1,,,NCN의 경우의 수를 탐색할 수 있다.

#include <bits/stdc++.h>
using namespace std;

int main() {

    vector<char> arr = {'A', 'B', 'C', 'D'};

    for(int mask = 0; mask < (1<<4); mask++) { //4개의 포함, 불포함 경우의 수 모두 포함해야하니 0000~1111 사용

        cout << "{ ";

        for(int i=0;i<4;i++) { //오른쪽부터 set되어있는 인덱스 검사
            if(mask & (1<<i))
                cout << arr[i] << ' ';
        }

        cout << "}\n";
    }
}

4. 한계

int 자료형은 32비트이다 -> 최대 32개 요소의 포홤, 불포함 여부만 비트마스킹으로 나타낼 수 있다.