비트마스크

지식 저장소·2021년 12월 2일

문제해결기법

목록 보기

16/21

도입

현대의 모든 CPU는 이진수를 이용해 모든 자료를 표현합니다. 이와 같은 디자인 결정은 내부적으로 이진수를 사용하는 컴퓨터들은 이진법 관련 연산들을 아주 빨리 할 수 있기 때문에 가끔 중요할 때가 있습니다. 이와 같은 특성을 이용해 정수의 이진수 표현을 자료 구조로 쓰는 기법을 비트마스크라고 부릅니다. 비트마스크는 엄밀하게 말해 자료 구조라고 할 수는 없지만 종종 굉장히 유용하게 사용됩니다.
비트마스크를 사용하는 코드는 다음과 같은 장점을 갖습니다.

더 빠른 수행 시간: 비트마스크 연산은 $O(1)$ 에 구현되는 것이 많기 때문에, 적절히 사용할 경우 다른 자료 구조를 사용하는 것보다 훨씬 빨리 동작합니다. 물론 비트마스크를 사용할 수 있다는 말은 원소의 수가 많지 않다는 뜻이기 때문에 엄청나게 큰 속도 향상을 기대할 수는 없지만, 이와 같은 연산을 굉장히 여러 번 수행해야 할 경우에는 작은 최적화도 큰 속도 향상을 가져올 수 있습니다.
더 간결한 코드: 다양한 집합 연산들을 반복문 없이 한 줄에 쓸 수 있습니다.
더 작은 메모리 사용량: 비트마스크를 이용하는 코드들은 같은 데이터를 더 적은 메모리를 사용해 표현할 수 있습니다. 더 적은 메모리를 사용한다는 말은 더 많은 데이터를 미리 계산해서 저장해 둘 수 있다는 뜻입니다. 더 많은 데이터를 미리 계산해 둘 수 있으면 프로그램도 빨라지고, 더 적은 메모리를 사용하는 프로그램은 일반적으로 캐시 효율도 더 좋습니다.
연관 배열을 배열로 대체: 불린 값 배열을 키로 갖는 연관 배열 객체를 사용하고 있다고 합시다. 이때 비트마스크를 써서 같은 정보를 정수 변수로 나타내면 단순한 배열 $int[]$ 를 사용해 같은 정보를 나타낼 수 있습니다. 많은 경우 이 기법은 엄청난 시간과 메모리의 차이를 불러옵니다.

비트 연산자

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

유의할 점들

다음은 비트마스크를 이용하는 프로그램을 짤 때 하기 쉬운 실수들입니다.
비트마스크를 사용할 때 가장 많이 하는 실수는 연산자 간 우선순위를 혼동하는 것입니다. C++이나 자바에서 &, |, ^ 등의 비트 연산자의 우선순위는 == 혹은 != 등의 비교 연산자보다 낮습니다. 이 말은 이런 연산자와 비교 연산자가 섞여 있는 경우 우리가 원하지 않는 답이 나올 수 있다는 것입니다. 예를 들어 보겠습니다.

int c = (6 & 4 == 4);

앞의 식에서는 4 == 4가 먼저 계산되고, 이 결과인 1이 6과 비트별 AND되어 $c$ 는 0이 됩니다. (참고로 자바에서 위 코드는 문법 오류입니다.)
두 번째로 많이 하는 실수는 64비트 정수를 비트마스크로 사용할 때 발생하는 오버플로입니다. 예를 들어 보겠습니다.

bool isBitSet(unsigned long long a, int b) {
    return (a & (1 << b)) > 0;
}

