비트마스크

비트마스크

 

비트마스크란?

내부적으로 이진수를 사용하는 컴퓨터는 이진법 관련 연산을 빨리 진행할 수 있다.

이런 특성을 이용해 정수의 이진수 표현을 자료 구조로 쓰는 기법을 비트마스크(bitmask)라고 한다.

보통은 집합에서 주로 쓰인다.

 

 

비트마스크의 장점

빠른 속도

비트마스크 연산은 O(1)에 구현되는 것이 많기 때문에 적절히 사용한다면 다른 자료구조들에 비해 빨리 동작한다.

비트마스크를 사용한다는 것은 애초에 원소의 개수가 많지 않다는 것을 의미하긴 하지만 같은 연산을 여러번 수행해야 할 경우에는 이런 사소한 차이가 큰 속도 향상을 가져올 수 있다.

 

* int(정수형) = 4 Bytes = 32 bits

 

간결한 코드

다양한 집합 연산들을 배열이나 반복문을 쓸 필요 없이 한 줄에 쓸 수 있기 때문에 비트마스크를 적절히 사용하면 코드를 줄일 수 있다.

 

적은 메모리 사용량

여타 배열보다는 변수 하나에 비트마스크를 담을 수 있으므로 메모리를 아낄 수 있다.

 

 

비트 연산자

AND a & b

두 개의 비트가 모두 1일 때만 1

 

OR a | b

두개의 비트 중 하나라도 1이라면 1

 

NOT ~a

비트가 1이라면 0, 0이라면 1

 

XOR a ^ b

비트가 서로 다르다면 1, 같다면 0

 

shift a<<b, a>>b

정수 a의 비트를 왼쪽(<<) 혹은 오른쪽(>>)으로 b만큼 움직임

 

 

비트마스크 예제

(※이 설명은 기본적인 비트 연산과 이진수를 알고 있다는 가정하에 설명됩니다.)

보통 비트마스크는 집합의 표현으로 주로 쓰인다.

예를 들어 원소 A, B, C, D가 있다고 가정하자.

• 집합에 포함 : 1
• 집합에 미포함 : 0

집합 S에 아무런 원소가 없다면(초기화) 아래와 같이 표현이 가능할 것이다.

S = (0000)₂ = 0

 

그럼 위 상태에서 A원소를 추가해보자.

• 원하는 원소를 가리키기 위해서는 shift 연산이 필요하고
• 이를 집합 S에 포함하기 위해서는 or 연산이 필요하다.

1. 원소 가리키기

n번째 원소를 가리킨다면 아래와 같이 표현할 수 있다.

• 1 << n

위 연산을 해석하자면 (0001)₂를 n만큼 왼쪽으로 이동하라는 뜻이다.

만약, 1 << 3이라면 왼쪽으로 3칸 이동하므로 (1000)₂이 될 것이다.

 

2. 집합에 포함시키기

가리킨 원소를 집합에 포함시키기 위해서는 간단히 or연산으로 가능하다.

[ OR 연산 결과 ]

 

정리하자면, 집합에 원소를 포함시키는 방법은 아래와 같다.

포함하고자 하는 원소가 n번째 위치에 있다면 이와 같이 표현 가능하다.

• S |= (1 << n)

 

원소의 포함 여부를 알고 싶다면 어떻게 해야 할까?

이 방법은 앞서 원소 추가 방법과 비슷하지만 OR이 아닌 AND연산을 해야 한다.

집합 S와 알고 싶은 원소( 1 << n )를 AND연산을 통해 유무를 판단한다.

• if( S & ( 1 << n ))

 

원소를 삭제하기 위해서는?

1. 삭제하고자 하는 원소를 가리킨다(Shift). ( 1 << n )
2. 해당 비트를 뒤집는다(NOT). ~( 1 << n )
3. 집합 S와 AND 연산을 해준다. S &= ~( 1 << n )

 S &= ~( 1 << n )

AND연산은 둘 다 참일 때만 참이므로 위의 식을 사용한다면 원하는 원소만 0이 되므로 이와 같이 원소를 삭제할 수 있다.

 

 

비트마스크 연산

합집합

int added = (a | b)

 

교집합

int intersection = (a & b)

 

a에서 b를 뺀 차집합

int remove = (a & ~b)

 

a와 b 중 하나에만 포함된 원소들의 집합

int toggled = (a ^ b)