비트마스크[BitMask]란?

 

개요

비트마스크(BitMask) 기법에 대해 이해하고 활용할 수 있는 능력을 키운다.

비트마스크는 알고리즘 카테고리에 들어와 있기는 하지만 알고리즘이라기 보다는 일종의 테크닉에 가깝다.

 

1. 비트(Bit) 그리고 비트연산

컴퓨터에서 사용되는 데이터의 최소 단위인 비트(Bit)는 '0과 1'의 값을 가질 수 있다.

이 때, 0은 'false / 꺼져 있음(off)' 그리고 1은 'true / 켜져 있음(on)'를 각각 나타낸다.

1111 1111 = 255

각 비트의 의미를 잘 기억해두고 우선 비트를 조작할 수 있는 비트 연산을 먼저 간단하게 정리해본다.

 

1) AND 연산(&)

논리 연산자인 &&과 마찬가지로 두 비트가 모두 1일 경우 1을 반환한다.

1001 & 1111 = 1001

 

2) OR 연산( | )

논리 연산자인 ||과 마찬가지로 두 비트 중 하나만 1이어도 1을 반환한다.

1001 | 1111 = 1111

 

3) XOR 연산(^)

두 비트가 서로 다르다면 1을 반환한다.

1001 ^ 1111 = 0110

 

4) NOT 연산(~)

비트의 값을 반전시킨다.

~1001 = 0110

 

5) SHIFT 연산(<<, >>)

왼쪽 혹은 오른쪽으로 비트를 원하는만큼 움직인다.

00001001 << 2 = 00100100
00001001 >> 2 = 00000010

쉬프트 연산에서 중요한 점 한가지는 바로 자리수다. 

java의 경우 int 자료형은 -2^31 ~ 2^31-1(-2147483648 ~ 2147483647) 을 범위로 갖는다.

int는 32bit 길이를 갖지만 첫 번째 비트는 부호를 나타내는 부호 있는 정수형이기 때문에 2^31까지만 양 방향으로 표현할 수 있게 되는 것이다. 다시 말해 자료형의 범위를 정확하게 인지하지 않은 상태에서 범위를 넘어서는 쉬프트 연산을 수행할 경우 쓰레기값을 얻을 수 있다.

* java에서는 16bit 자료형인 char가 부호 없는(unsigned) 자료형이므로 이를 bitmask에서 많이 활용한다.

 

비트 연산에서 공통적으로 가장 중요한 것은 바로 연산자 우선순위다. 쉬프트연산을 제외한 일반 비트 연산자(&, |, ^. ~)들은 비교연산자(==, !=)보다 우선 순위가 낮기 때문에 엉뚱한 결과를 얻고 싶지 않다면 괄호로 비트 연산자끼리는 반드시 묶어주는 습관을 들여야한다.(c++도 동일하며 사실 자바는 이미 컴파일 단계에서 잘못됐다는걸 알려쥼 :) )

(6 & 4 == 4) != ((6&4) == 4)

 

2. 비트마스크(BitMask)

앞서 비트에 대해 얘기를 하며 0 과 1은 각각 off / on의 의미를 갖는다고 했다. 이를 조금 연장해서 생각해본다면 특정 구성요소로 이루어진 집합을 표현할 수 있지 않을까?

 

{1, 2, 3, 4, 5, 6, 7, 8} 총 8개의 구성요소로 이루어진 집합이 있다고 가정하자.

구성요소들의 유무를 확인하기 위해 혹은 어떤 구성요소로 이루어져있는지를 확인하기 위해 어떤 자료구조를 사용할 수 있을까.

//1. 구성요소의 idx를 key로, boolean을 value로 갖는 map 객체
HashMap<Integer, Boolean> map = new HashMap<Integer, Boolean>();

//2. boolean 배열에서 idx를 조회
boolean comp[] = new boolean[N];

//3. idx 배열로 1이면 있고 0이면 없음을 나타냄
int comp2[]= new int[N];

 

idx를 안다는 전제 하에 map이든 배열이든 해당 idx를 조회해 유무를 파악해볼 수 있을 것이다.

 

굳이?

 

유무를 파악하고 싶을 뿐인데 불필요하게 메모리를 잡아먹으면서 선언해둘 필요가 있을까.