C++에서 1은 부호 있는 32비트 상수로 취급되기 때문에, b가 32 이상이면 식 (1 << b)에서 오버플로가 발생하기 때문입니다. 이 문제를 해결하기 위해서는 1 뒤에 이 상수가 부호 없는 64비트 정수임을 알려주는 접미사 ull을 붙여 주어야 합니다.
또 하나 종종 문제가 되는 것으로 부호 있는 정수형의 사용이 있습니다. 오른쪽으로 시프트 할 때 최상위 비트가 달라지면 부호가 바뀌므로 부호에 맞는 숫자를 채워줍니다. 따라서 변수의 모든 비트를 다 쓰고 싶을 때는 부호 없는 정수형을 쓰는 것이 좋습니다.

비트마스크를 이용한 집합의 구현

비트마스크의 가장 중요한 사용 사례는 집합을 구현하는 것입니다. 이 표현에서 $N$ 비트 정수 변수는 0부터 $N-1$ 까지의 정수 원소를 가질 수 있는 집합이 됩니다. 이때 원소 $i$ 가 집합에 속해 있는지 여부는 $2^i$ 을 나타내는 비트가 켜져 있는지 여부로 나타냅니다. 예를 들어 여섯 개의 원소를 갖는 집합 {1, 4, 5, 6, 7, 9}을 표현하는 정수는 754임을 다음과 같이 알 수 있습니다.

$2^1+2^4+2^5+2^6+2^7+2^9=10 1111 0010_2=754$

비트마스크 연산을 이용해 이 집합을 어떻게 조작할 수 있는지 알아봅시다.

피자집 예제

고객들이 원하는 토핑을 골라 주문할 수 있는 피자집의 주문 시스템을 만든다고 합시다. 이 피자집에는 0부터 19까지의 번호를 갖는 스무 가지의 토핑이 있으며, 주문시 토핑을 넣기 / 넣지 않기를 선택할 수 있습니다. 그러면 한 피자의 정보는 스무 종류의 원소만을 가지는 집합이 되고, 비트마스크를 이용해 표현할 수 있겠지요. 물론 크기 20인 불린 값 배열을 사용하더라도 같은 일을 할 수 있습니다만, 비트마스크를 이용하면 다양한 비트 연산을 이용해 집합 연산을 빠르고 간단하게 구현할 수 있습니다.

공집합과 꽉 찬 집합 구하기

공집합은 그냥 0입니다. 꽉 찬 집합은 다음과 같은 코드로 얻을 수 있습니다.

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

원소 추가

toppings |= (1 << p);

원소의 포함 여부 확인

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

원소의 삭제

toppings -= (1 << p);

이 코드는 페퍼로니가 없을 때 쓰면 큰일납니다. 토핑이 없을 때도 정상적으로 동작하는 방법은 다음과 같은 코드를 사용하는 것입니다.

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);
}

이것을 최적화할 수 있는 여러 가지 방법이 있지만 대회에서 한정된 시간 안에 구현하기에는 여러 모로 어려운 경우가 대부분입니다. 다행히 여러 프로그래밍 환경에서 이와 관련된 내장 명령어를 제공합니다. 다음 목록은 32비트 부호 없는 정수 $toppings$ 에 켜진 비트의 수를 구하는 코드를 각 언어 혹은 컴파일러 별로 보여줍니다.

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

이 연산들은 다양한 최적화를 이용해 구현되어 있기 때문에 매우 빠릅니다.

최소 원소 찾기

컴파일러나 언어에 포함된 명령어를 이용해 쉽게 수행할 수 있는 작업으로 집합에 포함된 가장 작은 원소를 찾는 것이 잇습니다. 이 연산은 "이 정수의 이진수 표현에서 끝에 붙어 있는 0이 몇 개인가?"의 형태로 지원됩니다. 켜져 있는 최하위 비트 밑의 비트들은 전부 0일테니, 이 연산은 켜져 있는 최하위 비트의 번호를 반환하게 됩니다. 다음 목록은 32비트 부호 없는 정수 $toppings$ 에서 켜져 있는 최하위 비트의 위치를 구하는 코드를 각 언어 혹은 컴파일러 별로 보여줍니다.

컴파일러 혹은 언어	최소 원소 찾기
gcc/g++	__builtin_ctz(toppings)
Visual C++	_BitScanForward(&index, toppings)
Java	Integer.numberOfTrailingZeros(toppings)

