특징
- 여러개의 상태를 하나의 변수에 담기 위해서
- CPU가 매우 빠르게 연산 가능하고, 메모리 효율 좋게 상태를 관리하기 위해서
기본 소개
비트 마스킹은 비트 연산을 활용해서 집합을 구현하는 방법이다. 각 자리수의 비트는 하나의 원소를 나타내며, 이 원소들이 모여서 집합을 구성하게 된다.
예를 들어, 원소 A, B, C, D를 각각 다음과 같이 표현할 수 있다:
let A = 0b0001 // 1
let B = 0b0010 // 2
let C = 0b0100 // 4
let D = 0b1000 // 8혹은 쉬프트 연산을 활용해서 표현할 수도 있다. 이 방법이 조금 더 직관적이고 단순하다:
let A = 1 << 0
let B = 1 << 1
let C = 1 << 2
let D = 1 << 3이렇게 원소들을 정의하게 되면, 각 원소들이 각각의 자릿수를 점유하고 있기 때문에 겹칠 일이 없다. 따라서 2진수로 쉽게 집합을 표현할 수 있다.
예를 들어, A와 B를 포함하는 집합은 다음과 같다:
let bitSet = 0b0011 // 3비트 연산
비트 마스킹으로 표현한 집합은 비트 연산자를 활용하여 연산을 하기 때문에 주요 연산자들을 알아야 한다. 아래 표는 간략하게 나타낸 것이고, 진리표를 찾아봐도 좋다:
| 연산자 | 이름 | 의미 | 사용법 |
|---|---|---|---|
| & | AND | 둘 다 1일 때만 1 | a & b |
| | | OR | 둘 중 하나가 1이면 1 | a | b |
| ~ | NOT | 비트를 반전한다. | ~a |
| ^ | XOR | 서로 다르면 1 | a ^ b |
| << | Left Shift | 비트 왼쪽으로 이동 (곱셈) | a << 1 |
| >> | Right Shift | 비트 오른쪽으로 이동 (나눗셈) | a >> 1 |
삽입, 삭제, 탐색(체크), 토글
비트 연산을 쓰면 집합에서 삽입, 삭제, 탐색, 토글 연산을 아주 쉽게 할 수 있다.
삽입
OR 연산을 사용한다.
다음은 집합에 원소 D를 삽입하는 예시다:
bitSet = bitSet | D
// 0011
// OR 1000
// --------
// 1011삭제
AND와 NO을 조합하여 특정 원소를 삭제할 수 있다.
다음은 집합에서 원소 B를 삭제하는 예시이다:
bitSet = bitSet & (~B)
// NOT 0010 = 1101
//
// 1011
// AND 1101
// ---------
// 1001체크
AND 연산을 한 결과를 찾고 싶은 원소와 비교해서 원소가 포함되어 있는지 확인할 수 있다:
if bitSet & A == A {
print("bitSet contains A")
} else {
print("bitSet not contains A")
}
// 1001
// AND 0001
// ---------
// 0001토글
만약 집합에서 원소가 없으면 추가하고, 있다면 제거하는 토글 기능을 XOR을 이용해서 쉽게 해결할 수 있다.
집합에서 A가 있으면 제거하고, 없으면 추가해보자:
bitSet = bitSet ^ A
// 1001
// XOR 0001
// ---------
// 1000심화
비트 마스킹으로 표현한 집합도 합집합, 교집합, 차집합 연산을 할 수 있다.
합집합
집합에 원소를 추가할 때 처럼, OR 연산을 통해 쉽게 할 수 있다:
let union = set1 | set2교집합
AND 연산을 활용한다:
let intersection = set1 & set2차집합
원소를 제거할 때와 마찬가지로 AND와 NOT의 조합을 이용하면 된다, 다음은 A에서 B를 뺀 차집합이다:
let difference = set1 & (~B)