비트마스크

비트마스크에 대해 araboza.

 

비트와 이진법

컴퓨터들은 내부적으로 이진수를 이용해 모든 자료를 비트(bit)라고 부르는 단위로 표현한다. 한 비트는 0 또는 1의 값만 가질 수 있고, 일반적으로 우리가 화면으로 보는 십진수의 숫자들도 컴퓨터 내부적으로는 이진수로 저장되어 있다. 

직관적으로 이해하는 방법은 비트를 스위치라고 생각하는 것이다. 0이면 꺼져있는 상태고, 1이면 켜져있는 상태인 것이다.

 

                           🕳🕳	모든 스위치가 꺼져있다
                           🕳💡	1번 스위치만 켜져있다
                           💡🕳	2번 스위치만 켜져있다
                           💡💡	모든 스위치가 켜져있다

 

 

 

 

			💡💡🕳🕳💡🕳🕳	7개의 스위치의 100번째 상태

 

 

비트마스크

비트마스크는 bit에 mask를 씌운다는 뜻으로, 정수의 이진수 표현을 자료 구조로 쓰는 기법이다. 쉽게 말하면 숫자를 위의 예시처럼 스위치 상태로 사용하는 것이다. 

예를 들어보자. 4가지 시험이 있고, 이를 모두 통과한 사람을 합격시키려고 한다. 어떻게 이 상태를 표현해야 할까? 가장 먼저 떠오르는 방법은 boolean 배열을 이용하는 것이다.

 

bool passed[4] = {false, false, false, false};

if(passedExam(0))
	passed[0] = true;
if(passedExam(2))
	passed[2] = true;
...

 

이렇게 false로 초기화 된 4개의 boolean 배열을 선언하고, 각 시험을 통과할 때 마다 해당하는 boolean 값을 true로 바꿔준다. 

 

같은 코드를 비트마스크를 사용하면 이렇게 구현할 수 있다.

 

int passed = 0;

if(passedExam(0))
	passed = passed | (1 << 0);
if(passedExam(2))
	passed = passed | (1 << 2);

 

흠... 기괴하다. 우선 처음보는 |과 <<연산이 나왔다고 당황하지 말자. 알고보면 별거 없는 녀석들이다. 지금은 (1 << 0)는 0번째, (1 << 2)는 2번째 스위치를 의미하고 | 연산이 스위치를 킨다고 생각하자.



이 상황에서 모든 시험을 통과했는지 여부를 판단하려면 어떻게 해야 할까?

 

bool allPass = true;
for(int i = 0; i < 4; ++i){
	if(passed[i] == false){
            allPass = false;
            break;
        }
}

 

boolean 배열을 이용한 경우, 위와 같은 반복문으로 모든 시험에 합격했는지 확인할 수 있다.

 

비트마스크를 이용한 코드를 보자

bool allPass = false;
if(passed == (1 << 4) - 1)
	allPass = true;

 

반복문 없이 한번의 비교로 확인이 가능하다!! 어떻게 가능할까?

 

                        🕳🕳🕳🕳	모든 스위치가 꺼져있다
                        💡🕳🕳💡	0, 3번 스위치가 켜져있다
                        💡💡💡💡	모든 스위치가 켜져있다

 

비트마스크의 뜻을 다시 생각해보자. 정수의 이진수 표현을 자로 구조로 사용한다. 우리의 예시에 적용하면 숫자를 스위치의 조합으로 사용하겠다는 뜻이다. 모든 스위치가 꺼져있는 상태는 0으로, 0번 3번 스위치가 켜져있는 상태는 8로, 그리고 4개의 스위치가 다 켜져있는 상태는 15로 표현하는 것이다. 

 

이렇게 비트마스크를 사용하면 숫자 자체가 스위치들의 상태가 되기 때문에 별도의 반복문 없이 바로 상태를(어느 스위치가 켜져있는지) 확인할 수 있다. 4가지 시험을 모두 통과했는지의 여부는 모든 스위치가 켜져있는 상태인지를 뜻하는 15인지만 확인하면 되는 것이다.

 

 

 

