[Algorithm] 비트마스크 (BitMask)

비트 마스크 (BitMask)

컴퓨터의 연산방식을 이용하여 정수의 이진수 표현을 자료구조로 쓰는 기법

 

*비트 (bit)란?

컴퓨터에서 다루는 최소 단위로 0과 1로 이루어짐

 

장점

• 빠른 수행시간
• 간결한 코드
• 더 적은 메모리 사용

 

비트 연산자

c = a & b    # AND    000101 & 000011 = 000001
c = a | b    # OR     000101 |  000011 = 000111
c = a ^ b    # XOR    000101 ^ 000011 = 000110
c = ~a       # NOT   ~000101 = 111010
c = a << b   # SHIFT  000101 << 000011 = 101000
c = a >> b   # SHIFT  000101 >> 000011 = 000000

1. AND 연산

대응하는 두 비트가 모두 1일 경우 1, 아니면 0

 

2. OR 연산

대응하는 두 비트가 모두 0일 경우 0, 아니면 1

 

3. XOR 연산

대응하는 두 비트가 서로 다르면 1, 아니면 0

 

4. NOT 연산

해당 비트가 1이면 0, 0이면 1

 

5. shift 연산

오른쪽 또는 왼쪽만큼 비트를 옮김

 

 

비트마스크 활용하기

집합구현

하나의 bit가 하나의 원소를 의미하게 집합의 부분집합들을 모두 표현할 수 있다. (1이면 포함, 0이면 포함X)

 

ex. 여러 종류의 토핑이 있는 피자

# toppings = ['tomato','cheese','pepperoni','onion']
# Pizza = ['cheese','pepperoni','onion'] -> 0111

Pizza |= (1<<tomato)	# 원소 추가
Pizza &= ~(1<<onion)	# 원소 삭제
Pizza ^= (1<<pepperoni)	# 원소 토글 (있으면 삭제, 없으면 추가)

if (Pizza & (1<<cheese)) # 원소의 존재여부 확인

 

[참고]

https://jooncco.com/algorithms/bitmask/