BITMASKS 를 정리해 봅니다...
등등 정리
Bitmasks provide an efficient way to manipulate a small set of Boolean.
엄밀하게 자료구조는 아니지만, 많이 쓰인다
정수의 이진수 표현을 자료 구조로 쓰는 기법
boolean 배열의 true / false 를 더 작은 메모리와 더 빠른 속도로 처리
비트 연산자
a & b: 비트별로 AND 연산
a | b: 비트별로 OR 연산
a ^ b: 비트별로 XOR 연산
~a: 비트별 NOT 연산 결과
a << b: 왼쪽으로 b 비트 시프트
=> a << 1 의 의미는 a 를 * 2 한 번
=> a << 2 의 의미는 a 를 * 2 두 번
=> ...
a >> b: 오른쪽으로 b 비트 시프트
=> a >> 1 의 의미는 a 를 / 2 * 한 번
=> a >> 2 의 의미는 a 를 / 2 * 두 번
=> ...
집합의 구현 - 가장 중요한 사용 사례(예, 20 개를 이용)
꽉 찬 집합
int a = (1<<20) - 1; // 1 을 20 bit 이동하고 1 을 뺀다
원소 추가 p (0 <= p < 20)
a |= (1 << p);
원소의 포함 여부
if (a & (1 << p)) ~~
두 집합의 연산 - 집합간의 연산을 빠르게 할 수 있다는 것이 큰 장점
합집합
added = (a | b);
교집합
intersection = (a & b);
하나에만 포함된 원소들의 집합
toggled = (a ^ b);
집합의 크기
1 의 개수를 센다
최소 원소 찾기
int first = (a & -a);
최소 원소 지우기
a &= (a - 1);
모든 부분 집합 순회하기
for (int subset = a; subset; subset = ((subset-1) & a)) {}
큰 N 개를 처리
예를 들어, 50,000 개의 어떤 값들이 50,000 가지의 상태( true / false )를 가진다고 하면
50,000 * 50,000 = 2,500,000,000 (25억) 개의 변수가 필요하다
boolean 배열로 처리하면 25 억 바이트 (대략 2,381 MB) 정도 필요하지만,
각 byte 를 8 개의 bit 로 처리해주면, 298 MB 정도로 줄어들 수 있다.
문제 제약 조건이 256 MB 정도라면,
35,000 * 50,000 개 정도 (대략 208 MB)가 처리가 가능
128 MB 정도라면
20,000 * 50,000 개 정도 (대략 119 MB) 가 처리가 가능
정수를 오른쪽으로 3 비트 시프트 => 8 로 나누는 것
7 (0111) 과 AND 연산 => 8 (1000) 로 나눈 나머지를 구하는 것
