비트 마스크(Bit Mask) - 활용(집합 연산)

 지난 번에는 비트 마스크의 기본인 비트 연산자를 간단하게 알아보았다.

 

그렇다면 이번에는 비트 마스크를 활용하는 예를 알아보는 게 좋지 않을까?

 

비트마스크의 가장 대표적인 활용은 바로 집합에서 이뤄진다. 비트 마스크 기법을 활용하면 

 

집합의 공집합, 원소 추가, 삭제, 포함 여부, 합집합, 교집합 등등 다양한 연산을 간단하게 실행할 수 있다.

 

1. 공집합과 꽉 찬 집합

위와 같이 공집합인 경우 그냥 0인 상태이고,

 

풀집합일 경우 1을 시프트 연산으로 한 자리 수 더 크게 만든 다음 1을 빼면 

 

해당 집합 크기에 모든 값이 1인 비트 값을 만들어 낼 수 있고, 이는 꽉 찬 집합과 같은 비트 값이다.

 

이렇게 간단히 비트 마스킹을 통해 공집합과 꽉 찬 집합을 확인할 수 있다.

 

 

2. 원소 추가, 삭제

 

추가의 경우 |(OR)연산을 실행한다면, 해당 집합에 추가할 요소가 없을 경우 

 

true로 바꾸어 추가가 되는 것이다.

 

 반대로 삭제 연산은 해당 요소가 모두 1이어야 1이 도출되는 AND 연산을 기반으로 한다.

 

1을 K번째까지 이동시킨 후 NOT연산으로 반전시키면 0이 되기 때문에 

 

이때 AND 연산을 하면 1과 0을 비교하게 되어 삭제를 할 수 있는 것이다.

 

 

3. 원소 토글

 

K번 비트가 1이면 0, 0이면 1로 바꾸는 토글 연산도 위와 마찬 가지로 쉽게 구현할 수 있다.

 

XOR 연산을 통해 해당 위치의 토글을 켜고 끌 수 있다.

 

XOR 연산은 비교 되는 두 값 중 하나만 1일 경우 (켜져 있을 경우) 1을 도출한다.

 

따라서 1 값을 가지고 해당 위치와 XOR 연산을 실행하면 간단하게 토글 연산이 가능하다.

 

4. 합집합, 교집합, 차집합 등의 집합 연산

 

위의 연산들을 살펴보면 집합과 관련된 연산을 할 때도 감이 어느정도 잡힐 것이다.

 

우선 합집합과 교집합은?

 

OR 연산을 쓰면 간단하게 도출할 수 있다.

 

 

 

합집합과 교집합은 각각 OR 연산과 AND 연산을 통해 간단하게 도출할 수 있다.

 

 

차집합의 경우는 어떨까?

 

논리적으로 생각을 해보면 A집합에서 B집합과의 교집합을 빼면 된다.

 

하지만 이를 2진수에서 어떻게 표현할까? 또 이를 어떻게 비트 연산자로 표현할 수 있을까?

 

답은 바로 AND 연산자와 NOT 연산자의 조합으로 도출할 수 있다. 

 

 

 

위와 같이 NOT연산을 통해 반전을 시킨 뒤 AND 연산으로 교집합을 찾으면 

 

결국 A-(AandB)값이 도출된다.

 

 

 

라고 이해했다.