비트마스킹

비트마스크란?

• 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료구조로 쓰는 기법이다.
• 이진수는 0 또는 1을 이용하므로 두 가지로 표현할 수 있다. 
• 장점
  1. 수행 시간이 빠르다. (bit 연산은 O(1)에 구현되는 것이 많다.)
  2. 코드가 짧다. (다양한 집합 연산들을 비트연산자로 한 줄로 작성할 수 있다.)
  3. 메모리 사용량이 적다. (가장 큰 장점, DP에 매우 유용하게 쓰임.)
• 비트 연산자 종류
  • AND 연산 (a&&b) → 대응하는 숫자가 모두 1이면 1 반환 
  • OR 연산 (a||b) →  대응하는 숫자 중 하나라도 1이면 1 반환 
  • XOR 연산 (a^b) → 대응하는 숫자가 서로 다를 경우 1 반환
  • NOT 연산 (~a)
  • SHIFT 연산 (>>, <<)

비트마스크와 집합

AND 연산 

bin(0b1010011010 & 0b1101101100)
# 0b1000001000

OR 연산 

bin(0b1010011010 | 0b1101101100)
# 0b1111111110

XOR 연산

bin(0b1010011010 ^ 0b1101101100)
# 0b0111110110

SHIFT 연산

bin(0b0010 << 2) # 0b1000
bin(0b1100 >> 2) # 0b11

 

원소 추가 

현재 상태 cur에서 p번 원소 추가 → cur에서 p번 비트만 1로 바꾸고 나머지 비트는 원상태 유지

cur = cur | (1<<p)

원소 삭제

cur = cur & ~(1<<p)

원소 토글

cur = cur ^ (1<<p)

집합 연산(합집합, 교집합, 차집합..)

a | b # a,b 합집합
a & b # a,b 교집합
a & ~b # a에서 b를 뺀 차집합
a ^ b # a,b 중 하나에만 포함된 원소들의 집합

 

# 백준 12813 - 이진수 연산

import sys
input = sys.stdin.readline
A = int(input(),2) # 2진수를 int형으로 변환
B = int(input(),2)

mask = 2**100000-1
print(bin(A & B)[2:].zfill(100000))
print(bin(A | B)[2:].zfill(100000))
print(bin(A ^ B)[2:].zfill(100000))
print(bin(A ^ mask)[2:].zfill(100000))
print(bin(B ^ mask)[2:].zfill(100000))