정수의 이진수 표현을 자료구조로 쓰는 기법
시간복잡도 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를 공집합으로 바꾼다.
S = S = (1 << 21) - 1
# 1 0000 0000 0000 0000 0000 에서 1을 빼기
# 1111 1111 1111 1111 1111 (1~20 원소가 모두 존재)
S = 0
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로 비트를 바꾼다 (원소를 추가한다)
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 원래 상태 유지
S = S ^ (1 << b)
# 해당 비트에 XOR 연산 적용
print(1 if S & (1 << b) != 0 else 0)
# AND 연산 결과가 0이 아니면 원소가 존재