[Algorithms] 비트마스크

💡비트마스크 : 집합의 요소들의 구성 여부를 표현할 때 유용한 테크닉

비트마스크를 사용하는 이유

• DP나 순열 등, 배열 활용만으로 해결할 수 없는 문제

• 작은 메모리와 빠른 수행시간으로 해결이 가능 (But, 원소의 수가 많지 않아야 함)

• 집합을 배열의 인덱스로 표현할 수 있음

• 코드가 간결해짐

---

비트(Bit)란?

컴퓨터에서 사용되는 데이터의 최소 단위 (0과 1)
2진법을 생각하면 편하다.

예시) 9 (10진수) -> 1001 (2진수)

---

비트마스킹 활용해보기

0과 1로, flag 활용하기

[1, 2, 3, 4, 5] 라는 집합이 있다고 가정해보자.

여기서 임의로 몇 개를 골라 부분집합을 만든다고 해보자.

여기서 비트마스킹을 이용하면, 각 요소를 인덱스처럼 표현하여 효율적인 접근이 가능하다.

[1, 2, 3, 4, 5] -> 11111
[2, 3, 4, 5] -> 11110
[1, 2, 5] -> 10011
[2] -> 00010

집합의 i번째 요소가 존재하면 1 , 존재하지 않으면 0을 의미하는 것이다.

---

비트 연산

AND, OR, XOR, NOT, SHIFT

• AND(&) : 대응하는 두 비트가 모두 1일 때, 1 반환

• OR(|) : 대응하는 두 비트 중 모두 1이거나 하나라도 1일때, 1 반환

• XOR(^) : 대응하는 두 비트가 서로 다를 때, 1 반환

• NOT(~) : 비트 값 반전하여 반환

• SHIFT(>>, <<) : 왼쪽 혹은 오른쪽으로 비트 옮겨 반환

---

비트 연산 활용⭐️

1. 삽입 -> OR 연산 이용

현재 이진수로 10101로 표현되고 있을 때, 3번째 비트 값을 1로 변경하려고 한다.
변경 후에는 11101이 나와야 한다. 이때는 OR연산을 활용한다.

10101 | 1 << 3

2. 삭제 -> AND, NOT 연산 이용

현재 이진수로 11101로 표현되고 있을 때, 3번째 비트 값을 0로 변경하려고 한다.
변경 후에는 10101이 나와야 한다. 이때는 AND연산과 NOT연산을 활용한다.

11101 & ~1 << 3

2. 조회 -> AND연산 이용

현재 이진수로 10101로 표현되고 있을 때, i번째 비트 값을 확인하려고 한다.
이때는 AND연산을 활용한다.

10101 & 1 << i