비트마스크,bitset 사용법

비트마스크란 비트연산을 사용하여 부분 집합을 표현하는 것이다.

기본적으로 &, | , ~ , ^ (and,or,not,xor) 연산이 있으며.

비트연산중에는 << 와 >> 연산이 있다.

만약 A << B 라는 연산이 있다면 이것은 A를 왼쪽으로 B비트만큼 민다라는 뜻이 되고

A >> B 같은 경우 오른쪽으로 B비트만큼 민다는 의미를 가진다.

실제로 직접 밀어보면 왼쪽으로 밀 때는 숫자가 2^B배가 되고

오른쪽으로 밀 때는 숫자가 2^B로 나눈값이 된다.

---

비트마스크의 가장 큰 특징은 정수로 집합을 나타낼 수 있다는 점이다.

예를들어 70을 8자리의 비트셋으로 나타내면 01000110이다.

이것을 1이 있는 자리인 {1,2,6}으로 표현할 수 있는것이다.

- n이 포함되어 있는지 검사

만약 2가 포함되어있는지 검사하고 싶다면

70 & ( 1 << 2) 라는 연산을 하면 될 것이다.

1<<2라는 연산을 수행하면 2번째 자리외에는 모두 0이므로 &연산을 했을 때 그 자리 외에는

모두 0이 될 것이며 만약 70에서 2번째 자리가 1이라면 2^2가 나올것이고 아니라면 

0이 나올것이다.

- n을 추가하고 싶다면

만약 위의 70에서 3을 추가하고 싶다면

70 + (1 << 3)을 해주면 간단하게 추가할 수 있다.

단순히 해당 비트에 1을 or연산 해주는 식이다.

- n을 제거하고 싶다면

만약 위의 70에서 2를 제거하고 싶다면

70 & ~2^2를 해주면 된다.

~연산을 해주면 해당 자리의 비트는 0 , 나머지 자리의 비트는 1이 될 것이고

&연산을 해주면 자연스럽게 해당 자리 비트만 0이 될 것이다.

---

bitset 사용법

먼저 #include<bitset>을 통해 라이브러리를 포함시켜준다.

위의 첫번째 예와같이 십진법으로 표현된 수를 집어넣으면 비트형식으로 변환되어

들어가기도 하고

두번째 예처럼 처음부터 비트로 표현된 수를 집어넣을 수도 있다.

이렇게 원하는 수만 잘 세팅해준다면 bitset으로 선언이 됐기 때문에 우리가 알고있는 연산들을

사용하여 간단하게 bit연산을 수행해줄 수 있다.