[python] 비트 마스킹

Dawon Seo·2023년 7월 26일
0
post-thumbnail

비트 마스킹?

정수의 이진수 표현을 자료구조로 쓰는 기법
시간복잡도 O(1)의 빠른 연산 속도, 메모리 효율성 증가라는 이점을 가지고 있다

비트 연산자

a & b	# AND
a | b	# OR
a ^ b	# XOR
~a		# NOT
a << b	# SHIFT
a >> b	# SHIFT

비트마스킹을 사용한 집합 표현

백준 11723번 집합 문제를 바탕으로 연습해 보쟈

비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
all: S를 {1, 2, ..., 20} 으로 바꾼다.
empty: S를 공집합으로 바꾼다.

all (1~20 원소 채우기)

S = S = (1 << 21) - 1
# 1 0000 0000 0000 0000 0000 에서 1을 빼기
# 1111 1111 1111 1111 1111 (1~20 원소가 모두 존재)

empty

S = 0

add x (원소 x 추가)

S = S | (1 << b)
# 예를 들어, S의 현재 상태가 1000이라고 할 때(4 존재), 원소 2 추가를 위해 (1 << 2) = 0010과 OR 연산 수행
# 1000 | 0010 = 1010
# 만약 S의 현재 상태가 0011(1, 2 존재)인 상태에서 2 삭제 위해 0010과 OR 연산 수행할 경우,
# 0011 | 1101 = 0011 원래 상태 유지

이미 원소가 있으면 원래 값이 유지되고, 없으면 1로 비트를 바꾼다 (원소를 추가한다)

remove x (원소 x 삭제)

S = S & ~(1 << b)
# 예를 들어, S의 현재 상태가 1011이라고 할 때(1, 2, 4 존재), 원소 2 삭제를 위해 ~(1 << 2) = 1101와 AND 연산 수행
# 1011 & 1101 = 1001
# 만약 S의 현재 상태가 1001(1, 4 존재)인 상태에서 2 삭제 위해 1101과 AND 연산 수행할 경우,
# 1001 & 1101 = 1001 원래 상태 유지

toggle x (없으면 추가, 있으면 삭제)

S = S ^ (1 << b)
# 해당 비트에 XOR 연산 적용

check x (원소 x 있는지 확인)

print(1 if S & (1 << b) != 0 else 0)
# AND 연산 결과가 0이 아니면 원소가 존재

0개의 댓글