비트마스크(Bitmask)

- 비트마스크는 말 그대로 어떠한 수의 비트에 0이나 1같은 마스크를 씌우는 것인데요.

초기화된 수를 2진수의 비트열로 생각하여 비트추가,제거,토글같은 연산을 처리할수 있습니다.

 

- 문법은 다음과 같습니다.

//cf.비교연산자가 비트마스크보다 우선순위 높다.
//cf. 1<<p 와 같은 꼴의 경우, 크기가 1인 집합으로 볼 수 있다.
 
 
// p번째 위치로 1을 옮긴다. p가 0일 경우는 0번째 비트로 옮긴다.
1<<p; 
 
// 2진수 a의 비트열에서 p번째 비트를 1로 켠다. (이미 켜져 있을경우 1로 유지)
a= a | 1<<p; 
 
// a의 비트열에서 p번째 비트가 1 인지 확인한다.
// if문으로 활용할수도 있는데, true일 경우 1<<p값이 반환되며 false경우 0이 반환된다!
a= a & 1<<p;
if(a&(1<<p)) { cout<<"switch on p"<<endl; }
 
// p번째 비트를 현재비트와 반대로 바꾼다.
a= a^1<<p;
 
// p번째 비트를 0으로 바꾼다.
a= a & ~1<<p;
a= a - 1<<p; //코드로도 지울수는 있다! 다만, p번째 원래 0이였다면 정상적으로 동작하지 않는다.

 

- 1보다 크기가 큰 집합의 비트들을 가지고도 동일하게 문법을 적용할 수 있습니다.

int Or=(a | b); //a+b의 합집합
int And=(a & b); //a와 b의 교집합
int Not=(a & ~b); //a-b 차집합
int Xor=(a ^ b); //a와 b중 하나에만 포함된 원소의 집합

 

- 또한 32비트 변수에 1<<p(p>=32)의 연산을 취할경우 오버플로우가 발생할 수 있습니다.

이때 이 상수가 부호없는 64비트로 바꿔주면 한계적으로라도 문제를 해결할 수 있습니다. (1ull<<p)

 

 

- 정리하고자 피자에 20가지(0~19번째 비트) 토핑메뉴를 통해 피자의 종류를 구분지어보는 예제코드를 보이겠습니다.

#include <cstdio>
#include <iostream>
using namespace std;
 
int main() 
{
    //cf. 1<<a 는 a번째 비트까지 1을 shift
    int allPizza = (1 << 20) - 1;// 0~19번째 토핑목록을 1으로
    int zeroPizza = ~allPizza;//0~19번째 0으로
    
    //페퍼로니p는 19번째 토핑목록
    int p = 19; 
 
    //cf. |연산을 통해 or연산 실행
    //제로피자에서 p위치의 비트를 켜면 페퍼로니피자!
    int pPizza = zeroPizza | (1 << p);
 
    //cf. &연산을 통해 and연산 실행
    //페퍼로니피자에 페퍼로니가 들어있는지 확인
    if (pPizza&(1 << p)) cout << "페퍼로니 피자!" << '\n';
    else cout << "치즈 피자!" << '\n';
    
    //cf. ~연산을 통해 not연산 실행
    //페퍼로니피자에서 페퍼로니토핑을 빼려면?
    pPizza &= ~(1 << p);
    if (pPizza&(1 << p)) cout << "페퍼로니 피자!" << '\n';
    else cout << "치즈 피자!" << '\n';
 
    //cf. ^연산을 통해 xor연산 실행
    //다시 페퍼로니를 넣고싶다?
    pPizza ^= (1 << p);
    if (pPizza&(1 << p)) cout << "페퍼로니 피자!" << '\n';
    else cout << "치즈 피자!" << '\n';
 
    
        
 
    return 0;
}

 

- 해당 비트열의(집합의) 크기를 구하고자 할때 다음과 같은 함수를 작성할 수 도 있습니다.

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

 

- 다만, 이미 최적화되어있는 내장 명령어를 사용하는 것이 대회에서는 보다 유리합니다.(집합의 크기 반환)

컴파일러 혹은 언어	집합의 크기 명령어
gcc/g++	__builtin_popcount(x)
Visual C++	__popcnt(x)
Java	Integer.bitCount(x)

 

- 최소 원소 찾기(비트열에서의 오른쪽 끝에 붙어 있는 0의 개수==최소원소의 비트위치 반환)

컴파일러 혹은 언어	최소 원소 찾기 명령어
gcc/g++	__builtin_ctz(x)  (cf. x==0일 경우 결과가 정의되어있지 않음)
Visual C++	_BitScanForward(&index,x)
Java	Integer.numberOfTrailingZeros(x)

 

- 최하위 비트의 해당 비트값(10진수)을 구하기 위해서는 다음과 같은 코드를 이용합니다.

int firstBitValue=(x & -x);

 

- 최소 원소 지우기

x &=(x-1)

* 최소원소, 즉 최하위 비트를 지웠을때 10진수값이 0이 된다면 그 수는 2의 거듭제곱입니다.

 

아래의 책으로 공부하며 자료를 정리하였습니다.

(참고서적: Algorithmic Problem Solving Strategies - 구종만 지음)