비트마스크 (Bitmask) 연산

"프로그래밍 대회에서 배우는 알고리즘 문제해결전략", 16장. 비트마스크 를 읽고 공부한 것을 기반으로 작성하였습니다.

 

우리가 사용하는 컴퓨터의 자료는 모두 2진수를 기반으로 이루어져 있습니다.

컴퓨터가 2진수를 이용한다 함은 보통은 컴퓨터를 사용하는 사람, 즉 우리에게는 큰 상관이 없지만,

프로그램 작성 시 연산 시간과 공간적 효율을 고려한다면 이진수를 직접 다루는 것이 효율적일 것입니다.

이러한 목적으로 이진수 표현을 자료구조로 쓰는 기법을 비트마스크 (bitmask) 라고 합니다.

 

비트마스크 기법은 아래와 같은 이점을 가진다고 합니다:

• 더 빠른 수행 시간. 대부분 O(1) 의 시간복잡도를 가져, 통상적인 다른 자료구조보다 훨씬 빠른 연산속도를 자랑합니다. 다만 비트마스크를 사용하는 경우 원소의 수가 클 수 없다는 단점이 존재합니다.
• 더 간결한 코드. 다양한 집합 연산에 관련된 코드를 간단하게 작성할 수 있어, 코드를 굉장히 짧게 작성할 수 있습니다.
• 더 적은 메모리 사용량. 더 적은 양의 메모리를 사용하여 같은 내용을 표현할 수 있습니다. 즉 더 많은 데이터를 미리 계산해서 저장해 둘 수 있고, 따라서 종합적인 성능 향상에 기여합니다.
• 연관 배열을 배열로 대체. 연관 배열 객체 map<vector<bool>, int> 를 사용한다고 가정하면, 이를 비트마스크를 아용하면 단순한 int[]를 통해 나타낼 수 있습니다. 이 점은 많은 경우 엄청난 시간과 공간의 절약을 가져다 줍니다.

비트 연산자.

우리가 흔히 알고 있는 숫자들을 이진법으로 나타내 봅시다.

 

941 = 11 1010 1101

365 = 01 0110 1101

 

비트 연산자는 위와 같이 비트 단위의 자료를 다룹니다.

• AND: 두 수를 비교합니다. Return 1 if bit A and bit B are both 1; otherwise, return 0. 즉, AND가 의미하는 대로, 두 비트가 모두 1인 경우 1을 반환합니다. 위의 941과 365를 비교한다면, 결과값은 01 0010 1101, 즉 10진수로는 301이 됩니다.
• OR: 두 수를 비교합니다. Return 1 if bit A or B is 1; otherwise, return. 즉, OR가 의미하는 대로, 두 비트 중 하나라도 1인 경우 1을 반환합니다. 위의 941과 365를 비교한다면, 결과값은 11 1110 1101, 즉 10진수로는 1005가 됩니다.
• XOR: 두 수를 비교합니다. Return 1 if bit A or B is exclusively 1; meaning, A and B must be different. Otherwise, return 0. 즉, XOR의 경우 A와 B의 비트가 서로 다를 경우 1을 반환합니다. 위의 941과 365를 비교한다면, 결과값은 10 1100 0000, 즉 704가 됩니다.
• NOT: 정수 하나에 대하여, 켜져 있는 비트는 끄고, 꺼 있는 비트는 켭니다. 941 = 0000 0011 1010 1101 이므로, NOT 연산 후에는 1111 1100 0101 0010, 즉 64954가 됩니다.
• SHIFT: 정수 하나에 대하여, 비트를 왼쪽 혹은 오른쪽으로 n만큼 움직입니다. 941 = 0000 0011 1010 1101 이므로, 왼쪽으로 2만큼 SHIFT 한다면, 0000 1110 1011 0100, 즉 3764가 됩니다.

C++ 에서 사용되는 비트연산자는 아래와 같습니다:

코드	연산
a & b	a와 b에 대하여 AND 연산
a | b	a와 b에 대하여 OR 연산
a ^ b	a와 b에 대하여 XOR 연산
~a	a에 대하여 NOT 연산
a << b	a의 비트를 왼쪽으로 b만큼 시프트
a >> b	a의 비트를 오른쪽으로 b만큼 시프트

 

비트마스크 연산을 이용하는 예로는 집합의 구현, 지수 시간 동적 계획법, 에라토스테네스의 체, 우선순위 큐 등이 있습니다.