Kang Sang Woo

It is incomplete..

[알고리즘 설계] 비트 마스크(Bitmask)

비트 마스크란?

내부적으로 이진수를 사용하는 컴퓨터들은 이진법 관련 연산을 빠르게 수행할 수 있다.

정수의 이진수 표현을 자료구조로 쓰는 기법을 비트마스크라고 한다.

비트마스크 장점

빠른 수행시간, 간결한 코드, 적은 메모리 사용량

비트 연산자

1.AND 연산자

AND 연산은 입력받은 두 정수를 한 비트씩 비교하면서, 두 정수에 해당 비트가 모두 켜져 있을 때만 결과의 비트를 켠다.

a & b

2. OR 연산자

OR 연산은 입력 받은 두 정수를 한 비트씩 비교하면서, 두 비트 중 하나라도 켜져 있을 경우 결과의 비트를 킨다.

a | b

3. XOR 연산자

XOR 연산은 입력 받은 두 정수를 한 비트씩 비교하면서, 하나는 켜져 있고, 하나는 꺼져 있을 경우 결과의 비트를 킨다.

a ^ b

4. NOT 연산자

정수 하나를 입력 받아 켜져 있는 비트는 끄고, 꺼져 있는 비트는 켠 결과를 반환한다.

~a

5. 시프트 연산자

정수 a의 비트들을 왼쪽 또는 오른쪽으로 원하는 만큼 움직인다. 어떤 수에 대해 왼쪽으로 2비트 시프트 연산을 하면, 모든 비트들이 왼쪽으로 두 칸 움직이고, 오른쪽 끝 두개의 비트들은 0으로 채워진다.

a << b

반대로, 오른쪽으로 2비트 시프트 연산을 하면, 모든 비트들이 오른쪽으로 두 칸 움직이고, 왼쪽 끝 두개의 비트들은 0으로 채워진다.

a >> b

비트 연산자를 사용할 때 주의 사항

c++이나 자바에서, &,|,^ 등의 비트 연산자의 우선순위는 == 혹은 != 등의 비교 연산자보다 낮다. 즉, 비트 연산자를 사용할 때는 가능한 괄호를 추가하는 것을 추천한다.

두 번째로, 64비트 정수를 비트마스크로 사용할 때 발생하는 오버 플로우를 조심해야 한다.

cout << (1 << b) << endl;

이런 상황에서 1은 부호 있는 32비트 상수로 취급된다. 즉 b가 32 이상이면, 1 « b 에서 오버 플로우가 발생한다.

이런 경우를 위해서 1 뒤에 이 상수가 부호 없는 64비트 정수임을 나타내는 접미사 ull을 붙혀야 한다.

세 번째로, 부호 있는 정수형의 사용에 조심해야 한다. 부호 있는 정수형에서 최상위 비트가 켜진 숫자는 음수를 표현한다. 32비트 정수형에서 하위 20비트만 사용하는 등의 경우엔 문제가 없지만, 32비트를 전부 사용하려면 버그가 발생할 수 있다.

번수의 모든 비트를 다 쓰고 싶을 때는 부호 없는 정수형을 쓰는 것이 좋다.

비트 마스크를 이용한 집합의 구현

이 부분에 대해서는 스스로 생각해보고 작성해보고 이해하는 것이 중요하다

N비트 정수 변수는 0부터 N-1까지의 정수 원소를 가질 수 있는 집합이 된다.

원소 i가 집합에 속해 있는지 여부는 2^i(2의 i승)을 나타내는 비트가 켜져 있는지 여부로 나타낸다.

예를 들어, {1,4,5,6,7,9}를 표현하는 정수는 10 1111 0010 임을 알 수 있다.

아래는 0~19까지의 번호를 갖는 집합을 표현하는 것으로 간주하고 코드를 작성하겠다.

1. 공집합과 꽉 찬 집합 구하기

int set = 0; // 공집합인 경우

set = (1<<20)-1; //꽉찬 집합

2. 원소 추가

9번 원소를 추가한다고 하자.

set |= (1<<9);

3. 원소의 포함 여부 확인

