[종만북] 비트마스크(Bitmask)

비트마스크란 이진수 표현을 자료구조로 쓰는 기법입니다.

 

비트 연산자로는

AND OR XOR NOT SHIFT등이 있습니다.

 

 

AND

a&b

AND	1	0
1	1	0
0	0	1

 

 

OR

a|b

OR	1	0
1	1	1
0	1	0

 

XOR

a^b

XOR	1	0
1	0	1
0	1	0

 

NOT

~a

NOT
1	0
0	1

 

 

SHIFT

a<<b

a를 b만큼 왼쪽으로 shift

a*=2^b

a>>b

a를 b만큼 오른쪽으로 shift

a/=2^b

 

 

유의할점

&,|,^ 등의 연산자는 ==또는 !=같은 비교연산자보다 우선순위가 낮습니다. 따라서 괄호를 치는것이 중요합니다.

 

64비트 정수를 비트마스크로 사용할 때 오버플로가 발생할 수 있습니다.

예를들어

bool isBitSet(unsigned long long a,int b){
	return (a&(1<<b))>0);  //1은 부호가 있는 32bit 상수로 취급하므로 b가 32보다 크면 오버플로발생
}
//따라서 1 뒤에 부호 없는 64비트 정수임을 알려주는 접미사 ull을 붙여야 함.

 

비트마스크로 주로 집합을 표현합니다.

피자집에 토핑이 0부터 19번까지 있다고 할때, 토핑을 넣거나 넣지않는것을 1과 0비트로 표현하기로 합시다.

공집합은 0으로 표현합니다.

 

모든 토핑을 올린 피자는

int fullPizza=(1<<20)-1;

1<<20은 1뒤에 20개의 0이 있는 수입니다. 따라서 1을 빼면 20개의 1이 있습니다.

 

집합에 원소를 추가할 때는 OR연산을 사용합니다.

OR	1	0
1	1	1
0	1	0

이미 있을때(1) 추가하면 그대로(1), 없을때(0)추가하면 추가(1)

p번 토핑을 추가할 때, 

topping|=(1<<p)

1<<p는 p번 비트만 켜져있습니다. 따라서 topping과 1<<p를 OR연산하면 p번 비트는 1이 됩니다.

 

그렇게 올린 원소가 잘 있는지 확인할 때는 AND연산을 사용합니다.

bool isPthTopping(int p){
	if(toppings&(1<<p)) //&연산의 결과값은 0 or 1<<p 입니다. 1이나 true를 반환하지 않습니다.
    	return true;
    return false;
}

/**잘못된 코드
if(toppings&(1<<p)==1) return true;
**/

원소를 삭제할때는 NOT연산자와 AND 연산자를 사용합니다

toppings &= ~(1<<p);

~(1<<p)는 p번 연산자 빼고 모두 켜져있는 상태입니다. 따라서 topping과 and연산을 수행하면 p번 연산자는 꺼지게 됩니다. 나머지는 그대로입니다.

 

원소를 토글할때는 XOR연산을 사용합니다. 토글이란 켜져있으면 끄고, 꺼져있으면 켜는 연산입니다.

toppings^=(1<<p)

 

 

두집합에대한 연산

합집합(a+b)

a|b

교집합(a*b)

a&b

차집합(a-b)

a&~b

합집합-교집합((a-b)+(b-a))

a^b

 

집합에 포함된 원소의 수를 세는법은 각 비트를 순회하는 방법밖에 없습니다. 

아래 예시는 재귀를 사용했습니다.

int bitcount(int x){
	if(x==0)return 0; //기저 bitCount(0)일때 0을 반환합니다 
    return x%2 + bitCount(x>>1); //현재비트 0or1을 판단하고 left 1 shift
}

다만 Visual C++에서 집합의 크기를 구하는 명령어가 존재합니다.

__popcnt(toppings)

 

 

최소의 원소를지울때는 AND연산자를 이용합니다.

toppings&=(toppings -1)

 

모든 부분집합을 순회하는 방법

for(int subset=pizza; subset; subset=((subset-1)&pizza)){
  //모든 부분집합을 순회할 수 있습니다.
}

 

 

 

예제

 

에라토스테네스의 체

에라토스테네스의 체를 구현할 때에는 각 정수가 지워졌는지 그 여부를 저장해야하는데, 메모리가 부담이 될 수있습니다. 따라서 비트마스킹을 사용하면 메모리 사용량을 1/8로 줄일 수 있습니다.

 

MAX_N개의 원소를 가지는 boolean배열을 다음 배열로 바꿉니다.

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

 8(2^3)로 나누는 것은 3만큼 right shift 하는 것과 같고 , 7과 AND연산 하는것은 module 8과 같습니다.

 

따라서 에라토스테네스의 체를 비트마스킹을 이용해 구현하면 다음과 같습니다.

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

inline bool isPrime(int k){ //k가 소수인가?
	return seive[k>>3] & (1<<(k&7));
}

inline void setComposite(int k){ //k는 소수가 아닙니다
	sieve[k>>3] &= ~(1<<(k&7));
}

void eratosthenes(){
	memset(sieve,255,sizeof(sieve));
    setComPosite(0);
    setComPosite(1);
    int  sqrtn=int(sqrt(n));
    for(int i=2;i<=sqrtn; ++i){
    	if(isPrime(i))
        for(int j=i*i;j<=n;j+=i)
        	setComposite(j);
    }
}