비스마스크란?

비트마스크 알고리즘은 0 또는 1로 표현되는 이진수 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 알고리즘이다. 이진수 표현을 사용하는 것이므로 비트마스크는 알고리즘이 아니라 "기법" 정도로 보는 의견도 있다.

이진수는 0 또는 1을 이용하므로 하나의 비트(bit)가 표현할 수 있는 경우는 두 가지이다.

보통 어떤 비트가 1이면 켜져 있다라고 말하며, 0이면 꺼져 있다라고 말한다.

집합 {1,2,3,4,5}의 부분집합 {1,4,5}를 표현한다고 하면 11001(2)가 된다.

비트마스크를 이용하면 다음과 같은 효과를 얻을 수 있다.

• 더 빠른 수행시간 -> O(1)의 시간복잡도
• 간결한 코드
• 적은 메모리 사용

비트 연산자

1. AND 연산 &
   대응하는 두 비트가 모두 1일 때 1 반환

2. OR 연산 |
   대응하는 두 비트 중 하나라도 1이라면 1, 아니면 0 반환

3. XOR 연산 ^
   대응하는 두 비트가 다르면 1, 같으면 0을 반환

4. NOT 연산 ~
   비트의 값을 반전

5. Shift 연산 <<, >>
   왼쪽 또는 오른쪽으로 비트를 이동

비트마스크를 이용한 집합 구현

비트마스크를 이용한 집합 구현은 가장 대표적이고, 중요한 사례이다.
하나의 bit가 하나의 원소를 의미하게 된다.

bit가 켜져(1) 있으면 해당 원소가 집합에 포함되어 있다는 의미이고, 꺼져(0) 있으면 포함되어 있지 않다는 의미이다. 

따라서 N비트 정수 변수라면 N개의 원소를 갖는 집합의 부분집합들을 모두 표현할 수 있게 된다.