[알고리즘] 비트마스킹

비트마스킹

정수의 이진수 표현을 자료구조로 사용하는 기법
집합을 나타내기에 유용하다.

전체집합의 원소들에 번호(0 ~ n-1)를 매겨 해당 원소가 존재하면 1 존재하지 않으면 0으로 표기한다.

에를 들어 전체집합 U = {a, b, c, d} 에서 부분 집합 A = {a}는 A = 0001(2)로 나타낼 수 있다. 마찬가지로 B = {b, d}는 B = 1010(2)로 나타낼 수 있을 것이다. 집합의 원소 표기를 이렇게 단순한 정수로 저장할 수 있으므로(집합 A의 경우 8로 저장, 집합 B의 경우 5로 저장) 코드가 매우 간단해지고 메모리 사용량을 줄일 수 있다.

---

기대효과

• 수행 시간 단축
• 코드 간결화
• 메모리 절약

---

구현

비트 연산자를 이용해 간단하게 구현할 수 있다.

원소 추가

집합 A에 n번 원소를 추가하는 방법은 다음과 같다.

A = A | (1 << n)

시프트와 OR 연산자를 이용해 n번 째 비트를 1로 바꾼다.

원소 제거

집합 A에서 n번 원소를 제거하는 방법은 다음과 같다.

A = A & ~ (1 << n)

n번 째 비트만 0으로 바꾸어 AND연산을 한다.

원소 확인

집합 A에 n번 원소가 있는지 확인하는 방법은 다음과 같다.

!((A & (1 << n)) == 0)

해당 값이 참일 경우 집합 A에는 n번 원소가 있다.

집합 연산

A | B  //A와 B의 합집합
A & B  //A와 B의 교집합
A & ~B //A와 B의 차집합 
A ^ B  //(A ∪ B)-(A ∩ B)