c++ 비트 마스킹, 배열

int 나 char 등 기본 자료형 변수를 비트 단위로 사용함으로서 배열처럼 사용하는 기법.

 

ex) char a;  //0000 0000
      a |= 1<<3;  // 3번째 비트(인덱스)에 1을 등록
      a & 1<<3;  // 3번째 비트(인덱스)의 값을 확인
      a &= ~(1<<3);  //3번째 비트(인덱스)의 값 제거

 

int 는 32비트라서 32개 크기의 bool 배열로 쓸 수 있음.

 

*참고 : 연산 순서 [  "+"(사칙), "<<" (시프트), "=="(비교), "&"(비트 연산) ]

 

 

10개 크기 배열 기준 (int 사용)

모든 원소 채우기

block = (1<<10) - 1		
//100 0000 0000 -1 
// 11 1111 1111

원소 추가

block |= 1<<idx;

원소 확인

block & 1<<idx;

원소 삭제

block &= ~(1<<idx);

원소 토글

block ^= 1<<idx;

• ^ : (xor) ( 같으면 0, 다르면 1)

원소 총 갯수 확인

int cnt =o;
int temp = block;
while(temp)
{
    cnt += (temp & 1);
    temp >>=1;
}

최소 원소만 출력?

int first = block & (-block);
//00 1100 1000 (block)
//11 0011 1000 (-block) (2의 보수)
//00 0000 1000

최소 원소 제거

block -= block & (-block);
// or
block &= (block-1)