🧚‍♂️알고리즘🧚‍♂️ - 비트마스킹

🧚‍♂️ 비트마스킹🧚‍♂️

정수의 이진수 표현을 자료구조로 쓰는 기법

---

🧚‍♂️연산🧚‍♂️

• AND 연산 (&): 대응하는 두 비트가 모두 1일 때, 1 반환
• OR 연산 (|): 대응하는 두 비트가 하나라도 1일 때, 1 반환
• XOR 연산 (^): 대응하는 두 비트가 서로 다르면, 1 반환

1010 & 1111 = 1010
1010 | 1111 = 1111
1010 ^ 1111 = 0101

• NOT 연산 (~): 비트의 값을 반전하여 반환

~1010 = 0101

• 왼쪽 Shift (<<): 왼쪽으로 비트를 옮긴다. (수 * 2^k)
• 오른쪽 Shift (>>): 오른쪽으로 비트를 옮긴다. (수 / 2^k) 

# k=2일때 결과
00001010 << k = 101000
00001010 >> k = 000010

---

🧚‍♂️활용🧚‍♂️

<방문 체크>

 visited = [False] * 10

visited = 0b0000000000

 

 

< 집합에서 원소 추가 >

S에 num을 추가 -> "S의 num번 비트만 1로"

 

 (1 << num): num번째를 1로 만들어줌

S |= (1 << num)

 

 

< 집합에서 원소 삭제 >

S에서 num을 삭제 -> " S의 num번 비트를 0으로"

 

 ~(1 << num) :  num번 비트만 0으로 만들고 나머지는 1로 만들어 주기

이후 and 연산 : num을 제외한 나머지 비트는 동일한 상태를 유지

S &= ~(1 << num)

 

 

< 집합에서 원소 토클 >

S에 num이 없다면 추가, 있다면 삭제

 

xor 연산 :  두 비트가 서로 다를 때 1을 반환

S ^= (1 << num)

 

 

< 집합에서 원소 체크 >

S에 num이 있으면 1, 없으면 0을 출력

 

and 연산 : 두 비트가 모두 1이어야 1을 반환

print(1 if S & (1 << int(op[1])) != 0 else 0))

 

 

< 집합에서 원소 비우기,채우기 >

원소를 비우기 -> S의 모든 비트를 0으로

원소를 채우기 -> S의 모든 비트를 1으로

S = 0              #비우기
S = (1 << 21) - 1  #채우기    (1 << 21)은 1000000000000000000000 -> 한자릿수 줄이면서 모두 1로 하기: 1을 빼주기

---

< 집합끼리의 연산 >

A | B   # 합집합
A & B   # 교집합
A & ~B  # 차집합 (A - B)
A ^ B   # A와 B 중 하나에만 포함된 원소들의 집합

 

 

< 집합의 크기 >

집합의 크기 구하기 -> 비트에서 1인 비트 수를 세기

 

x % 2는 마지막 비트를 의미

x // 2는 마지막 비트의 삭제를 의미

def bitCount(x):
	if x == 0: return 0
	return x % 2 + bitCount(x//2)

---

🧚‍♂️활용🧚‍♂️

https://www.acmicpc.net/problem/11723

import sys

m = int(sys.stdin.readline())

bit = 0
for i in range(m):
    comm = sys.stdin.readline().rstrip().split()

    if comm[0] == "all":
        bit = (1 << 20) - 1
    elif comm[0] == "empty":
        bit = 0
    else:
        op = comm[0]
        num = int(comm[1]) - 1

        if op == "add":
            bit |= (1 << num)
        elif op == "remove":
            bit &= ~(1 << num)
        elif op == "check":
            if bit & (1 << num) == 0:
                print(0)
            else:
                print(1)

        elif op == "toggle":
            bit = bit ^ (1 << num)

---

출처

[Python] 비트 마스킹 정리

[백준] 11723 집합 (파이썬 비트마스크)