🥽

[JS] Bit Mask(비트 마스크)


비트마스크?

정수의 이진수 표현으로 자료를 표현하는 기법을 '비트마스크'라고 부른다.

예를 들어 그래프에 정점 0, 1, 2, 3 있다고 해보자. 이 그래프를 탐색할 때 DFS로 순회하든, BFS로 순회하든 보통 visited 배열을 둬서 방문한 노드인지 아닌지 확인한다. 정점 0을 방문했다면 배열 [1, 0, 0, 0]로 표현할 수 있다.

이때 배열 대신 비트마스크를 사용할 수도 있다. 비트마스크를 사용하면 정점 0을 방문한 것을 0001로 표현할 수 있다. 23을 추가적으로 방문하게 된다면 1101로 표현할 수 있을 것이다.

그렇다면 이걸 왜 쓰는 걸까?

비트마스크를 사용하면 다음과 같은 장점을 얻을 수 있다.

  • 더 빠른 수행시간: 비트마스크 연산은 O(1)O(1)에 구현되는 것이 많기 때문에 적잘히 사용하면 다른 자료구조를 사용하는 것보다 훨씬 빨리 동작한다. 물론 비트마스크를 사용할 수 있다는 뜻은 원소의 수가 적다는 뜻이지만, 연산을 굉장히 많이 수행해야 할 경우에는 속도를 크게 향상할 수 있다.

  • 더 작은 메모리 사용량: 위의 예시에서 알 수 있듯이, 배열을 사용하면 정수 4개로 방문 상태롤 표현하지만 비트마스크를 사용하면 단 하나의 정수로 표현할 수 있다.

  • 더 간결한 코드: 집합에 대한 연산을 처리할 때 비트마스크를 사용하면 굉장히 짧은 코드로 작성할 수 있다.

경험적으로 봤을 때 비트마스크는 원소의 개수가 적고, 그 원소의 상태(집합에 있는지 없는지, 방문했는지 안했는지)를 저장해야할 때 매우 유용하다고 생각한다.

비트 연산자

비트마스크는 비트 연산자를 사용해 조작한다.

  • AND 연산

두 비트마스크의 각 비트를 비교하면서 해당 비트가 둘 다 켜져 있다면 결과의 비트를 켠다.

1(01)3(11)을 AND 연산하면 1 & 3 = 1(01)을 얻을 수 있다.

  • OR 연산

AND와 비슷하지만, 해당 비트 중 하나라도 켜져 있으면 해당 비트를 켠다.

1 | 3 = 3(11)

  • XOR 연산

이것도 비슷하지만, 해당 비트 중 하나만 켜져 있으면 해당 비트를 켠다.

1 ^ 3 = 2(10)

  • NOT 연산

켜져있는 비트는 끄고, 꺼져있는 비트는 켠다. 즉, 각 비트를 반전시킨다.

!2(10) = 1(01)

  • Shift 연산

비트들을 왼쪽으로 밀거나 오른쪽으로 민다. 움직이고 나서 빈자리는 0으로 채워진다.

3(11) << 1 = 6(110), 3(11) >> 1 = 1(01)

자바스크립에서 비트마스크를 사용할 때 주의해야할 점이 있는데, 바로 비트연산의 피연산자가 32비트 정수로 변환된다는 것이다. 따라서 원소 개수가 32개 보다 많다면 표현할 수 없다.


참조:
https://rebro.kr/63
프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략