이 연산들 역시 대개 CPU 명령어로 곧장 치환되거나, 다양한 최적화가 적용된 코드를 사용하기 때문에 굉장히 빠릅니다.
최하위 비트의 번호 대신 해당 비트를 직접 구하고 싶으면 어떻게 할까요? 예를 들어 40이 주어질 경우 $3$ 대신 $2^3$ 을 구하는 것이죠. 비트의 위치를 구한 뒤 1을 그만큼 왼쪽으로 시프트해도 되겠지만, 이것을 좀더 간단하게 하는 방법이 있습니다.

int firstTopping = (toppings & -toppings);

이것은 대부분의 컴퓨터가 음수를 표현하기 위해 2의 보수를 사용한다는 점을 이용합니다. 이 기법은 펜윅 트리에서 유용하게 사용됩니다.

최소 원소 지우기

종종 최소 원소가 무엇인가와 상관 없이 최소 원소를 지우는 연산이 유용할 때가 있습니다. 다음 코드가 이 방법을 보여줍니다.

toppings &= (toppings - 1);

최소 원소를 얻은 뒤, 그 원소를 지우는 것보다 훨씬 간결합니다.
이 방법은 어떤 정수가 2의 거듭제곱 값인지 확인할 대도 유용하게 쓰입니다. 2의 거듭제곱 값들의 이진수 표현에는 켜진 비트가 하나밖에 없기 때문에, 최하위 비트를 지웠을 때 0이 된다면 주어진 수는 2의 거듭제곱입니다.

모든 부분 집합 순회하기

비트마스크를 사용할 때 매우 유용한 점은 주어진 집합의 모든 부분 집합을 순회할 수 있다는 것입니다. 다음 코드를 봅시다.

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

이 코드는 어떻게 동작할까요? 다음 부분 집합을 구하는 식 $(subset-1)\&pizza$ 를 눈여겨 봅시다. $subset$ 에서 1을 빼면 켜져 있던 최하위 비트가 꺼지고, 그 밑의 비트들은 전부 켜지게 됩니다. 이 결과와 $pizza$ 의 교집합을 구하면 그 중 $pizza$ 에 속하지 않는 비트들은 모두 꺼지게 됩니다. 이 연산을 반복하면 $pizza$ 의 모든 부분 집합을 방문할 수 있을 겁니다. for문은 $subset=0$ 인 시점에서 종료하므로 공집합은 방문하지 않는다는 점을 잊으면 안됩니다.
만약 불린 값 배열을 통해 이 일을 하려고 한다면 재귀 함수를 작성해야 하지만, 위 코드가 훨씬 간단합니다.

비트마스크의 응용 예제

지수 시간 동적 계획법

배열 입력을 갖는 함수를 메모이제이션하는 방법을 다룬 적 있다면 이미 동적 계획법 알고리즘을 구현하기 위해 비트마스크를 사용한 경험이 있을 것입니다. 배열 대신 정수로 집합을 표현하면 이것을 곧장 배열의 인덱스로 쓸 수 있기 때문에 메모이제이션의 구현 또한 훨씬 간단해집니다.

에라토스테네스의 체

에라토스테네스의 체는 굉장히 빠르게 동작하기 때문에, 수행 범위를 늘릴 때 부담이 되는 것은 수행 시간보다는 메모리였습니다. 체를 구현할 때는 범위 내의 각 정수가 지워졌는지 여부를 저장해야 하는데, 여기에선 이것을 불린 값 배열을 이용해 표현했습니다. 32비트 정수가 표현할 수 있는 범위 내의 모든 수에 대해 체를 수행한다고 합시다. 불린 값 배열을 이용하면 4기가바이트의 메모리를 써야하므로 많은 양의 메모리를 사용해야 합니다. 짝수를 제외해도 2기가바이트라 여전히 많습니다. 이때 비트마스크를 사용하면 메모리 사용량을 8분의 1로 줄일 수 있습니다.
MAX_N개의 원소를 갖는 불린 값 배열을 다음과 같은 배열로 대체합시다.

