비트마스킹/Bitmasking을 배워보자

비트마스킹

비트마스크라고도 한다. 비트마스킹에 대한 정의가 없는 것 같은데 비트와 마스크를 따로 보고 생각하면 비트는 우리가 흔히 생각하는 0과 1로 표현하는 2진수이다. 마스크는 기관지인 입과 코를 보호하기 위해 덮는 수단?이라고 생각한다. 다른 방식으로 보면 무언가를 덮는 용도라고 볼 수도 있다. 따라서, 우리가 생각하는 정수형을 bit로 덮어서(마스크의 역할) 표현하는 것을 비트마스크 및 비트마스킹이라고 생각한다.

 

 

왜 사용해야 해?

 

첫 번째, 메모리가 효율적이다.

비트마스크는 x번째가 체크가 되어있는지? 또는 포함이 되어있는지 확인해야할 때 쓰면 메모리적으로 많은 효율을 볼 수 있다고 생각한다. 

 

만약, a0123456789z 이라는 문자열이 있고 a에서 시작하여 z까지 가는데 지나친 0-9까지의 숫자를 모두 출력하라는 문제가 있다. 문자열을 0부터 시작하여 돌면서 그냥 출력할 수도 있지만 list에 담아서 출력한다고 가정해보자. 이때, 드는 메모리는 int형인 4byte가 총 10개로 40byte가 사용된다. 해당 문제를 비트마스킹으로 사용하면 int형 1개인 4byte로 표현할 수 있다.

 

이처럼 이렇게 간단한 문제에서도 4byte와 40byte를 사용하는 것에서 차이를 얻을 수 있다. 큰 프로젝트라면 상상할 수 없는 차이를 낼 수 있을 것이다.

 

 

두 번째, 연산이 빠르다.

앞서 문제를 조금만 바꿔서 예시를 들어보자. a부터 z안에 0-9까지의 숫자가 적힌 문자열이 아래와 같이 여러개가 있다. 이때, 0-9중 2개의 숫자를 골라서 아래 문자열 중 값을 모두 표현할 수 있는 문자열의 개수를 출력하라는 문제가 있다고 가정해보자.

a4398z
a23z
a32z
a22z

그렇다면 문자열에 있는 숫자인 2,3,4,8,9 중에서 2개의 모든 조합으로 표현할 수 있는 문자열을 확인하고 그 중 최대값을 출력하면 될 것이다. 이때, 2개의 조합을 HashSet에 넣어 확인한다고 가정하자. 2,3부터 첫번째 문자열에서 4를 확인하고 3을 확인하고 9를 확인하고 8을 확인하여 첫번째 문자열에서 4번을 확인한다. 2개의 조합으로 4개의 문자열을 확인하면 총 10번을 확인해야 한다. 이것을 2,3,4,8,9에서 2개의 모든 조합을 확인한다고 하면 20번이고 여기서 10번을 곱하면 200번이 될 것이다. 하지만, 여기서 비트마스킹을 사용한다면 문자열 별로 1번씩만 확인하면 된다. 2개의 조합으로 문자열의 개수인 4번 여기서 20번을 곱하면 결과적으로 총 80번을 확인하면 된다. 해당 문제에서 200번과 80번의 차이가 발생한다. 이는 문자열에 숫자의 조합이 많으면 많을 수록 비트마스킹의 효과가 극대화될 것이다. 

 

이처럼 문제에 따라서 더 빠른 연산을 얻을 수도 있다.

 

 

그렇다면, 사용하지 말아야할 이유는 없을까?

 

첫 번째, 연산이 느리다.

의아할 수 있다. 앞서 사용해야하는 이유 중 하나가 연산이 빠르다고 했기 때문이다. 하지만, 문제에 따라서 연산이 더 느려질 수도 있다는 것을 인지해야 한다. 즉, 문제에 따라서 비트마스킹은 장점이 될 수도 단점이 될 수도 있다. 그렇기때문에 잘 이해하고 사용해야 한다. 

 

앞서 말한 사용해야할 이유의 첫 번째 예시를 생각해보자. a0123456789z 이라는 문자열이 있고 a에서 시작하여 z까지 가는데 지나친 0-9까지의 숫자를 모두 출력하라는 문제였다. 여기서 비트마스킹을 사용하면 출력 하기 전 if문을 한번 거쳐야 하고 0-9까지 모든 수를 확인해야한다. 하지만, list를 사용하는 경우 if문을 거치지 않고 0-9까지 모든 수를 확인할 필요도 없이 list에 있는 값들만 출력하면 된다. 물론, 값이 겹치지 않다는 가정하의 얘기이다. 이처럼 문제에 따라서 이점을 얻을 수 있다는 것을 생각하자.

 

두 번째, 표현값 제한이 있다. 

표현할 수 있는 가장 큰값은 32bit로 0111 1111 1111 1111 1111 1111 1111 1111(2) = 2147483647이다. 따라서 총 31개의 값까지만 체크할 수 있다고 생각하면 된다. 

 

 

어떻게 사용할까?

일단, 연산자에 대한 이해가 있어야 한다. &(and), |(or), ^(xor), ~(not), <<>>(shift)

 

예시를 들어보자. 아래와 같이 a,b 2개의 2진수가 있다.

a - 1010
b - 1100

a&b -> 1000

a|b -> 1110

a^b -> 1001

~a -> 0101

a<<1 -> 0100

 

아래는 비트를 통하여 문제를 해결해나갈 때 알아두면 좋은 방법들을 잘 정리하였길래 가져왔다. 참고하면 좋을 것 같다. 

 

 

비트마스킹 문제

위의 정리한 내용들은 아래 비트마스킹의 여러 문제들을 풀어보며 느낀점들이다. 아래 문제들을 추가할테니 풀어보고 싶다면 풀어보길 바란다.

• https://www.acmicpc.net/problem/1062
• https://www.acmicpc.net/problem/2098
• https://www.acmicpc.net/problem/1194

 

참고 문서

• https://rebro.kr/63