비트마스크

비트마스크
->집합의 요소들을 비트로 표현하는 방법. 특정알고리즘이라기보다는 기법,테크닉을 의미한다.

예를들어  {1,2,3,4,5} 의 집합이 있다면 부분집합은 다음과같다

int[] array1 = {1,2}
int[] array2 = {1,2,4}............... 등등

물론 배열로 표현할수는 있다.
하지만 그러면 메모리를 많이 잡아먹게된다.
집합의 개수가 n개라 가정하면, 부분집합의 개수는 2^n 개이다. (자기자신 포함)
n이 '10'만되도 이미 2^10인 1024개이다.

하지만 저걸 bit로 표현해보자.
{1,2,3,4,5} 의 부분집합 {1,2}는 아래와 같이 표현할 수 있다.
11000

{1,2,4}
1,1,0,1,0

이 2진수들을 10진수로 바꿔서 보관하면,
고작 int형 하나로 하나의 부분집합을 표현할 수 있게된다.

C++에서 비트를 다루는 자료형으로 bitset이란것을 제공한다. (#include <bitset>)

간단한 예제는 다음과 같다.

    bitset<8> temp(0x5); // 정수5를 총 8개의 bit로 표현.

    cout << temp[0];
    cout << temp[1];
    cout << temp[2];
    cout << temp[3];


그냥 cout << temp 할 경우, 0000 0101이 나온다. 
실제 이진수처럼 오른쪽끝에서부터 출력.
출력만 저렇게하는거고, cout << temp[0] 하면은 0이 아니라 1이 출력된다.
실제 0번째 인덱스부터 저장되는 값은 작은 이진수부터,즉 맨 오른쪽부터 출력된다는것.

 

bitset.count()   // 1인비트수 리턴

bitset.all()        // 모든 비트가 1이면 return true; 

bitset.any()      // 1인 비트가 하나라도 있으면 retrun true;

bitset.none()    // 1인비트가 한개도 없으면 return true;

bitset.set(int index)  // index번째의 비트를 1로 변경

bitset.rest(int index) // index번째의 비트를 0으로 변경.

bitset.test(int index) // index번째의 비트가 켜져있으면(1이면) return true;

---------------------------------------------
특정 비트를 키려면 OR연산(|)을 이용한다.
(하나라도 1이면 1을 리턴하는 특징을 이용)

option4 = 0000 1000

myflags == 0000 0000

option4 | myflags

=> 0000 1000    //

특정비트가 켜져있는지 체크하려면 AND연산을 이용.
1인 경우에만 1을 리턴하기 때문.

특정비트를 끄려면 AND연산자(&)와 NOT연산자(~)을 이용.

ex) 

myflags ==   0000 1011 // 현재 내 상태

option4 ==  0000 1000  // 끄려는 옵션

myflags &= ~option4 // 특정비트만 꺼버리기.

 

~option4 == 1111 0111

myflags ==   0000 1011    // 이거 두개 &연산

 

-> 0000 0011 // 깔끔하게 옵션만 끄기 성공.

 

두개의 옵션을 동시에 끄려면 아래처럼 표현하면 된다.

myflags &= ~(option4 | option5);

 

 

토글은 XOR연산자(^)를 사용하면 된다.

myflags ^= option4;

myflags ^= (option4 | option5);

해당 연산의 의미는 특정bit가 꺼져있으면(0이면) 키고, 켜져있으면 꺼버리겠다는 의미.