비트마스크

2권의 첫 내용은 비트마스크이다.

 

익히 알고 있는 내용이지만 새롭게 알게 된 내용도 있고 하여 정리해 보겠다.

 

우선 비트마스크란, 말 그대로 비트를 가지고 집합과 유사하게 연산하는 것이다.

AND, OR, XOR, NOT, shift 연산 등이 있다.

 

유의 사항

1. C++, java 에서는 &, |, ^, <<, >> 등 비트 연산자가 ==, != 등 비교 연산자보다 우선순위가 낮다. 반면 파이썬의 경우 비트 연산자의 우선순위가 더 높다. 언어마다 우선순위가 다르니 괄호를 통해 확실히 하는 것이 좋다.

2. 자료형이 다른 경우 오버플로우가 발생한다.

예를 들어, long long a, int b 에 대해  a & (1 << b)를 연산하려고 한다. a가 long long 이고, b가 int이므로 b가 32 이상의 수라해도 long long에서 인식할 것 같지만, 1 자체가 int이므로 오버플로우가 발생한다. 그러므로 자료형을 long long으로 변환 후 사용해야 한다. ( a % (1LL << b) )

 

새롭게 알게 된 것

비트마스크를 이용해 bool 배열 (bool 형태의 집합)처럼 사용할 수 있다. 존재하면 해당 비트가 1, 존재하지 않으면 해당 비트가 0 으로 사용하면 된다. 이를 집합 연산과 비교하면 잘 이해할 수 있다.

( 수=집합, 비트=원소 index)

 

1. 꽉찬 집합 구하기

원소가 20개인 집합의 전체 집합을 구하면 다음과 같다.

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

 1<<20 = 2^20 이고 index를 0부터 세어 0,1,2,... ,19번 째 원소가 모두 있으려면 2^20-1을 구하면 된다.

 

2. 원소 추가

어떤 집합에 해당 원소를 넣으려면, 합집합 (OR)를 이용하면 된다. Set이라는 집합(수)에 p라는 원소(비트)를 추가하는 것이다. or 연산이므로 있으면 그냥 비트가 1로 유지되고, 없어도 1로 바뀐다.

int Set |= (1<<p);

 

3. 원소 유무

해당 원소가 집합에 존재하는지 유무를 가릴 수도 있다.

(1<<p)에서 p번째 비트 외에는 전부 0이다. & 연산을 통해 값이 0이면 해당 비트가 없는 것이고, 0이 아니면 해당 비트가 있는 것이다.

if( Set & (1<<p) )
	return true;
else
	return false;

 

4. 원소 삭제

해당 비트를 삭제하는 것 또한 적용할 수 있다. 1<<p 에서 p번째 원소를 제외한 나머지 비트는 0이다. 여기에 not 연산을 하므로 p번째 비트만 0, 나머지는 1이다. 그리고 & 연산을 취하므로, Set이라는 것에서 p번째 비트는 꺼지고, 나머지는 그대로이다.

Set &= ~(1<<p);

 

5. 토글

해당 비트가 켜져있으면 끄고, 꺼져있으면 켜는 것이 토글이다. 이는 다음과 같다.

Set ^= (1<<p);

 

6. 집합처럼 연산

두 수 a, b를 비트의 집합으로 생각하여 연산 할 수 있다.

int added = (a | b); // 합집합
int intersection = (a & b); // 교집합
int removed = (a & ~b); // 차집합 (a-b)
int toggled = (a ^ b); // (a-b) | (b-a) 와 같은 집합, 두 집합 중 하나에만 있는 원소들의 합집합

 

7. 집합 크기 구하기

해당 집합 (수)의 원소 (비트) 수를 구할 수도 있다.

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

 

8. 최하위 비트 구하기

이는 1<< 연산을 통해 직접 구해도 되지만, 다음과 같이 구할 수도 있다.

( 11000 이면 2^3을 구하는 것)

-a 라는 것은 a의 보수이므로, not 연산한 뒤 1을 더한 것이다. 이를 이용하면 최하위 비트 아래로는 모두 1, 나머지는 0이었던 것에서 1을 더하므로, 최하위 비트는 1, 나머지는 0이된다. 그리고 & 연산을 이용해 최하위 비트를 구할 수 있다.

int first = (bits & -bits);

 

9. 최하위 원소 지우기

마찬가지로 최하위 원소를 지울 수도 있다.

bits &= (bits - 1);

 

10. 부분 집합 순회

예를 들어, 2진수 111 이라는 것이 있으면 111 -> 110 -> 101 -> 100 -> ... 이런 식으로 순화하는 것이다.

for( int subset = Set; subset; subset = ((subset-1) & Set) ){
	.....
}

주의해야할 것은 subset이 0일 때 (즉, 공집합)는 탐색하지 않는 것이다.