post list

2015년 7월 1일

[Algorithm] Bit 연산

1  <<  n
 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

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} 의 모든 부분 집합을 출력 했다. 이를 이용해 완전 검색 문제를 해결할 수도 있을 것이라 예상된다..





댓글 없음:

댓글 쓰기