2의 n승을 의미함. 예를 들어 n = 3 이면, 1 << 3 = 8 = 2의 3승!
{1,2,3}의 모든 부분 집합의 개수를 의미하기도 함.
{ }, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} 은 8 = 2의 3승개이다.
자세한 것은 http://karmainearth.tistory.com/150
자세한 것은 http://karmainearth.tistory.com/150
i & (1 << j)
i의 j번째 bit가 1인지를 검사한다.
이를 이용해 모든 부분집합의 수를 출력해 볼 수 있다. 코드는 다음과 같다.
#include <iostream>
using namespace std;
int arr[3] =
{
1,2,3
};
void makeCandidates(int n)
{
int k = (1 << n);
for(int i=0; i<k; i++)
{
printf("{");
for(int j=0; j<n; j++)
if(i & (1 << j)) printf("%d",arr[j]);
printf("}\n");
}
}
int main()
{
makeCandidates(3);
return 0;
}
Result
{}
{1}
{2}
{12}
{3}
{13}
{23}
{123}
집합 {1,2,3} 의 모든 부분 집합을 출력 했다. 이를 이용해 완전 검색 문제를 해결할 수도 있을 것이라 예상된다..
댓글 없음:
댓글 쓰기