[Algorithm] Bitmask (비트마스크) (Swift)

Bitmask란?

Bitmask는 단어 그대로 비트에 마스킹을 한다라는 뜻인데, 비트 연산을 활용하여 데이터를 효율적으로 저장하고 조작하는 방법이다. 비트(Bit)는 컴퓨터 과학에서 정보의 가장 작은 단위이다. 비트는 이진법(Binary System)을 기반으로 하며, 두 가지 값(0, 1) 중 하나를 가질 수 있다.

 

비트연산

Bitmask를 하기 전에 비트 연산에 대해서 알아야 한다. 비트 연산에는 AND, OR, XOR, NOT, Shift연산이 있다. 아래와 같은 게이트들을 접해봤을 것이다. (직접 그려봤는데 생각보다 그리기 힘들다 😅)

처음에는 OR과 XOR이 약간 헷갈렸는데 아래의 개념으로 생각한다면 아주 이해가 쏙쏙 된다.

AND 연산 ( & )

1101 & 1011 을 하게 되면 두 비트가 모두 1일 때만 1을 반환하여 1001 이 나오게 된다.

let a: UInt8 = 0b1101
let b: UInt8 = 0b1011
let result = a & b
print(String(result, radix: 2)) // 1001

 

OR 연산 ( | )

1101 | 1011 을 하게 되면 두 비트 중 하나라도 1이면 1을 반환하여 1111 이 나오게 된다.

let a: UInt8 = 0b1101
let b: UInt8 = 0b1011
let result = a | b
print(String(result, radix: 2)) // 1111

 

XOR 연산 ( ^ )

1101 ^ 1011 을 하게 되면 두 비트가 다르면 1을 반환하여야 0110 이 나오게 된다.

let a: UInt8 = 0b1101
let b: UInt8 = 0b1011
let result = a ^ b
print(String(result, radix: 2)) // 110

 

NOT 연산 ( ~ )

비트를 반전시킨다. 1101인 경우 8비트이기 때문에 00001101에서 반전이 되어 11110010 이 나온다.

let a: UInt8 = 0b1101
let result = ~a
print(String(result, radix: 2)) // 11110010

 

Shift 연산 (  <<, >> )

비트를 이동시킨다 << 는 왼쪽, >> 는 오른쪽이다. 1101을 왼쪽으로 두 번 이동시키면 110100이 되고, 오른쪽으로 두번 이동시키면 앞의 01이 사라지고 11이 된다.

let a: UInt8 = 0b1101
let leftShift = a << 2
let rightShif = a >> 2

print(String(leftShift, radix: 2)) // 110100
print(String(rightShif, radix: 2)) // 11

 

비트마스킹

그렇다면 이 비트연산을 사용하여 비트마스킹을 어떻게 할 수 있을까? 여러 가지 활용법이 있겠지만 간단한 사용법은 아래와 같다.

비트삭제

& 연산과 ~ 연산을 활용하여 지울 수 있다. 아래와 같이 1101에서 오른쪽에서 세 번째 비트를 지우고 싶다면 아래와 같이 1을 2번 왼쪽으로 Shift 한 뒤 NOT 연산을 하게 되면 1011이 되는데 AND 연산을 하면 1001 이 되는 것이다. 말이 복잡할 뿐 절대 어렵지 않다.

var bitmask: UInt8 = 0b1101
let bitToClear: UInt8 = 1 << 2

bitmask &= ~bitToClear // 1101 & 1011
print(String(bitmask, radix: 2)) // 1001

 

비트토글

XOR 연산을 통해 간단하게 가능하다. 왜냐하면 XOR 은 같을 경우 0, 다를 경우 1을 반환하기 때문에 1001과 0100을 하게 된다면 1101 이 되고, 1101과 0100을 하게 된다면 1001이 된다.

var bitmask: UInt8 = 0b1001
let bitToToggle: UInt8 = 1 << 2

bitmask ^= bitToToggle // 1001 ^ 0100
print(String(bitmask, radix: 2)) // 1101

 

비트확인

AND 연산을 통해 확인 가능하다. 1101과 0100을 AND 연산하게 되면 0100 이 나오는데 이는 0이 아니기 때문에 원하는 위치에 1이 있는지 없는지 확인 가능하다.

var bitmask: UInt8 = 0b1101
let bitToCheck: UInt8 = 1 << 2

print(bitmask & bitToCheck != 0) // true

 

아래와 같이 여러 자리에 1이 있는지 없는지도 확인이 가능하다.

var bitmask: UInt8 = 0b1101
let bitToCheck: UInt8 = 0b0101

print(bitmask & bitToCheck == bitToCheck) // true

 

활용방법

그렇다면 이것을 어떻게 활용하는 것인지 궁금할 수 있다. 예를 들어보자면 a직원이 월화수목금에 일하고 b직원이 월수금에 일하는데 b직원이 일하는 날 a직원이 일하는지 판단하는 방법을 구하라고 한다면 아래와 같이 a 직원은 월화수목금 = 11111 로 두고, b 직원은 월수금 = 10101 으로 비트마스킹을 한다면 간단한 연산으로 판별이 가능하다.

var a: UInt8 = 0b11111
let b: UInt8 = 0b10101

print(a & b == b) // true