비트 연산을 활용해서 부분집합을 구해보자!

---

비트 연산자

연산자	결과
&	AND (둘 다 1이면 1)
ㅣ	OR (하나라도 1이면 1)
^	XOR (서로 다르면 1)
~	모든 비트 반전
<<	왼쪽 시프트 (비트열을 왼쪽으로 이동)
>>	오른쪽 시프트 (비트열을 오른쪽으로 이동)

---

예제

"1234" 문자열을 이용해서 만들 수 있는 숫자들의 집합을 구하려고 한다.
이렇게 만들어진 숫자들을 벡터 subset에 넣을거다.

string numbers = "1234";							
int num_size = numbers.length();
vector<int> subset;

for (int i = 0 ; i < (1 << num_size) ; i++) {
     string element = "";
     for (int j = 0 ; j < num_size ; j++) {
     	if (i & (1 << j))
       		element += numbers[j];       
	}
    subset.emplace_back(atoi(element.c_str()));
}

여기서 num_size = 4
1 << 4라면 1을 왼쪽으로 4번 시프트한거니까 결과는 10000 .
그래서 첫 번째 for문은 0 ~ 1111까지 돌겠다는 이야기

두 번째 포문을 보면
4번을 돌면서
현재 i값과 1을 j번 시프트한 값을 AND 연산하겠다는 의미.
이거는 직접 보는게 편하다 ..

하 진짜 이 똥 그림 ..
긍까

파란색 애들 중 원소 하나 당, 초록색 애들과 전부 AND연산으로 비교한다.
그래서 AND연산이 1인 애들만 element에 더해주면 된다.

예시로, 0011과 초록이들을 AND하면 0001, 0010이 나오고
1110과 초록이들을 AND하면 0010, 0100, 1000이 나온다.

이런 식으로 쭉 쭉 해주면 부분집합이 만들어진다.

그래서 실질적으로 저기서 내가 얻고 싶은 값은
부분집합이 되는 숫자들 == string의 인덱스이다.

그래서 만약에 0010, 0100, 1000이 리턴됐다면,
여기서 1인 위치 == 부분집합에 들어갈 인덱스

즉, 이번 부분 집합은 {A, B, C}라는 의미이다

오키.. ?

좀 어렵지만 내가 이해하기 위해서 적어봤당.

관련 문제

https://www.acmicpc.net/problem/2961

->
나중에 다시 푸니까 까먹어서 다시 정리함!!

---

참고
https://gksid102.tistory.com/90
https://ansohxxn.github.io/algorithm/bitset/