unsigned char sieve[(MAX_N + 7) / 8];

이 배열은 $\lceil{MAX\_N \over 8}\rceil$ 바이트만을 써서 MAX_N개의 원소를 갖는 불린 값 배열을 구현합니다. 이때 $k$ 번 원소가 참인지를 알기 위해서는 k/8번째 원소의 k%8번째 비트가 켜져 있는지를 확인하면 됩니다. 아래 코드는 비트마스크를 이용하는 에라토스테네스의 체의 구현을 보여줍니다. 정수를 오른쪽으로 3비트 시프트하는 것은 8로 나누는 것과 같고, 7과 AND 연산하는 것은 8로 나눈 나머지를 구하는 것과 같습니다.

int n;
unsigned char sieve[(MAX_N + 7) / 8];
// k가 소수인지 확인한다.
inline bool isPrime(int k) {
    return sieve[k >> 3] & (1 << (k & 7));
}
// k가 소수가 아니라고 표시한다.
inline void setComposite(int k) {
    sieve[k >> 3] &= ~(1 << (k & 7));
}
// 비트마스크를 사용하는 에라토스테네스의 체의 구현
// 이 함수를 수행하고 난 뒤, isPrime()을 이용해 각 수가 소수인지 알 수 있다.
void eratosthenex() {
    memset(sieve, 255, sizeof(sieve));
    setComposite(0);
    setComposite(1);
    int sqrtn = int(sqrt(n));
    for (int i = 2; i <= sqrtn; i++) 
        // 이 수가 아직 지워지지 않았다면
        if (isPrime(i))
            // i의 배수 j들에 대해 isPrime[j]=false로 둔다.
            // i*i 미만의 배수는 이미 지워졌으므로 신경 쓰지 않는다.
            for (int j = i * i; j <= n; j += i)
                setComposite(j);
}

15 퍼즐 상태 표현하기

표현해야 하는 값의 범위가 작을 때는 2비트나 3비트씩 묶어서 배열로 쓸 수도 있습니다. 15퍼즐의 상태는 0부터 15까지의 숫자가 들어있는 4 $\times$ 4 크기의 배열로 표현할 수 있습니다. 각 숫자는 4비트로 표현할 수 있고, 16개의 숫자가 있기 때문에 비트마스크를 사용하면 이 배열 전체를 64비트 정수 하나로 표현할 수 있습니다.
아래 코드는 64비트 부호 없는 정수를 배열로 다루기 위한 함수들의 구현을 보여줍니다.

