Hello

: )

2018년 4월 12일 목요일

BITMASKS 정리

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 = 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) 가 처리가 가능


                              정수를 오른쪽으로 3 비트 시프트 => 8 로 나누는 것
                              7 (0111) 과 AND 연산 => 8 (1000) 로 나눈 나머지를 구하는 것


                              댓글 없음:

                              댓글 쓰기