연구소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

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

② 오른쪽 시프트 (>>) : 숫자가 작아진다. 1>>1 : 0(2) = 0 10진수 10에 대해서 오른쪽 시프트 연산해본다! 10 = 1010(2) 1010(2) >> 1 = 101(2) = 5 1010(2) >> 2 = 10(2) = 2 1010(2) >> 3 = 1(2) = 1 1>>n : 2^n 을 나눈것만큼 작아지는 것을 알 수 있다! 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