16. 비트마스크 (bitmask)

장점

- 더 빠른 수행 시간을 보장합니다.

- 더 간결한 코드를 제공합니다.

- 메모리 사용량을 줄일 수 있습니다.

즉, 더 많은 데이터를 미리 계산해서 저장해 둘 수 있습니다.

비트마스크를 자료 구조로 이용하는 방법 및 각종 트랙을 소개합니다.

용어정리

8bit를 예로들자면,

최솟값은 0이고, 최댓값은 1111 1111(2) = 255입니다.

 

20을 나타내는 비트를 최하위 비트(LSB, Least Significant Bit),

2N-1을 나타내는 비트를 최상위 비트(MSB, Most Significant, Bit) 라고 합니다.

 

어떤 비트의 위치가 1이면 해당 비트가 "켜져 있다"고 하고,

0이면 "꺼져 있다"라고 합니다.

연산	코드
두 정수 a, b를 비트 별로 AND 연산	a & b
OR	a
XOR	a ^ b
NOT	~a
정수 a를 왼쪽으로 b비트 시프트	a << b
오른쪽으로 b비트 시프트	a >> b

※ !는 참을 거짓으로 또는 거짓을 참으로 바꿉니다.

정수형(int)에서는 참은 0 이외의 수를 말하며, 거짓은 0을 말합니다.

따라서 ~a(NOT)과 !a는 다릅니다.

~a는 각 비트를 0은 1로, 1은 0으로 바꾸어주는 역할을 합니다. (1의 보수라고도 말하지요)

 

 

 

주의사항 (C++)

• 연산자 우선순위가 낮기 때문에 괄호 쳐주는 습관을 가지는 것이 좋습니다.
  ex) ( 6 & 4 )
• 1은 부호있는 32bit 상수로 취급합니다. 때문이 32bit 를 넘어가는 수표현에서는 오류가 날 수 있습니다.
• 부호 있는 정수형에서 최상위 비트가 켜진 숫자는 음수를 표현합니다.

공집합과 전체집합

int empty = 0;

int full = (1 << 20) - 1;

1 << 20 은 1뒤에 20개의 0이 있는 정수입니다. 여기서 1을 빼면 20개의 비트가 모두 켜진 수를 얻을 수 있습니다.

원소 추가

원소를 추가한다는 것은, 해당 비트를 키는 것입니다.

samplebit의 p번째 비트를 켜봅시다.

samplebit |= (1 << p);

1과 OR 연산을 하면 반드시 1이 나오기 때문에, p번째 비트는 켜지게 됩니다.

원소의 포함 여부 확인

if ( samplebit & (1 << p)) cout << "There is 'p'th element" << endl;

여기서 주의할 점은 &의 결과값이 0 또는 (1 << p) 이라는 것입니다.

samplebit과 (1<<p)를 연산하면, 자리수는 자동적으로 작은 수에 맞추어지기 때문입니다.

 

원소 삭제

samplebit &= ~(1 << p);

위 코드는, samplebit의 p번째 비트가 0이든 1이든 상관없이 0으로 만들어 줍니다.

원소의 토글

samplebit ^= (1 << p);

해당 비트(p)가 켜져 있으면 끄고, 꺼져 있으면 킵니다. XOR인 ^를 사용합니다.

두 집합 연산

int union = (a | b);
int intersection = (a & b);
int set_difference = (a & ~b);
int toggle = (a ^ b);

위 연산은 n개(비트)의 원소를 가진 두 집합 a, b의 4가지 연산(합집합, 교집합, 차집합, XOR)을

원소 하나에 대해 수행하는 것과 다를 것이 없습니다. = 수행 속도가 빠릅니다.

집합의 크기 구하기

int bit_size(int x){
    if (x == 0) return 0;
    return x % 2 + bit_size(x / 2);

작은 셋에 대해 간단히 구하고자 할 때 사용합니다. 이미 최적화하여 만들어 놓은 코드가 gcc/g++ 또는 java에는 구현되어 있습니다.

 

gcc/g++ __builtin_popcount(x)
java Integer.bitCount(x)

원소 찾기

특별히 첫번째 원소를 찾아봅시다.

int firstbit = (samplebit & -samplebit);

이는 컴퓨터가 음수를 표현하기 위해 2의 보수를 이용한다는 점을 이용합니다.

최소 원소 지우기

samplebit &= (samplebit - 1);

예로 40(= 1001000₍₂₎)과 39(= 100111₍₂₎)의 AND을 하면 32(=100000₍₂₎)가 되어
최하위 비트가 꺼진것을 알 수 있습니다.

 

이 방법은 2의 거듭제곱값인지 확인할 때 유용하게 사용됩니다.

모든 부분집합 순회하기

{1, 2, 3}의 부분집합은 {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} 입니다. (공집합 제외)

for (int subset = fullset; subset; subset = ((subset - 1) & fullset)) {
    // cout << subset << endl;
}