여기서 3번 구조에 초점을 맞춰보자. 

{1, 2, 4, 5} 구성요소만 존재하는 집합이라 했을 때 3번 구조의 배열은 아래의 형태를 띄고 있을 것이다.

int comp[] = {0, 1, 1, 0, 1, 1, 0, 0, 0};

보인다. 2진수가. 

배열을 오른쪽에서 부터 읽어들인다면 {1, 2, 4, 5}로 구성된 집합은 000110110으로 나타낼 수 있을 것이다.

더 이상 배열이 필요하지 않다. 이진수는 10진수로 바꿔 char나 int형으로 변수를 가지고 있으면 된다.

//int comp[] = {0, 1, 1, 0, 1, 1, 0, 0, 0};
char comp = 54;

 

3. 응용

선언만 하면 의미가 없다. 집합의 각 구성요소들을 조작하는 방법을 익히자.

 

키보드를 커스텀 해서 사고 싶은데 [0, 4]의 번호를 갖는 옵션들이 있다고 가정하자. 키보드를 주문하고자 하는 필자는 자금난과 지름신 사이에서 옵션을 계속 고민하고 있다. 우선 옵션이 없는 키보드를 장바구니에 담아두었다.

int keyboard = 0;

(리얼포스 재고 언제 입고되냐!!!!!!!!!!!!!!!!!!)

 

1) 원소 추가 

- 3번 옵션인 저소음 옵션을 추가하고 싶다.

keyboard |= (1 << 3);
//00000 => 01000

 

2) 원소 읽기

- 2번 옵션인 텐키 유무를 확인하고 싶다.

//텐키 있으면 풀배열, 없으면 텐키리스
String ret = ((keyboard & (1 << 2)) == 0)? "텐키리스" : "풀배열";
//01000 & 00100 = 0
//01000 & 01000 = 01000

 

3) 원소 삭제

- 3번 옵션인 저소음 옵션을 다시 빼고 싶다.

keyboard &= ~(1 << 3)
//01000 & 10111 = 00000

- 4번 옵션인 APC 옵션을 빼고 싶다.

//keyboard -= (1 << 4);
//빼는 연산을 구성요소를 제거하기 위해 사용할 수도 있겠지만,
//이는 기존에 값이 없을 경우에는 쓰레기값을 생성한다.
//아래의 방법을 사용하자.
keyboard &= ~(1 << 4);
//01000 & 01111 = 01000

 

 

4) 원소 변경(Toggle)

- 1번 옵션인 색상을 기존에 선택한것에서 바꾸고 싶다.

keyboard ^= (1 << 1);
//01000 ^ 00010 = 01010

 

 

 

5) 집합 사이즈

- 현재 선택한 옵션이 몇개인지 보고 싶다.

int bitCnt = 0;
while(keyboard != 0) {
  if(keyboard % 2 == 1)
  	bitCnt++;
  keyboard /= 2;
}

- java가 화를 냈다. '내장 메소드를 만들어 놨는데 뭐하러 그러는 거니'

Integer.bitCount(keyboard);

 

4. 정리

비트마스크(BitMask)는 모든 다른 자료구조를 대체한다거나 모든 문제의 해결방안으로 사용될 수는 없다. 하지만 구성요소가 한정되어있는 집합을 구현하기에는 적합할 수 있다. 더 빠른 수행시간과 더 적은 메모리 사용량으로 효율적이고 짧은 코드를 작성할 수 있지만 단점아닌 단점이 있다면 코드가 직관적이지는 않다는 것이다. 특히 메모리사용량이 한정된 문제를 풀이함에 있어서 Map 과 같은 객체를 비트마스크 배열로 대체한다면 많은 시간과 메모리를 절약할 수 있다.

 

---

 

Reference

1. 프로그래밍 대회에서 배우는 알고리즘 문제해결전략 2권_비트마스크_575p_구종만 지음

 

---

 

 

관련문제

1. [Silver 5] 1978번 소수찾기

1978번: 소수 찾기

2. [Silver 5] 11723번 집합

11723번: 집합

3. [Gold 5] 심심한 준규

2892번: 심심한 준규