[알고리즘]비트마스크(BitMask), 비트조작 - 파이썬

비트마스크란?

---

• 비트마스크는 알고리즘이라기 보다는 알고리즘보다는 테크닉 중 하나
• 정수의 이진수 표현(비트, 0과 1의 binary digits)을 활용한 기법
• states = [True, False, False, True, True, False, False, False, True, True] 등으로 상태 표현 가능

  # 길이가 5인 집합 { 0, 1, 2, 3, 4 } 있다고 하자
  arr = [1, 1, 1, 1, 0] # 배열로 표현하면 비효율
  { 1, 2, 3, 4 } => 11110 # 메모리 적게 차이하고 효율적
  { 1, 2, 3, 4 } => 11110 => (2^4 * 1) + (2^3 * 1) + (2^2 * 1) + (2^1 * 1) = 30 # 10진수 표현 가능

• 코드를 간결하게 작성 가능하며 메모리를 적게 차지하고 수행 시간이 빠르다.
• DP, 순열 등 활용 가능

비트연산자, 파이썬

---

• 2진수를 10진수로 변환하기
  • int('0b1101',2) # 13, python에서는 앞에 '0b'를 붙여 이진수 표현 가능
• AND 연산(&) : 대응하는 두 비트가 모두 1이면 1을 반환
  • bin(0b1010011010 & 0b1101101100) # 0b1000001000
• OR 연산(|) :대응하는 두 비트가 하나라도 1이면 1을 반환
  • bin(0b1010011010 | 0b1101101100) # 0b1111111110
• XOR 연산(^) : 대응하는 두 비트가 서로 다르면 1을 반환
  • bin(0b1010011010 ^ 0b1101101100) # 0b111110110
• NOT 연산(~) : 비트의 값을 반전하여 반환
  • bin(~0b111) # -0b1000
• 시프트(Shift) 연산(>>, <<) : 왼쪽 또는 오른쪽으로 비트를 옮긴다
  • bin(0b0010 << 2) # 0b1000
  • bin(0b1100 >> 2) # 0b11

비트마스크를 활용한 삽입, 삭제, 조회는 어떻게 이루어질까?

1. 원소추가 : n번째 비트의 값을 1로 변경

   n = 3
   print(bin(0b0010 | (1 << n)))  #  0b1010

2. 원소삭제 : n번째 비트의 값을 0으로 변경

   n = 3
   print(bin(0b1010 & ~(1 << n)))  #  0b10

3. 원소 조회: n번째 비트의 값을 알 수 있는 방법

   n = 3
   print(bin(0b1010 & (1 << n)))  #  0b1000

비트마스크 예제문제(추가예정)