비트연산자

이제 비트연산자(bitwise operator)에 대해 알아보자.

 

shift 연산의 비트를 왼쪽이나 오른쪽으로 이동한다는게 무슨 의미인지 와닿지 않을 수도 있기에 예시를 들면 이와 같다.

 

0110에 left shift 연산을 하면 1100이 된다.
0110에 right shift 연산을 하면 0011이 된다.
1100에 left shift 연산을 하면 1000이 된다.
0011에 right shift 연산을 하면 0001이 된다.

 

말 그대로 현재 비트를 한 칸씩 왼쪽이나 오른쪽으로 이동하는 것이다. 그리고 shift 연산으로 버려지는 비트는 0으로 대체되게 된다. 2의 보수 체계에서 음수의 경우 약간 다르지만 이 글에서는 다루지 않겠다.

 

나머지 비트연산의 설명은 아래 예시로 대체하겠다.

 

0000 과 1110 에 OR 연산을 적용하면 1110이 된다.
0110 과 1110 에 OR 연산을 적용하면 1110이 된다.

0000 과 1110 에 AND 연산을 적용하면 0000이 된다.
0110 과 1110 에 AND 연산을 적용하면 0110이 된다. 

0000 과 1110 에 XOR 연산을 적용하면 1110 된다.
0110 과 1110 에 XOR 연산을 적용하면 1000 된다.

0100 에 NOT 연산을 적용하면 1011이 된다.

 

예시

위에서 예시로 사용한 코드를 다시 보자. (1 << 0)이 0번 스위치를 뜻하고 | 연산이 스위치를 킨다고 했다.

if(passedExam(0))
	passed = passed | (1 << 0);
if(passedExam(2))
	passed = passed | (1 << 2);

 

 

8비트 정수를 기준으로, passed 변수가 0011 0100이라고 가정하고 코드를 설명하면 이와 같다.

1 = 0000 0001
(1 << 0) = 0000 0001	// 비트를 0번 왼쪽으로 이동
(1 << 2) = 0000 0100	// 비트를 2번 왼쪽으로 이동

passed | (1 << 0) = 0011 0101		// (0011 0100) | (0000 0001)
passed | (1 << 2) = 0011 0100		// (0011 0100) | (0000 0100)

이렇게 (1 << n) 으로 n번 스위치를 선택하고, | 연산으로 스위치를 켰던 것이다.

 

그래서 왜?

비트연산자로 스위치를 키고 끌 수 있다는 사실은 알았다. 근데 직관적인 boolean을 사용하지 않고 비트연산자를 이용하고 비트마스크 기법을 쓰는 이유가 뭘까?

 

속도

메모리 (중요)

대부분 알고리즘 문제에서 비트마스킹은 어떤 '상태'를 효과적으로 표현하기 위해 사용된다. 위의 예시에서 숫자 15는 4개의 스위치가 켜진 상태, 숫자 2는 우측 기준 2번째 스위치가 켜진 상태가 된다. 이처럼 4개의 스위치를 크기가 4인 bool 배열을 사용하지 않고 숫자 하나로 표현할 수 있게 된다. 

 

 

겉멋

비트연산을 아직 모르는 사람 앞에서 고수인 척 할 수 있다.

응용

외판원 순회 문제는 비트마스킹과 dp로 풀 수 있는 좋은 문제다. 총 16개의 도시가 있고, dp를 적용하기 위해서 도시 방문 상태를 표현할 방법이 필요하다. bool 배열을 사용한다면 16개의 bool 변수와 상태를 확인하기 위해 매번 16개를 다 확인해야 하지만, 비트마스크를 이용하면 숫자 하나로 이 모두를 해결할 수 있다.

 

이런 특징을 가진 문제라면 비트마스크 문제일 가능성이 높다.

• 상태를 표현할 필요
• n의 값이 20 이하
  
  
  

추천 문제

프로그래머스 미로 탈출

백준 12813 이진수 연산
백준 1102 발전소
백준 1480 보석 모으기
백준 1311 할 일 정하기1