비트연산

- 비트 연산자

AND 연산    a & b

OR   연산    a | b

XOR 연산    a ^ b

NOT 연산    ~a

a를 왼쪽으로 b만큼 시프트 a<<b

a를 오른쪽으로 b만큼 시프트 a>>b

- 유의할 점

1) 연산자 우선 순위

비트 연산자는 == , != 보다 우선순위가 낮다.

그래서 if(a&b==4) 같은 코드는 주의! if((a&b)==4)처럼 무조건 괄호를 사용해주는게 좋다.

2) 64비트 오버 플로우

unsinged long long a = (1<<35);

1은 부호 있는 32 bit로 취급 되기 때문에 오버플로우 발생.

따라서 접미사 ull을 붙이거나 unsingd long long tmp = 1  에 저장해서 사용한다.

- 비트 마스크를 이용한 집합 구현

1)공집합 

1<<N : N개의 비트를 사용할때 N개의 비트를 모두 0으로 초기화(N+1번째 비트는 )

2)꽉찬 집합 

(1<<N) - 1 : N개의 비트를 사용할때 N개의 비트를 모두 1로 초기화

3)합집합(OR)

added = (a | b);

4)교집합(AND)

intersection = (a&b);

5)차집합

removed = (a & ~b);

6)모든 부분집합 순회하기

for(int subset = set; subset>0 ; subset = ((subset-1)&subset) )

{

//모든 부분집합 원소

//subset -1  & subset을 했을 때 최하위 비트가 하나씩 꺼짐(0)

}

예제 문제 

https://algospot.com/judge/submission/detail/550178

#include<stdio.h>

#include<algorithm>

using namespace std;

const int INF = 987654321;

int N,K,M,L;

int cache[10][1<<12];

int pre[12];

int classes[10];

int numOfCount(int currentTaken){

    int ret = 0;

    for(int i=0;i<N;i++){

        if((currentTaken>>i)&1)

            ret++;

    }

    return ret;

}

int sol(int currentSemester,int currentTaken){

    //printf("currentTaken :%d\n",currentTaken);

    if(numOfCount(currentTaken)>=K)

        return 0;

    if(currentSemester == M)

        return INF;

    int &ret = cache[currentSemester][currentTaken];

    if(ret!=-1)

        return ret;

    ret = INF;

    //이번학기 안듣고 넘김

    ret = min(ret, sol(currentSemester+1, currentTaken));

    

    //모든 경우의 수를 고려해서 수업을 들음

    int canTake = (classes[currentSemester] & (~currentTaken));//들었던 수업 빼기

    

    //선행수업 조건 안되는 과목 빼기

    for(int i=0;i<N;i++){

        if(((currentTaken & pre[i]) != pre[i])

           && (canTake&(1<<i))){

            canTake &= ~(1<<i);

        }

    }

    

    for(int take=canTake;take>0;take=((take-1)&canTake)){

        if(numOfCount(take)>L)

            continue;

        ret = min(ret,sol(currentSemester+1, currentTaken|take)+1);

    }

    return ret;

}

int main(void){

    int T;

    scanf("%d",&T);

    for(int testCase=0;testCase<T;testCase++){

        for(int i=0;i<10;i++){

            for(int j=0;j<(1<<12);j++){

                cache[i][j]=-1;

            }

        }

        scanf("%d %d %d %d",&N,&K,&M,&L);

        //set pre classes

        for(int n=0;n<N;n++){

            int numOfPre;

            

            pre[n] = 0;

            scanf("%d",&numOfPre);

            for(int cnt=0;cnt<numOfPre;cnt++){

                int preClass;

                scanf("%d",&preClass);

                pre[n] |= (1<<preClass);

            }

        }

        

        //set semester

        for(int m=0;m<M;m++){

            int numOfClass;

            

            classes[m] = 0;

            scanf("%d",&numOfClass);

            for(int cnt=0;cnt<numOfClass;cnt++){

                int major;

                scanf("%d",&major);

                classes[m] |= (1<<major);

            }

        }

        int ret = sol(0,0);

        if(ret==INF)

            printf("IMPOSSIBLE\n");

        else

            printf("%d\n",ret);

    }

    return 0;

}