[알고리즘] 비트마스크

김민기·2021년 2월 15일

알고리즘

목록 보기

2/6

각 정점에 도달했을 때 정점에 접근해야하는 값이 1개가 아닐 경우 각 데이터에 대한 접근을 했는 지 여부를 위해 배열을 사용할 때 점점 많은 차원의 배열이 필요하다. 각 정점에 저장되는 데이터가 26개일 때, 방문여부를 포함해서 27차원의 방문 배열을 선언해야할까?

방문 배열에서 어떤 연산을 했는지 안했는지를 정수형태로 저장하고, 그걸 이진수로 치환해 각각의 자릿수마다 어떤 연산의 인덱스를 할당한다면 위의 문제를 해결할 수 있을 것이다.

그렇다면 정수형태의 값에 방문 여부를 어떻게 2진수로 저장하고 또 불러올 수 있을까? 우리는 비트 연산자로 각 자리수에 접근하고 사용여부를 체크하며 또 체크여부를 확인할 수 있다.

|
- 두 수의 각각 비트 값에 비트 OR 연산한 결과를 반환
- 0b0010 | 0b1011 == 0b1011
&
- 두 수의 각각 비트 값에 비트 AND 연산한 결과를 반환
- 0b0010 & 0b1011 == 0b0010
^
- 두 수의 각각 비트 값에 비트 XOR 연산한 결과를 반환
- XOR( 배타적 논리합) 비트가 같으면 0, 다르면 1
- 0b0010 ^ 0b1011 == 0b1001
~
- 단항연산자로 하나의 수의 각각 비트값을 모두 반전시킨다
- ~0b0010 == 0b1101
<<
- 왼쪽 피연산자의 비트를 오른쪽 피연산자(정수)만큼 이동시킨다
- 2진수의 자리수가 하나 증가하므로 값은 *2가 된다.
- 0b0010 << 2 == 0b1000
>>
- 왼쪽 피연산자의 비트를 왼쪽 피연산자(정수)만큼 이동시킨다
- 2진수의 자리수가 하나 감소하므로 값은 /2 가 된다.
- 0b0010 >> 1 == 0b0001

위에서는 예를 들기 위하여 2진수를 비트연산했지만 16진수나 10진수의 정수값도 마찬가지로 비트연산할 수 있다. 이때 각각의 연산들은 피연산자들을 2진수로 바꾼 값으로 연산하되 반환값은 원하는 정수값으로 받을 수 있다.

자세한 내용은 비트연산자 게시글에 작성해 놓았다

그렇다면 비트연산자를 활용하여 비트 마스킹을 하는 법에 대해 알아보자.

10 & 2
- 10진수 10은 이진수 0b 0000 1010 으로 표현할 수 있으며 10진수 2는 이진수 0b 0000 0010 으로 표현할 수 있다.
- 0b 0000 1010 & 0b 0000 0010 을 연산하면 0b 0000 0010 즉 2로 표현할 수 있으며 이는 1 << 2 와 같다.
10 & 3
- 10진수 10은 이진수 0b 0000 1010 으로 표현할 수 있으며 10진수 1는 이진수 0b 0000 0001 으로 표현할 수 있다.
- 1 << 3 은 0b 0000 0001 << 3 이므로 0b 0000 1000 으로 표현할 수 있다.
- 0b 0000 1010 & 0b 0000 1000 을 연산하면 0b 0000 1000 이며 1 << 3 와 같다.
10 | 2
- 0b 0000 1010 | 0b 0000 0010 == 0b 0000 0010
10 | 1 << 3
- 0b 0000 1010 | (0b 0000 0001 << 3)
- 0b 0000 1010 | 0b 0000 0100 == 0b 0000 1101

위와 같이 비트연산을 진행하면 &, |, << 의 연산에 따라서 비트 값을 제어할 수 있다. 그렇다면 이를 활용해서 비트마스킹은 어떻게 사용할 수 있을까?

각각의 비트 자리를 마치 방문 배열처럼 사용하면 비트 마스킹을 한 정수의 이진수 자릿수를 방문 배열의 인덱스처럼 사용할 수 있다.

이렇게 치환된 마스크 값을 비트 연산을 통해 다음과 같이 제어한다.

boolean[] selected = new boolean[8];
int mask;

int maskingIndex = 5;

selected[maskingIndex] = true;
mask |= 1 << maskingIndex;

| 연산자는 해당 비트에 대해 or 연산을 하므로 1을 넣은 자릿수 외에는 원래의 값이 반환된다. 따라서 원하는 자릿수에 대해서만 변환시킬 수 있다. 그러므로 배열 마스크에서 해당 자리만 체크해주는 결과와 동일하게 동작시킬 수 있다.

if(selected[maskingIndex]){
	//do something..
}
if((mask & 1 << maskingIndex) != 0){
	//do something..
}

& 연산자는 해당 비트가 둘 다 1이면 값을 반환하므로 비트시프트를 이용해서 원하는 자리에 비트 자리가 존재 하는지 여부에 대해 검사할 수 있다. 배열 마스크에 대해서 해당 마스크가 true 인지 false 인지에 대한 조건문과 동일하게 동작시킬 수 있다.

if((mask & 1 << maskingIndex) == 1)
//wrong usage

위와 같은 코드는 원하는 값을 얻을 수 없다. 비트연산의 결과는 해당 자리의 비트에 대해서 0, 1로 반환하므로 결과로 나오는 값은 해당 비트가 0 혹은 1인 값으로 연산된 정수 값이지 0이나 1이 반환되는 것은 아니다.

따라서 위의 코드에 해당하는 수는 maskingIndex 가 1이어서 비트연산에서 첫째 자리의 비트 값을 연산하는 결과만 조건에 해당할 수 있다.

또한 int형으로 비트연산을 할 때 int형의 자릿수는 32비트, 그리고 한 자리는 부호비트이므로 31비트로 제한되어 있으므로 그 이상으로 마스킹 연산을 하게되면 비트 값이 저장되지 않을 수 있다.

민기1