> For the complete documentation index, see [llms.txt](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/undefined-1/3.md).

# 연구소3 문제 풀기 위한 비트마스킹 복습⭐️

비트마스크 : **정수**로 집합 나타낼 수 있다.

{1, 3, 4, 5, 9} = **2^1 + 2^3 + 2^4 + 2^5 + 2^9** = **570⭐️**

|  9  |  8  |  7  |  6  |  5  |  4  |  3  |  2  |  1  | **0** |
| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :---: |
|  1  |  0  |  0  |  0  |  1  |  1  |  1  |  0  |  1  |   0   |

1부터 N까지 정수로 이루어진 집합 => 0부터 N-1까지 정수로 변환한다.\
1\~N 정수 집합은 공간 2배 더 필요하고, 각종 연산을 조금 변형해서 사용해야하기 때문이라고 함.

**비트연산** : 두 수 A,B 가장 뒤자리부터 한 비트씩 연산 수행.

* AND(&)
* OR(|)
* NOT(\~) : 8비트/ 32비트 자료형인지에 따라, signed/unsigned인지에 따라 보여지는 결과물 다름.
* XOR(^)
* Shift(<<, >>)⭐️⭐️⭐️⭐️⭐️

**Shift연산 : A를 B만큼 시프트연산!!!**\
**A << B = A \* 2^B**\
**A >> B = A / 2^B**

① 왼쪽 시프트 (<<) : 숫자가 커진다.\
&#x20; 1<<1 : 10(2) = 2\
&#x20; 1<<2 : 100(2) = 4\
&#x20; 1<<3 : 1000(2) = 8\
&#x20; 1<\<n = 2^n인 것을 알 수 있다!⭐️⭐️⭐️

② 오른쪽 시프트 (>>) : 숫자가 작아진다.\
&#x20; 1>>1 : 0(2) = 0 \
&#x20; 10진수 10에 대해서 오른쪽 시프트 연산해본다! 10 = 1010(2)\
&#x20; 1010(2) >> 1 = 101(2) = 5\
&#x20; 1010(2) >> 2 = 10(2) = 2\
&#x20; 1010(2) >> 3 = 1(2) = 1\
&#x20; 1>>n : 2^n 을 나눈것만큼 작아지는 것을 알 수 있다!\
&#x20; A>>B = A / 2^B

**본격 비트연산 예**\
**{1,3,4,5,9} = 570 = 1000111010(2)**

1. 검사 : AND(&)\
   **n을 포함하는지 검사 = n번째 비트에 1이 있는지 검사⭐️⭐️⭐️⭐️⭐️**\
   **n번째 비트 = 2^n과 AND 연산하면된다. 2^n은 그 자체로 n번째비트가 1이기 때문이다!**\
   0 포함되있는지 검사 = 570 & **2^0** =  570 & (1<<0)\
   1 포함되있는지 검사 = 570 & **2^1** = 570 & (1<<1)\
   2 포함되있는지 검사 = 570 & **2^2** = 570 & (1<<2)\
   3 포함되있는지 검사 = 570 & **2^3** = 570 & (1<<3)
2. 추가 : OR(|)
3. 제거 : AND(&) 와 NOT(\~)\
   n번째 비트를 먼저 NOT연산으로 1과 0반전 시킨다.=>n번째 비트만 0이 된다! = \~2^n

   반전시킨 2^n인 \~2^n과 AND 연산! => **원래 n번째 비트가 1이든 0이든 0과 AND하면 무조건 0이 되기 때문**

   0 제거 = 570 & \~(**2^0)** =  570 & \~(1<<0)\
   1 제거 = 570 & \~(**2^1)** = 570 & \~(1<<1)\
   2 제거 = 570 & \~(**2^2)** = 570 & \~(1<<2)\
   3 제거 = 570 & \~(**2^3)** = 570 & \~(1<<3)
4. 토글 : XOR(^)\
   원래 1이면 0으로, 원래 0이면 1로 바꾼다. XOR은 다르면 1, 같으면 0이 되는 성질을 이용한다!\
   n번째 비트를 토글한다면 **2^n(n번째 비트가 1인 값**)을 XOR 연산하면 된다!

   0 토글 = 570 ^ (**2^0)** =  570 ^ (1<<0)\
   1 토글 = 570 ^ (**2^1)** = 570 ^ (1<<1)\
   2 토글 = 570 ^ (**2^2)** = 570 ^ (1<<2)\
   3 토글 = 570 ^ (**2^3)** = 570 ^ (1<<3)
5. **전체집합 구하기 : (1<\<N) - 1 ⭐️⭐️⭐️⭐️⭐️**\
   전체 원소가 N개라고 하면, N개의 비트로 부분집합을 나타낼 수 있다.\
   ex) N = 5일때, 전제 집합은 {1,1,1,1,1}이고 이것을 비트로 나타내면 11111(2)이다.\
   N=5일 때 전체집합을 비트로 나타내면 2^4 + 2^3 + 2^2 + 2^1 + 2^0 이다.(**2진수 맨 오른쪽 자릿수는 0부터 시작**)

   이것은 2^5에서 1을 뺀수다!!\
   따라서 N개의 숫자가 있다고 할 때 전체 집합은 2^N - 1과 같다. 그리고 이것은 (1<\<N) -1로 나타낼 수 있다!
6. 공집합 구하기 : 0