[Algorithm] 비트마스크

- 공간을 적게 사용 

- 정수

- 검사, 추가, 삭제의 3가지 연산이 모두 시간복잡도 O(1)로 수행 가능

 

 

1. 집합 S에 x가 있는지 검사

S & (1<<x)

 

2. 집합 S에 x 추가

S | (1<<x)

 

3. 집합 S에 x 제거

S | ~(1<<x)

 

4. toggle (0에서 1로, 1에서 0으로)

S ^ (1<<x)

 

5. 0~(N-1)까지의 전체집합

S = (1<<N) -1

 

6. 공집합

S = 0