typedef unsigned long long uint64;
// mask의 index 위치에 쓰인 값을 반환한다.
int get(uint64 mask, int index) {
    return (mask >> (index << 2) & 15;
}
// mask의 index 위치를 value로 바꾼 결과를 반환한다.
uint64 set(uint64 mask, int index, uint64 value) {
    return mask & ~(15LL << (index << 2) | (value << (index << 2));
}

O(1) 우선순위 큐

우선순위 큐에 자료를 추가하거나 삭제하는 작업에는 $N$ 개의 원소가 있을 때 $O(\log N)$ 의 시간이 걸립니다.
하지만 비트마스크를 이용하면 모든 작업을 $O(1)$ 에 할 수 있는 우선순위 큐를 만들 수 있습니다. 예를 들어 우리가 큐에 넣는 원소의 우선순위가 1 이상 140 이하의 정수라고 합시다. 각 우선순위를 갖는 원소들을 담는 140개의 큐를 만들고, 각 큐에 원소가 있는지 여부를 비트마스크로 표현합시다. 140개의 불린 값을 64비트 정수 세 개에 저장하면 첫 번째 비트를 찾는 연산을 이용해 가장 우선순위가 높은 원소가 어디에 있는지를 쉽게 찾을 수 있습니다. 이와 같은 우선순위 큐는 실제로 리눅스 커널의 프로세스 관리를 위해 사용된 적 있습니다.

예제: 극대 안정 집합

$N(N\le20)$ 개의 화학 물질을 운반해야 한다고 합시다. 각 화학 물질은 무해하지만, 같이 두었을 때 서로 반응해 폭발하는 물질들이 있습니다. 이때 한 상자에 넣어도 폭발하지 않는 물질의 집합을 안정적이라고 부릅시다.
물질을 하나라도 추가하면 폭발이 일어나는 집합들을 극대 안정 집합이라고 부릅니다.
각 화학 물질의 정보가 주어질 때 극대 안정 집합의 수를 세는 코드를 작성해봅시다. 이것을 푸는 좋은 방법은 한 개의 물질을 갖는 모든 집합으로부터 시작해서 그래프의 탐색 알고리즘을 사용해 모든 안정 집합을 만들어 나가는 것입니다. 이 탐색 과정에서 더이상 물질을 추가할 수 없는 집합의 수를 반환하면 되지요. 하지만 이 문제에서는 입력의 크기가 그렇게 크지 않기 때문에 좀더 비효율적이라도 짧은 코드를 작성하고 싶습니다. 그러니 비트마스크를 사용해 이 문제를 풀어 봅시다.
비트마스크를 제일 먼저 적용할 수 있는 곳은 어떤 집합이 안정적인지를 판단하는 코드입니다. 이 코드를 구현하는 쉬운 방법은 모든 쌍의 물질에 대해 이 둘을 같이 뒀을 때 폭발하지 않는지 확인하는 것입니다. 이를 위해 중첩 for문이 필요합니다. 반면 각 물질에 대해 같이 뒀을 때 폭발하는 물질의 집합을 비트마스크에 저장해 두면 아래 코드의 $isStable()과 같이 for문 하나로 이 코드를 짤 수 있습니다.

static int n;
// explodes[i]는 i와 같이 두었을 때 폭발하는 물질 집합의 비트마스크 표현
static int[] explodes;
// 주어진 집합이 안정적인지 확인한다.
static boolean isStable(int set) {
    for (int i = 0; i < n; i++)
        // 집합에 포함된 i번째 원소와 같이 두었을 때 폭발하는 물질이 set에 있다면
        if (((set & (1 << i)) & (set & explodes[i])) > 0)
            return false;
    return true;
}
// 모든 극대 안정 집합의 수를 센다.
static int countStableSet() {
    int result = 0;
    // 모든 집합을 만들어 보자.
    for (int set = 1; set < (1 << n); set++) {
        // 우선 안정적이 아니라면 셀 필요가 없다.
        if (!isStable(set)) continue;
        // 극대 안정 집합인지 확인하기 위해, 넣을 수 있는 다른 물질이 있나 확인한다.
        boolean canExtend = false;
        for (int add = 0; add < n; add++)
            // add가 집합에 포함되어 있지 않고, set에 add를 넣어도 안정적이라면
            if ((set & (1 << add)) == 0 && (explodes[add] & set) == 0) {
                canExtend = true;
                break;
            }
        if (!canExtend)
            result++;
    }
    return result;
}

이렇게 하고 나면 $2^N$ 개의 모든 집합을 전부 만들어 보면서 각 집합이 안정적인지, 안정적이라면 다른 물질을 추가할 수 있는지 확인하는 알고리즘을 간단하게 작성할 수 있습니다. 어떤 안정 집합에 다른 원소 $add$ 를 넣을 수 있는지를 $isStable()$ 를 다시 호출하는 대신 $explodes[add]\&set$ 이 0인지만 확인하는 것을 눈여겨보세요.

참고문헌: 구종만, 프로그래밍 대회에서 배우는 알고리즘 문제해결전략, 인사이트, (2012)

지식 저장소

그리디하게 살자.

다음 포스트