비트마스크
21 Jun 2021전구가 5개가 있을 때 어떤 전구들이 켜져있는지 나타내는 방법은 무엇이 있을까? 전구의 각 상태를 arr로 저장해서 켜져있으면 1 아니면 0으로 나타내는 방법을 생각해보자. 만약 2, 3번째 전구가 켜져있다면 배열은 [0 0 1 1 0]으로 나타날 것이다.
배열을 다시보니 0과 1로만 표현되는 이진법과 형태가 같다는 것을 알 수 있다. 그렇다면 배열의 상태를 이진법 숫자로 변환해보자. 001102 -> 6 이렇게 표현하고 나니 배열을 쓰지 않고도 전체 상태를 간결히 확인 할 수 있을 것이란 생각이 든다.
이렇듯 비트마스크는 이진법을 이용한 숫자표현으로 배열의 상태를 나타내는 기법이다. 비트마스크를 활용하면 비트 연산을 활용하여 집합 상태의 추가, 삭제, 조회 등의 연산을 간단히 처리할 수 있다. 비트연산에는 크게 AND, OR, XOR, NOT, SHIFT가 있다.
- AND(&) 연산
대응하는 bit가 모두 1일때 1 반환, 그외에는 0
1010 & 1100 = 1000
- OR(|) 연산
대응하는 bit 중 하나라도 1이면 1 반환, 둘 다 0이면 0
1010 | 1100 = 1110
- XOR(^) 연산
대응하는 bit가 서로 다르면 1, 서로 같으면 0
1010 ^ 1100 = 0110
- NOT(~) 연산
비트 값을 전부 뒤집는 연산
~1010 = 0101
- Shift(«, ») 연산
비트값을 전부 왼쪽(«)으로 혹은 오른쪽(»)으로 주어진 숫자만큼 옮기는 연산
주목할만한건 <<1 or >>1은 주어진 숫자를 *2 or /2 하는것과 같다는 것이다.
1010 >> 2 = 0010
1010 << 2 = 101000
앞으로 우리는 상태 저장을 비트마스크로 하는 문제들을 풀어 볼 것이다. 비트마스크는 이곳저곳에 섞여서 많이 쓰이므로 정확히 개념을 잡고 넘어가는걸 추천드린다.