비트 마스크, 비트 마스킹(Bit-Masking)이란? (비트 마스크 알고리즘, 비트 마스킹 알고리즘)

비트 마스킹(Bit Masking)이란?

---

• 비트 마스크는 알고리즘 테크닉
• 비트 마스크를 표현하면 집합을 효율적 + 빠르게 구현 가능
• 이진수(BIT)로 자료를 표현

비트 연산자

---

AND 연산 (&)

• 대응하는 비트가 모두 1(True)일 때, 1(True)반환

1010 & 1111 = 1010

OR 연산 (|)

• 대응하는 비트가 하나라도 1(True)일 때, 1(True)반환

1010 | 1111 = 1111

XOR 연산 (^)

• 대응하는 비트가 서로 다르면 1(True) 반환

1010 ^ 1111 = 0101

NOT 연산 (~)

• 비트의 값을 반전하여 반환 (1 -> 0, 0 -> 1)

~1010 = 0101

오른쪽 Shift 연산 (>>)

• 오른쪽으로 비트를 옮김 (밀기)

00001010 >> 2(N) = 00000010  # 오른쪽으로 비트를 2(N)칸만큼 밈, 나머지는 버림

왼쪽 Shift 연산 (<<)

• 왼쪽으로 비트를 옮김 (밀기)

00001010 << 2(N) = 00101000  # 왼쪽으로 비트를 2(N)칸만큼 밈

비트 마스크의 활용

---

• 방문 체크 할 시 유용하게 사용가능 (DP, 메모이제이션)

check = [False, True, False, False, True]

->

bit_check = 0b01001  # 0b는 python의 2진수 표현 방법

• 집합사용시 유용하게 사용가능

비트 마스크의 집합 표현

---

• 비트 마스크의 집합 표현은 비트 그자체를 집합으로 표현 (합집합, 교집합, 차집합 등 표현 가능)
• 비트 마스크의 집합 연산은 (1 << N)으로 쉽게 표현
  • 비트는 오른쪽부터 index로 세며, 0부터 Count (0, 1, 2, 3, …)
• 원소를 추가할 때

>>> print(bin(0b1010 | 1<<8))
0b100001010

• 원소를 제거할 때

>>> print(bin(0b10101 & ~(1 << 2)))  # 왼쪽에서부터 0, 1, '2'번째 원소가 0으로 제거 됨
0b10001

• 원소를 조회할 때 (0이면 False/1이상이면 True)

>>> print(bin(0b1010 & (1 << 1)))  # 1번째 비트는 존재함
0b10
>>> print(bin(0b1010 & (1 << 2)))  # 2번째 비트는 0이라 존재하지 않음
0b0
>>> print(bin(0b1010 & (1 << 3)))  # 3번째 비트는 존재함
0b1000
>>> print(bin(0b1010 & (1 << 4)))  # 4번째 비트는 존재하지 않음
0b0
>>> print(bin(0b1010 & (1 << 5)))  # 5번째 비트는 존재하지 않음
0b0
>>> print(bin(0b1010 & (1 << 6)))  # 6번째 비트는 존재하지 않음
0b0

• 원소를 반전할 때
  • 원소 제거로 사용할 수 도 있음 (단, 존재하지 않는 원소에 적용해도 반전 되어 적용 됨)

>>> print(bin(0b10101 ^ (1 << 2)))  # 0, 1, '2' 번째 원소 1이 0으로 반전 됨
0b10001
>>> print(bin(0b10101 ^ (1 << 3)))  # 0, 1, 2, '3' 번째 원소 0이 1로 반전 됨
0b11101

• 원소를 비우거나 채울 때

>>> x = 0b1010110
>>> print(bin(x))
0b1010110
>>> x = 0
>>> print(bin(x))
0b0
>>> x = (1 << 11) -1  # 10자리 비트를 1로 채울 때
>>> print(bin(x))
0b11111111111