[Algorithm] 알고리즘 준비 02. 비트마스크

비트 마스크
정수로 집합을 표현함
집합 {1, 3, 4, 5, 9} 는 정수 570으로 표현 가능 2^1 + 2^3 + 2^4 + 2^5 + 2^9 = 570
집합에 n을 포함 되어 있는지 검사
570 & (1 << n) = 0 이면 n이 없고 0이 아니면 n이 집합에 포함 되어 있다.
집합 연산
집합 S에 관하여,
- n 추가하기
S = S | ( 1 << n)
- n 제거하기
S = S & ~( 1 << n )
- 전체 집합
S = (1 << N ) - 1
- 공집합
S = 0