오늘부터는 그 동안 공부했던 것을 잠깐 복습하려 한다.
종만북 2권의 앞부분 절반 정도를 공부했다. (16장 비트마스크 ~ 24장 구간 트리)
지금 복습안하면 기껏 공부한 거 다 까먹을 것 같아서 여기에 정리한다.
다만, 내가 공부했던 내용을 복습하고 정리한 내용이기 때문에 내가 다시 봤을 때 기억나는 것이 목표이고
따라서 여러분이 읽을 때 이게 왜 이렇게 되는거지라고 생각할 수 있다.
암튼 서론 그만쓰고 시작한다.
비트마스크란?
불린 값을 비트마다 저장하는 것이다.
비트마스크 장점
- 비트 하나하나를 불린 변수(스위치 값)으로 사용하기 때문에 메모리 낭비가 적다.
- 반복문 차수를 하나 줄일 수 있다. (ex. O(n^3)을 O(n^2)으로 줄일 수 있다.)
- 2번 때문에 코드가 더 간결해진다.
비트마스크를 사용해야 할 때
- 많은 불린 값을 저장해야 할 때
- 메모리 초과가 일어날 때
- 반복문 차수를 하나 줄여야 할 때
비트 연산시 주의할 점
- ==, != 보다 우선순위가 낮다.
- 상수는 32비트 부호있는 수이다.(1<<33 하면 오버플로우 발생)
- 만약 64비트 부호없이 쓰려면 1ull << 33 해야 한다.(접미사 ull)
- C++에서 N비트 정수를 N비트 이상 왼쪽으로 시프트하면 0이 안 나올수도 있다.(환경마다 다름)
비트마스크 집합 연산(종만북에서는 피자토핑을 예시로 들음)
- 공집합 : 0
- 꽉찬 집합 : (1<<p) - 1 (p개 비트가 1로 초기화됨)
- 원소 추가 : toppings |= (1<<p); (p번째 비트만 켜져 있는 것과 OR / 이미 있을 경우 변동없음)
- 원소의 포함 여부 확인 : if(toppings & (1 << p))
- 원소 삭제 : toppings &= ~(1<<p); (p번째 비트만 꺼져 있는 것과 AND / 이미 없는 경우 변동없음)
- 원소 토글 : toppings ^= (1<<p);
- 집합의 크기(1의 갯수) : __builtin_popcount(toppings) (gcc기준) / 직접 구하고 싶다면 return n%2 + bitCount(n/2); 로 재귀함수 돌리기
- 최소원소 찾기(맨 끝 1의 위치) : __builtin_ctz(toppings) (gcc기준 / 입력이 0일때는 사용하면 안됩니다.) / 혹은 toppings & (-toppings) (2의 보수 사용)
- 최소원소 지우기 : toppings &= (toppings - 1) (2의 거듭제곱 값은 1이 하나밖에 없으므로 지우면 0이 됩니다!)
- 모든 부분집합 순회하기 : for(int subset = pizza; subset; subset = ((subset-1) & pizza) { ... } / (최소원소 지우기 반복, 공집합은 순회하지 않음)
비트마스크 대표적인 예제
에라토스테네스의 체
에라토스테네스의 체에서 N이 커질수록 시간보다 메모리 초과 가능성이 높다.
지워진 수를 저장하는 것을 int형 변수로 하는 것보다, 비트마스크를 사용하면 1/8로 줄일 수 있다.
unsigned char sieve[(MAX_N + 7) / 8]로 배열을 잡는다.
k번째 원소는 sieve[k/8] 의 k%8번째 비트이다.
함수에서 계산할 때는 k/8대신 k >> 3, k%8 대신 k & 7을 하면 좀 더 빠른 계산이 가능하다.
15퍼즐 상태 표현하기
64비트 부호없는 정수 변수 하나에 [0, 15] 구간의 정수 16개를 넣을 수 있다.
