[Algorithm] 비트마스킹

비트마스킹(BitMasking)

비트마스킹(BitMasking)이란 비트를 활용해 집합을 표현하는 기법이라고 볼 수 있다.

빠른 연산속도와 적은 메모리 사용량, 그리고 배열을 정수로 표현할 수 있다는 장점이 있다.

비트는 컴퓨터에서 사용되는 데이터의 최소단위인데 0과 1로 표현한다. 따라서 2진법이라고 생각하면 편하다.

비트마스킹은 이런 특징을 이용한다.

 

예를 들어 {1, 4, 3}이라는 집합이 있다고 해보자.

각 원소의 포함 여부를 이용해 부분집합을 표현하면 다음과 같다.

{1, 4} => 110

{3} => 001

{1, 3} => 101

 

또한 이를 10진수로 표현할 수도 있다.

{1, 4} => 110 => 6

{3} => 001 => 1

{1, 3} => 101 => 5

 

이러한 특징을 이용해 비트 연산을 해서 집합에 원소를 추가, 삭제 등을 할 수 있다.

우선 비트 연산을 어떻게 하는지 비트 연산자부터 알아보면 다음과 같다.

a&b	and 연산. 둘다 1이면 1, 그외엔 0	a = 100 b = 111 a & b = 100
a|b	or 연산. 둘다 0이면 0, 그외엔 1	a = 010 b = 101 a|b = 111
a^b	xor 연산. 둘이 다르면 1, 그외엔 0	a = 011 b = 101 a^b = 110
~a	not 연산. 0->1, 1->0	a = 001 ~a = 110
a<<b	shift 연산. a를 b만큼 왼쪽으로 시프트	a = 001 a << 2 = 100
a>>b	shift 연산. a를 b만큼 오른쪽으로 시프트	a = 100 a >> 2 = 001

 

그럼 비트 연산자를 통해 어떻게 집합의 연산을 표현할 수 있을까?

원소 추가

# 현재 상태 cur, p번 원소 추가
cur = cur | (1 << p)

원소 삭제

# 현재 상태 cur, p번 원소 삭제
cur = cur & ~(1 << p)

원소 토글

# 현재 상태 cur, p번 원소 있다면 삭제하고 없다면 추가
cur = cur ^ (1 << p)

합집합

a | b

교집합

a & b

차집합

a & ~b

합집합에서 교집합 제외한 집합

a ^ b

집합의 크기 구하기

function bitCount(x) {
    if x == 0:
      return 0
    return x % 2 + bitCount(x / 2)
}

모든 부분 집합 순회

for(subset = set; subset; subset = (subset - 1) & set) {
  # subset은 set의 부분집합 중 하나
}

원소 조회

# i번째 비트가 무슨 값인지 조회
cur & (1 << i)

 

 

참고

https://travelbeeee.tistory.com/451