bit masking (비트마스킹 정리)

비트마스킹의 개념을 알아두면 

값 하나에 여러가지 상태를 표시하는 기법을 알 수 있게 된다.

비트마스킹을 이용한 대표적인 문제가 외판원 순회(TSP) 인 것 같다.

 

예를 들어 집이 4개가 있고, 집 번호를 0~3, 이 집들을 방문한 정보들을 알고 싶다고 할 때,

우리는 비트마스킹 즉, 비트라는 값을 이용해서 하나의 값으로 여러 상태를 표현할 수 있다.

우선 집이 4개 => 4개의 집에 대한 정보를 표현하기 위한 크기가 필요하다.

이를 4비트(2^4 = 16(0~15))로 표현해보자

이 때, 4비트에 대한 비트 표현법은 1<<4 (2^4) 가 된다.

 

만약 0번 집만 방문했다면 0001 (실제로는 1이 저장된다)

만약 1번 집만 방문했다면 0010 (실제로는 2가 저장된다)

만약 1, 3번 집만 방문했다면 1010 (실제로는 2^1+2^3 => 10이 저장된다)

 

여기서 비트1은 방문을 했고 비트0은 방문을 하지 않았음을 나타낸다.

 

비트마스킹 정보를 배열에 저장한다고 가정하면 array[1<<4] 와 같이 선언하여 사용하면 된다.

 

----------- 연산 -------------

 

어떤식으로 사용되는지 알았다면, 이용할 수 있는 연산이 뭐가 있는지 알아보자

 

기본적인 비트연산은 알고 있을 것이다.

&연산의 의미는 두 비트값 모두 1이면 1, 아니면 0을 반환하고

| 연산의 의미는 둘중 한 값이라도 1이면 1, 아니면 0을 반환하고

~연산의 의미는 모든비트를 뒤집는 연산 0->1, 1->0 을 반환하게 된다.

 

비트의 크기는 N, 현재 비트값을 current 라고 할 때

 

. 모든 비트가 1인지 확인해보고 싶다 => current & (1<<N)-1 

 

. 모든 비트가 0인지 확인해보고 싶다 => current & 0

 

. K번째 비트가 1인지 0인지 확인해보고 싶다 => current & (1<<K)

K번째 비트만 둔채로 나머지 비트는 다 버려야 된다

이때 1<<K 의 의미는 K번째 비트만 1 처리하고 나머지 비트는 0 처리한다는 뜻이다.

(만약 K가 4라면 1<<4 => 16이 되고, 이를 비트로 나타내면 10000 (= 16) 가 된다는 뜻이다.

N이 4보다 큰 값이라고 할 때 좀더 정확히는 ...0000...0010000 이라는 의미가 된다)

 

. K번째 비트를 1로 만들고 싶다 => current | (1<<K)

위의 설명을 이해했다면 | (OR) 연산자를 사용해야 함을 알 수 있을 것이다.

K번째 비트를 1로 만들고 싶다면 K번째 비트를 1로 만들고 나머지 비트는 current 값 그대로 가져오면 된다.

 

. K번째 비트를 0으로 만들고 싶다 => current & ~(1<<K)

K번째 비트를 1로 만든 후, NOT연산 ~을 이용하여 뒤집어버리면

K번째 비트만 0이 되고 나머지는 1이 된다.

& 연산을 하면 K번째 비트는 강제로 0이 될 것이고, 나머지 비트들은 원래 값을 가지게 된다.