[Algorithm] 비트마스크 (BitMask)

비트(Bit)란?

컴퓨터에서 사용되는 데이터의 최소 단위 (0과 1)

2진법을 생각하면 편하다.

우리가 흔히 사용하는 10진수를 2진수로 바꾸면?

9(10진수) → 1001(2진수)

 

비트마스크 (BitMask)

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

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

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

 

왜 비트마스크를 사용하는가?

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

• 더 빠른 수행시간: 비트마스크 연산은 O(1)에 구현되는 것이 많기 때문에 적잘히 사용하면 다른 자료구조를 사용하는 것보다 훨씬 빨리 동작한다. 물론 비트마스크를 사용할 수 있다는 뜻은 원소의 수가 적다는 뜻이지만, 연산을 굉장히 많이 수행해야 할 경우에는 속도를 크게 향상할 수 있다.
• 더 작은 메모리 사용량: 위의 예시에서 알 수 있듯이, 배열을 사용하면 정수 4개로 방문 상태를 표현하지만, 비트마스크를 사용하면 단 하나의 정수로 표현할 수 있다. (But, 원소의 수가 많지 않아야 함)
• 더 간결한 코드: 집합에 대한 연산을 처리할 때 비트마스크를 사용하면 굉장히 짧은 코드로 작성할 수 있다.

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

 

비트마스킹 활용해보기

0과 1로, flag 활용하기

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

여기서 임의로 몇 개를 골라 뽑아서 확인을 해야하는 상황이 주어졌다. (즉, 부분집합을 의미)

{1}, {2} , ... , {1,2} , ... , {1,2,5} , ... , {1,2,3,4,5}

물론, 간단히 for문 돌려가며 배열에 저장하며 경우의 수를 구할 순 있다.

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

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

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

이러한 2진수는 다시 10진수로 변환도 가능하다.

11111은 10진수로 31이므로, 부분집합을 정수를 통해 나타내는 것이 가능하다는 것을 알 수 있다.

31은 [1,2,3,4,5] 전체에 해당하는 부분집합에 해당한다는 의미!

이로써, 해당 부분집합에 i를 추가하고 싶을때 i번째 비트를 1로만 바꿔주면 표현이 가능해졌다.

이런 행위는 비트 연산을 통해 제어가 가능하다.

 

비트 연산자

AND, OR, XOR, NOT, SHIFT

• AND(&) : 대응하는 두 비트가 모두 1일 때, 1 반환
  • 두 비트마스크의 각 비트를 비교하면서 해당 비트가 둘 다 켜져 있다면 결과의 비트를 켠다.
  • 1(01)과 3(11)을 AND 연산하면 1 & 3 = 1(01)을 얻을 수 있다.
• OR(|) : 대응하는 두 비트 중 모두 1이거나 하나라도 1일때, 1 반환
  • AND와 비슷하지만, 해당 비트 중 하나라도 켜져 있으면 해당 비트를 켠다.
  • 1 | 3 = 3(11)
• XOR(^) : 대응하는 두 비트가 서로 다를 때, 1 반환
  • 이것도 비슷하지만, 해당 비트 중 하나만 켜져 있으면 해당 비트를 켠다.
  • 1 ^ 3 = 2(10)
• NOT(~) : 비트 값 반전하여 반환
  • 켜져있는 비트는 끄고, 꺼져있는 비트는 켠다. 즉, 각 비트를 반전시킨다.
  • !2(10) = 1(01)
• SHIFT(>>, <<) : 왼쪽 혹은 오른쪽으로 비트 옮겨 반환
  • 비트들을 왼쪽으로 밀거나 오른쪽으로 민다. 움직이고 나서 빈자리는 0으로 채워진다.
  • 3(11) << 1 = 6(110), 3(11) >> 1 = 1(01)
  • 왼쪽 시프트 : A * 2^B
  • 오른쪽 시프트 : A / 2^B

  • [왼  쪽] 0001 → 0010 → 0100 → 1000 : 1 → 2 → 4 → 8
    [오른쪽] 1000 → 0100 → 0010 → 0001 : 8 → 4 → 2 → 1
    

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

 

1. 삽입

현재 이진수로 10101로 표현되고 있을 때, i번째 비트 값을 1로 변경하려고 한다.

i = 3일 때 변경 후에는 11101이 나와야 한다. 이때는 OR연산을 활용한다.

10101 | 1 << 3

1 << 3은 1000이므로 10101 | 01000이 되어 11101을 만들 수 있다.

 

2. 삭제

반대로 0으로 변경하려면, AND연산과 NOT 연산을 활용한다.

11101 & ~1 << 3

~1 << 3은 10111이므로, 11101 & 10111이 되어 10101을 만들 수 있다.

 

3. 조회

i번째 비트가 무슨 값인지 알려면, AND연산을 활용한다.

10101 & 1 << i

3번째 비트 값 : 10101 & (1 << 3) = 10101 & 01000 → 0
4번째 비트 값 : 10101 & (1 << 4) = 10101 & 10000 → 10000

이처럼 결과값이 0이 나왔을 때는 i번째 비트 값이 0인 것을 파악할 수 있다. (반대로 0이 아니면 무조건 1인 것)

이러한 방법을 활용하여 문제를 해결하는 것이 비트마스크다.