[Algorithm/ 비트마스크]

공부 전 Tmi.

매일 일 집 일 집 하니 꾸미는 날도 없고 나를 너무 대충대충 살게 두는 거 같아서 현타가 옵니다. 옷도 가방도 화장품도 안 산 지 오래 된 거 같아요. 나를 위한 소비도 없이 그냥 먹고 자고 일합니다. 이렇게 살면 좋을까? 라는 생각이 종종 듭니다. 잘 살고 있는건 아닌거 같죠 ? ㅠㅠ 공부도 조금 쉬었어요. 나의 속도로 공부하려고 했는데 남들의 속도를 보고 불안함을 느끼면서 우울감에 쉬는 것…? 참 아이러니합니다. (한심..) 백준 드디어 200개 돌파했습니다. 아직 적은 수지만 이번 연도에 500개는 넘고 싶네요. 지금은 정말 푸는 데 오래 걸리고 이전에 풀었던 거와 비슷한 문제여도 헤매는데 그러지 않을 날이 올까요? 현재 골드 2 입니다. 백준이 플레니넘이 되는 날 헌 번 더 Tmi을 적겠습니다. 힘내자!  멋진 여성이 되겠옹 ~! 아자 !!

---

오늘은 비트 마스크에 대해서 샅샅이 분석하려고 합니다. 요즘 DP 문제를 푸는데 비트 마스크를 사용하는 부분을 풀고 있거든요. 모르겠어요…. 그냥 모르겠어 ~~~ 잘 안 돌아갑니다. 비트 마스크에 대해서 정리해봅시다.

비트 연산자

여기서는 프로그래밍에서 배열에 있는 원소 삭제하고 추가하고 있는지 확인하는 작업을 비트와 비트연산자로 하는 방법에 대해서 공부하려고 합니다. 

비트 마스크는 비트를 다뤄야 하는 문제이므로 비트 연산자를 제대로 알아야 합니다. 비트(Bit)란 컴퓨터에서 처리하는 정보의 최소표현단위 입니다. 우리가 사용하는 숫자는 10진수고 이 10진수를 0과 1로 표현을 하면 비트로 표현하는데 이를 2진수라고 칭합니다. 

a & b	AND	🔹 둘다 1이라면 1, 아니라면 0    ex. ( A = 0101 / 5 ) & ( B = 0001 / 1 ) = ( Result = 0001 / 1 )
a | b	OR	🔹 둘다 0이라면 1, 아니라면 0   ex. ( A = 0101 / 5 ) | ( B = 0001 / 1 ) = ( Result = 0101 / 5 )
a ^ b	XOR	🔹 모든 비트에 대해서 반대로 Not연산을 해준다.    ex. ( A = 0101 / 5 ) ^ ( B = 0001 / 1 ) = ( Result = 0001 / 1 )
~ a	NOT	🔹 모든 비트에 대해서 반대로 Not연산을 해준다.    ex.  ~(1011) = 0100
a << b	LEFT SHIFT	🔹 왼쪽으로 밀어준다.   ex.   1. 0001 << 0 =  0001   2. 0101 << 1 =  1010   3. 0101 << 3 =  0010 1000
a >> b	RIGHT SHIFT	🔹 오른쪽으로 밀어준다.   ex.   1. 0001 >> 0 =  0001   2. 0101 >> 1 =  0010   3. 0101 >> 3 =  0000

 

비트 마스크를 이용한 추가, 삭제, 토글, 검색

 

정리하기

// Add
S |= 1 << x - 1;

// Remove
S &= ~(1 << x - 1);

// Check
cout << ((S & (1 << x - 1)) ? true : false);

// Toggle
S ^= 1 << x - 1;

// 모두 1로 채우기
S = ~(0 << N);

S = (1<<N)-1;

//모두 0으로 채우기
S = 0;

// on되어 있는 집합 개수 세기
ex) M = 1001 0110
 while (M) {
    count += (M&1);
    M >>= 1;
 }
 // 1001 0110 .... count = 0
 // 0100 1011 .... count = 1
 // 0010 0101 .... count = 2
 // 0001 0010 .... count = 2
 // 0000 1001 .... count = 3
 // 0000 0100 .... count = 3
  ....
 // 0000 0001 .... count = 4