Bitmask에 대해 알아보자

  • 13/6/2022
  • 읽는 시간 3분

비트마스크

비트마스크란, 정수의 이진수 표현을 활용한 기법이다. 비트가 가질 수 있는 상태는 0과 1로 이진수로 표현이 된다. 따라서 비트로 알 수 있는 정보는 다음과 같다.

  • 0과 1로 true/false 상태를 갖는다.
  • 이진수를 십진수로 표현 가능하다.

이러한 정보를 활용하는 방법을 봐보자.
예를 들어 집합 {0,1,2,3,4,5 ...}이 있다고 가정한다. 이후 해당 원소가 선택 되었나 안되었나 체크를 하는 방법을 여러가지로 볼 수 있다. 먼저 배열을 통해서 해당 인덱스를 체크할 수 있다.

int array[n] = {1,1,1,1,1,...}; // 0,1,2,3,4
int array2[n] = {0,1,0,1,0,...}; //1,3...

이러하게 만든다면 메모리를 쓸데없이 낭비하게되며, 오버헤드가 증가한다. 따라서 다음과 같이 사용하게 되면 효율적일 수 있다.

{0,1,2,3,4} // 11111
{1,2,3,4} // 11110
{1,2,4} // 10110
{2,4} // 10100
{1} // 00010

부분집합으로 표현하여, index번째 요소가 존재한다면 1, 없다면 0으로 볼 수 있다. 이러한 값을 그대로 10진수로 변환할 수 있다.

{0,1,2,3,4} // 11111 (2^4 * 1) + (2^3 * 1) + (2^2 * 1) + (2^1 * 1) + (2^0 * 1) = 31
{1,2,3,4} // 11110 (2^4 * 1) + (2^3 * 1) + (2^2 * 1) + (2^1 * 1) = 30 
{1,2,4} // 10110 (2^4 * 1) + (2^2 * 1) + (2^1 * 1) = 22
{2,4} // 10100 (2^4 * 1) + (2^2 * 1) = 20
{1} // 00010 (2^1 * 1) = 2

이렇게 부분집합에서 빼고 넣어서 십진수로도 표현 가능할 수 있다. 비트를 제어하기 위해서 비트 연산이 존재한다.

비트 연산

  • &(AND) 연산

1011 & 1100 = 1000 이러한 식과 같이 해당 비트셋에서 대응하는 두 비트가 모두 1일 때 1을 반환하게 된다.

  • |(OR) 연산

1011 | 1100 = 1111 이러한 식과 같이 해당 비트셋에서 대응하는 두 비트 둘 중 하나라도 1일 때 1을 반환하게 된다.

  • ^(NOR) 연산

1011 ^ 1100 = 0111 이러한 식과 같이 해당 비트셋에서 대응하는 두 비트가 서로 다르면 1을 반환하게 된다.

  • ~(NOT) 연산

~1011 = 0100 이러한 식과 같이 비트 값들을 반전하여 반환한다.

  • >>,<<(SHIFT) 연산

001011 << 2 = 101100 이러한 식과 같이 해당 값을 숫자만큼 비트들을 옮긴다. 이때 왼쪽 시프트는 A * 2^B, 오른쪽 시프트는 A / 2^B를 의미한다.

연산

원하는 인덱스의 값을 바꾸고 싶을 때, 어떤 연산을 사용해야 가능한지 보자.

예를 들어 0101 => 1101로 바꾸고 싶은 경우 여러가지 연산이 가능하다. 먼저 0101 | 1000 연산을 통해서 원하는 결과를 만들 수 있다. 또, 0101 | 1 << 3을 통해서도 결과를 만들 수 있다.

  • 0101 | 1000 = 1101
  • 0101 | 1 << 3 = 0101 | 1000 = 1101

추가적으로 ~연산을 통해서 반대의 값을 쉬프트해서 &, | 연산을 할때는 먼저 쉬프트한 뒤 그 값을 NOT 연산 뒤 AND나 OR 연산을 하여 값을 얻어낸다.

마지막으로 연산을 통해서 원하는 인덱스 번째 비트의 값을 알아내는 연산을 봐보자.

Bitset & (1 << idx)

쉬프트 연산을 통해 해당 인덱스만큼 밀고 해당 값과 AND 연산을 통해서 1 혹은 0인지 알아 낼 수 있다.

예시

이러한 테크닉을 비트마스크라고 하며, 여러 문제에 활용될 수 있다. 그 문제 중 대표 문제는 Traveling Salesman Problem으로 외판원 순회 문제이다. 해당 문제를 풀어보며 조금 더 이해를 가져보는 시간을 가져보자.

int dp[MAX][1<<MAX];
int tsp(int cur, int visited) {
	int& ret = dp[cur][visited];
	if(ret != -1)
		return ret;
		
	if(visited == (1<<n)-1) {
		if(arr[cur][0] != 0)
			return arr[cur][0];
		else
			return INF;
	}
	
	ret = INF;
	for (int i=0; i<n; i++) {
		if(arr[cur][i] && !(visited & (1 << i))) {
			int visit = visited | (1 << i);
			ret = min(ret, tsp(i, visit) + arr[cur][i]);
		}
	}
	
	return ret;
}

해당 문제에서 사용한 함수를 가져와봤다. 이런식으로 비트마스크를 사용했다.

https://www.ardanlabs.com/blog/2021/04/using-bitmasks-in-go.html

algorithm bitmask

댓글