BITMASKS 정리

BITMASKS 를 정리해 봅니다...

알고리즘 문제 해결 전략

Codeforces 블로그 (BITMASKS - FOR BEGINNERS)

등등 정리

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 = 0;

꽉 찬 집합
int a = (1<<20) - 1;  // 1 을 20 bit 이동하고 1 을 뺀다

원소 추가 p (0 <= p < 20)
a |= (1 << p);

원소의 포함 여부
if (a & (1 << p)) ~~

원소의 삭제
a &= ~(1 <<p);

원소의 토글
a ^= (1 << p);

두 집합의 연산 - 집합간의 연산을 빠르게 할 수 있다는 것이 큰 장점

합집합
added = (a | b);

교집합
intersection = (a & b);

차집합
removed = (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) 가 처리가 가능

https://github.com/sgchoi5/algorithm/blob/master/16_code_snippet.cpp

정수를 오른쪽으로 3 비트 시프트 => 8 로 나누는 것

7 (0111) 과 AND 연산 => 8 (1000) 로 나눈 나머지를 구하는 것