[알고리즘 이론] 비트마스크(BitMask)

비트마스크(BitMask)

비트마스크(BitMask)는 정수의 이진수 표현을 자료구조 처럼 사용하는 기법이다.

0과 1을 이용하여 비트를 표현하며 해당 비트가 0인 경우 "꺼져있다", 1인 경우 "켜져있다" 라고 말한다.

 

비트마스크의 장점

• 수행 시간이 빠르다
  - 비트 연산이므로 O(1)에 구현되는 연산들이 많다

 

• 메모리 효율성
  - 하나의 정수는 32비트기 때문에 2^32 가지의 표현이 가능하다.

 

• 코드의 간결성
  
  

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

집합 구현은 비트마스크의 가장 대표적이고 중요한 사례이다.

하나의 비트는 원소 하나를 의미하게 되며 비트가 켜진 경우 포함, 꺼진 경우 미포함을 의미한다.

즉, N비트 정수 변수는 N개의 원소를 가지는 집합의 부분집합들을 모두 표현할 수 있다.

이는 N개의 bool형 원소를 갖는 배열을 선언하는 것보다 메모리를 훨씬 절약할 수 있다.

 

S라는 변수를 집합이라고 하고, 원소의 총 개수를 N라고 가정할 때

연산	코드 표현
공집합으로 만들기	S = 0;
모든 원소 포함하는 집합으로 만들기	S = (1 << N) - 1;
K번째 비트 켜기	S |= (1 << K);
K번째 비트 끄기	S &= ~(1 << K);
K번째 비트 뒤집기(toggle)	S ^= (1 << K);
K번째 비트 포함 여부 확인	if((S & (1 << K))

---