✔ 미리 알림: 본 내용은 종만북의 내용을 정리한 것입니다.

비트마스크

컴퓨터는 2진 체계로 되어있다보니 이진법 관련 연산이 굉장히 빠르다. 이러한 특성을 이용해 정수의 이진수 표현을 자료 구조로 쓰는 기법을 비트마스크(bitmask)라고 한다. 엄밀하게 말하면 자료 구조라고 할 수는 없지만 일단 유용하다.

장점

빠른 수행 시간
간결한 코드
작은 메모리 사용량
연관 배열을 배열로 대체

집합 구현 및 각종 연산

N비트 정수 변수는 0부터 N-1까지의 정수 원소를 가질 수 있는 집합이 된다. 원소 i가 집합에 속해 있는지는 2^i을 나타내는 비트가 켜져 있는지 여부로 나타낸다. {1, 4, 5, 6, 7, 9}를 표현하는 정수는 754인 것이 그 예이다.

공집합과 꽉 찬 집합

공집합은 0으로 표현하면 되고 꽉 찬 집합은 다음과 같이 표현하면 된다. 다만, 오버플로에 주의해야한다. (1 « 32를 하면 int에서는 터짐)

다음 예제는 20개의 비트를 킬 때이다.

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

원소 추가

p번째 비트를 추가할 때

toppings |= (1 << p);

원소의 포함 여부 확인

if(toppings & (1 << p)) cout << "pepperoni is in" << endl;

결과는 0 또는 1 « p이기 때문에 if문 작성시 1과 비교하는 불상사는 만들지 말자.

원소의 삭제

toppings &= ~(1 << p);

원소의 토글

toppings ^= (1 << p);

두 집합에 대해 연산하기

int added = (a | b);        // a와 b의 합집합
int intersection = (a & b); // a와 b의 교집합
int removed = (a & ~b);     // a에서 b를 뺀 차집합
int toggled = (a ^ b);      // a와 b중 하나에만 포함된 원소들의 집합

집합의 크기 구하기

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

또는 컴파일러마다 구현된 내장 명령어를 사용하는 방법도 있다.

컴파일러 혹은 언어	집합의 크기 구하기
gcc/g++	__builtin_popcount(toppings)
Visual C++	__popcnt(toppings)

내가 확인한 바로 MSVC에서 해당 함수를 사용하기 위해서는 <intrin.h> 헤더를 추가해줘야 한다.

최소 원소 찾기

int firstTopping = (toppings & -toppings);

집합 크기 구하는 것과 마찬가지로 내장 함수가 있다.

컴파일러 혹은 언어	최소 원소 구하기
gcc/g++	__builtin_ctz(toppings)
Visual C++	__BitScanForward(&index, toppings)

마찬가지로 <intrin.h> 헤더를 추가해야 한다.

최소 원소 지우기

최소 원소 찾는 방법을 응용해서 지울 수도 있지만 더 효율적인 방법이 있다.

toppings &= (toppings - 1);

모든 부분 집합 순회하기

for (int subset = pizza; subset; subset = ((subset - 1) & pizza)) {
    // subset은 pizza의 부분집합
}

Gnod

Bitmask