p번 원소가 포함되어 있는지 확인하는 방법

if(set & (1<<p)){
    cout <<"포함되어 있다" <<endl;
}

4. 원소의 삭제

원소가 이미 존재하는 것을 보장할 수 있을때는 아래와 같은 코드를 사용하여도 된다.

set -= (1<<p);

하지만 이 번호의 원소가 존재하는 지 모를 경우 위와 같이 코딩을 하면 큰 오류가 발생할 수 있다.

원소가 존재하는지 안하는지 모를 때, 삭제하기 좋은 코드는 아래와 같다.

set &= ~(1<<p);

5. 원소의 토글

해당 비트가 켜져 있다면 끄고, 꺼져 있다면 키는 것. XOR 연산이 토글 역할을 한다.

set ^= (1<<p);

6. 두 집합에 대한 연산

//a와 b의 합집합
int added = (a|b);

//a와 b의 교집합
int intersection = (a & b);

//a와 b를 뺀 차집합
int removed = (a & ~b);

//a와 b중 하나에만 포함된 원소들의 집합
int toggled = (a^b);

7. 집합의 크기 구하기

집합의 크기를 구하는 방법은 그저 각 비트를 순회하면서 켜져 있는 비트의 수를 세는 방법이다.

int bitCnt(int x){
    if(x==0) return 0;
    return x%2 + bitCnt(x/2);
}

다만 집합의 크기를 구하는 내장 명령어가 존재한다.

  • gcc/g++ : __builtin_popcount(set);
  • Visual C++ : “ __popcnt(set);
  • Java : Integer.bitCount(set);

8. 최소 원소 찾기

집합에서 1이 처음 나오는 곳의 위치를 찾는 방법.

int first = (set & -set);
//-set 은 2의보수를 취한 값

9. 최소 원소 지우기

최소 원소가 무엇인가와 상관 없이 최소 원소를 지우는 연산

set &= (set -1);

10. 모든 부분 집합 순회하기

for(int subset = set; subset; subset((subset-1)&set)){
    //subset 은 set의 부분집합
}

위의 코드는 subset이 0일 때 종료되므로 공집합은 체크하지 않는다는 점을 생각해야 한다.

직접 set비트열을 나열해 두고, 해보는 것을 추천한다. 모든 부분집합을 순회할 수 있는 것을 알 수 있다.

에라토스테네스의 체 Bitmask로 구하기

기존의 에라토스테네스의 체 방식은 수행 범위를 늘릴 때 부담이 되는 것은 수행시간 보다는 메모리 였다.

비트 마스크를 통해서 구현하면, char형 배열 한 칸에 8개의 숫자를 표현할 수 있는 8비트의 메모리가 있으므로 기존 방식에서 1/8만큼의 메모리를 줄일 수 있게 된다.

해당 수의 비트 번호가 1일 경우 소수, 아닐 경우 소수가 아니라고 판단하는 방식으로 진행된다.

int n;
unsigned char sieve[(MAX_N + 7)/8];

//소수인지 판별한다.
bool isPrime(int k){
	return sieve[k>>3] & (1<<(k&7));
	//sieve[k>>3] == sieve[k/8];
	// & ( 1<<(k&7) 을 통한 연산은 직접 해보며 이해하기.
}

//k가 소수가 아니라고 표시한다. 
//해당 수의 비트를 0으로 바꿔준다.
void setComposite(int k){
	sieve[k>>3] &= ~(1 <<(k&7));
}

void eratosthenes(){
	memset(sieve, 255, sizeof(sieve));
	setComposite(0);
	setComposite(1); //0과 1은 소수가 아니라고 미리 설정.
	int sqrtn = int(sqrt(n));
	for(int i=2; i<=sqrtn; i++){
		if(isPrime(i)){
			//이 수가 아직 지워지지 않았다면,,
			//i*i 미만의 배수는 이미 지워졌지만, 이해를 위해 아래 코드는 i*2로 한다.
			for(int j=i*2; j<=n; j+=i){
				setComposite(j); //배수들을 지워준다.
			}
		}
	}
}

댓글남기기

참고