비트마스크(BitMask)
BitMask는 정수의 이진수 표현을 자료구조로 사용하는 기법이다.
비트마스크의 장점은 무엇일까?
- 빠른 수행시간
- 짧은 코드
- 적은 메모리 사용량
비트 연산자
비트마스크는 이진 연산을 하므로 비트 연산자를 사용한다.
- AND 연산(&) : 둘 다 1이면 1, 아니면 0
- OR 연산(|) : 둘 다 0이면 0, 아니면 1
- XOR 연산(^) : 둘이 다르면 1, 아니면 0
- NOT 연산(~) : 0이면 1, 1이면 0
- SHIFT 연산(<<, >>) : 비트들을 왼쪽(<<) 또는 오른쪽(>>)으로 이동
비트마스크를 이용한 집합 구현
비트마스크를 이용하면 집합을 쉽게 표현 할 수 있다.
다음은 S를 집합이라고 가정하고, 집합의 총 원소 개수를 k이라고 가정한 예시이다.
- 공집합 :
S = 0; - 꽉 찬 집합 :
S = (1 << k) - 1; - e 원소 추가 :
S |= (1 << e); - e 원소 삭제 :
S &= ~(1 << e); - e 원소 포함 여부 :
S & (1 << e); - e 원소 토글 :
S ^= (1 << e);
@minzdev