비트연산 공부하기

1. 공집합 꽉 찬 집합 구하기

0 ~ 19 가 집합의 크기일 경우

unsigned int a = (1 << 20) - 1;

2. 원소 추가

15번째 원소 추가

a |= (1 << 15)

3. 원소의 포함 여부 확인

15번째 원소가 켜져있는지 확인(켜져있으면 1이아니라 1<<15의 값이 된다.)

if(a & (1 << 15)) 

4. 원소의 삭제

15번째 원소 삭제

a &= ~(1<<15);

5. 원소의 토글

15번째 원소 토글

a ^= (1 << 15);

6. 두집합의 합집합, 교집합, 차집합, 교집합을 제외한 여집합

a | b, a & b, a & ~b, a ^ b

7. 집합의 크기구하기

int bitCount(int a){

if(a == 0) return 0;

return a % 2 + bitCount(a >>1 );

}

8. 최소 원소 찾기

int a = 1 << 3;

a |= 1 << 5;

int m = a & -a;

printf("%d", m);   -> 8

9. 최소 원소 지우기

int a = (1 << 3);

a &= (a - 1);

10. 모든 부분집합 순회

for(int subset = pizza; subset; subset =((subset - 1) & pizza){

}

-> 공집합은 방문하지 않는다..

11. 2의 n승으로 나눌경우, 쉬프트 연산을 활용하자

a = a/8   -> a = a >> 3;

12. 2의 n승으로 %연산을 할 경우, 앤드 연산을 활용하자

a = a% 8  -> a &= (8 - 1)

JM북 공부중.