비트마스크 (Bit Mask)

비트마스크란 ?

• 비트마스크(Bit Mask)는 이진수를 사용하는 컴퓨터의  연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법을 말한다.
• 이진수는 0 또는 1을 이용하므로 하나의 비트(bit)가 표현할 수 있는 경우는 두 가지이다.
• 보통 어떤 비트가 1이면 "켜져 있다" 라고 말하며, 0이면 "꺼져 있다" 라고 말한다.

 

---

비트마스크의 장점

1. 수행 시간이 빠르다.
   • 연산이기 때문에 O(1)에 구현되는 것이 많다. 따라서 다른 자료구조를 이용하는 것보다 훨씬 빠르게 동작하게 된다. 이는 연산 횟수가 늘어날수록 차이가 매우 커지게 된다.
2. 코드가 짧다.
3. 메모리 사용량이 더 적다 ★
   • 예를 들면, bit가 10개인 경우에는 각 bit당 두 가지 경우를 가지기 때문에 2¹⁰ 가지 경우를 10bit 이진수 하나로 표현이 가능하다.
   • 이처럼 하나의 정수로 매우 많은 경우의 수를 표현할 수 있기 때문에 메모리 측면에서 효율적이며, 더 많은 데이터를 미리 계산해서 저장해 둘수 있는 장점이 있다. 
   • 따라서 방문처리를 예전에는 visited = [True, False, True, False] 로 했다면, 비트 마스킹으로 visited = 0b0101 으로 같은 표현을 할 수 있다.
     (비트 마스크에서 각 비트는 하위 주소(오른쪽)부터 인덱스를 센다.)

 

---

비트 연산

1. AND 연산 (&)

- 대응하는 숫자가 모두 1일 경우 1을 반환

bin(0b11110000 & 0b11001100) # 0b11000000

 

2. OR 연산 (|)

- 대응하는 숫자 중 하나라도 1일 경우 1을 반환

bin(0b11110000 | 0b11001100) # 0b11111100

 

3. XOR 연산 (^)

- 대응하는 숫자가 모두 다를 경우 1을 반환

bin(0b11110000 & 0b11001100) # 0b11111100

 

4. SHIFT 연산 (>>, <<)

- a << b : a의 비트를 b칸만큼 왼쪽으로 밀어냄

- a >> b : a의 비트를 b칸만큼 오른쪽으로 밀어냄

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

 

5. NOT 연산 (~)

- 비트 값을 반전시킴

bin(~0b11110000) # 0b00001111

---

비트 연산 응용

1. 원소 추가

- n번째 수를 추가하고자 할 때

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

 

2. 원소 제거

- n번째 수를 제거하고자 할 때

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

 

3. 원소 조회

- n번째 수가 있나 없나 확인할 때 (0이면 없고, 1 이상이면 있는 것)

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

 

4. 원소 토글

- n번째 수를 켜져 있으면 끄고, 꺼져 있으면 켬

n = 3
bin(0b1010 ^ (1 << n)) # 0b10

 

5. 공집합

bin(0)

 

6. 꽉 찬 집합

bin((1 << 10) - 1) # 0b1111111111

 

---

참조

https://rebro.kr/63

https://justkode.kr/algorithm/bitmash