비트셋과 비트 압축

번호가 매겨진 집합은 불리언 배열로 나타낼 수 있습니다. 원소 $x$가 집합에 속하면 배열의 $x$번째 원소는 1이 되고, 그렇지 않으면 0이 됩니다.

다양한 집합 연산은 흔히 불리언 배열에 대한 원소별 연산으로 환원할 수 있습니다. 예를 들면 다음과 같습니다.

• 합집합은 비트 OR입니다.
• 집합의 교집합은 비트 단위 AND입니다.
• 대칭 차집합은 비트 단위 XOR(배타적 논리합)입니다.

프로세서는 개별 비트 단위가 아니라, 예를 들어 32비트나 64비트 크기의 블록 단위로 한 번에 작동하도록 설계되어 있습니다. 이 크기를 머신 워드라고 합니다. 따라서 비트 하나만 다루는 연산도 실제로는 int나 long의 모든 비트를 대상으로 하는 연산과 같은 “비용"이 듭니다.

여기서 다음과 같은 최적화 아이디어가 떠오릅니다. 불리언 배열의 원소들을 크기 64의 블록으로 묶고, 각 블록을 64비트 이진수 하나로 표현하는 것입니다. 그러면 해당 비트 연산을 64개의 원소에 한꺼번에 적용할 수 있으며, 이에 드는 비용은 64번이 아니라 프로세서 클록 한 번입니다.

#std::bitset

이 모든 것을 직접 구현하는 것도 어렵지 않지만, STL에는 이미 모든 것이 마련되어 있습니다. bitset은 모든 표준 비트 연산을 지원하는 큰 이진수처럼 동작하는 자료구조입니다:

const int lim = 1000;
bitset<lim> b; // создать битсет размера lim (должно быть константой)
b.set();       // заполнить единицами
b.reset();     // заполнить нулями
b.flip();      // заменить единички на нули и наоборот
b.count();     // посчитать число единичек
cout << b;     // вывести бинарную строку
cout << b[42]; // вывести 43-ий (нумерация с нуля, как у массивов) бит "справа"

또한 비트셋에는 모든 비트 연산이 적용됩니다: &, |, ^, ~, <<, >> 및 [operator]= 형태의 변형들입니다.

참고. 비트 압축을 사용하는 알고리즘의 ‘점근적 복잡도’를 흔히 $O(f / 64)$로 표기합니다. 저자는 이러한 표기법을 좋아하지 않는데, 형식적으로는 수치 상수를 약분하여 없앨 수 있고, 무엇보다 아키텍처와 구현에 따라 상수가 달라지기 때문입니다. 대신 이 글에서는 항상 $O(f / w)$로 표기하겠으며, 여기서 $w$는 머신 워드의 크기를 의미합니다.

#배낭 문제

양의 정수 무게 $a_i$를 가진 물건 $n$개와 크기가 $m$인 배낭이 주어집니다. 배낭의 크기를 넘지 않으면서 합이 최대가 되는 물건의 부분집합을 골라야 합니다.

$O(n \cdot m)$의 일반적인 풀이는 다음과 같습니다:

bool dp[m] = {}; // так можно его заполнить нулями
dp[0] = 1;
for (int i = 0; i < n; i++)
    for (int x = m - a[i]; x >= 0; x--)
        dp[x + a[i]] |= dp[x];

…비트 압축을 사용하면 다음과 같이 $O(n \cdot m / w)$까지 빠르게 만들 수 있습니다:

bitset<m> b;
b[0] = 1;
for (int i = 0; i < n; i++)
    b |= b << a[i];

#길이 3인 사이클

인접 행렬로 주어진 $n$개의 정점으로 이루어진 방향 그래프에 길이 3인 사이클이 있는지 알아내야 합니다.

인접 행렬을 비트셋 배열로 감싸면 문제를 $O(n^3 / w)$에 해결할 수 있습니다:

bitset<maxn> g[maxn]; // матрица смежности
for (int a = 0; a < n; a++) {
    for (int b = 0; b < n; b++) {
        if (g[a][b] && (~g[a] & g[b]).any()) {
            // цикл найден
        }
    }
}

벤치마크: CodeForces 서버에서 이 코드는 $n = 5000$일 때 7초 동안 실행됩니다.

#행렬 곱셈

경로의 수를 세는 문제에서는 그래프의 인접 행렬을 $n$제곱한 행렬이 조합적 의미를 가진다는 사실이 자주 사용됩니다. 즉, 행렬 $G^n$의 $a$번째 행과 $b$번째 열이 만나는 위치에는 정확히 $n$번의 이동으로 정점 $a$에서 정점 $b$까지 도달하는 방법의 수가 기록됩니다.

어떤 문제에서는 $a$에서 $b$로 가는 방법의 수를 정확히 알 필요가 없고, $n$번의 이동으로 그곳에 도달할 수 있는지 여부만 알면 충분합니다. 이 경우에는 수의 곱셈 대신 비트 곱셈, 즉 &만으로 충분합니다:

typedef bitset<maxn> t;
typedef array<t, maxn> matrix;

matrix matmul(matrix a, matrix b) {
    matrix c;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (a[i][j])
                c[i] |= b[j];
    return c;
}

#가우스 소거법

때때로 연립 일차방정식을 풀어야 하는 문제가 나옵니다. 사실 그중 대부분은 체 $\mathbb{Z}_2$ 위에서, 즉 “2를 법으로” 풀 수 있습니다.

전구 스위치가 $n$개 있습니다. 활성화된 각 스위치는 $n$개의 전구 중 어떤 부분집합의 상태를 바꿉니다(켜거나 끕니다). 모든 전구의 현재 상태가 알려져 있을 때, 이를 바탕으로 스위치의 상태를 복원해야 합니다.

결국 우리는 다음 연립방정식을 풀어야 합니다:

여기서 $x$는 스위치의 상태이고, $b$는 전구의 상태이며, 비트 $a_{ij}$는 스위치 $i$가 전구 $j$에 영향을 주는지를 나타냅니다.

이 경우 일반적인 가우스 소거법을 상당히 빠르고 간단하게 만들 수 있습니다:

t gauss(matrix a) {
    for (int i = 0; i < n; i++) {
        int nonzero = i;
        for (int j = i+1; j < n; j++)
            if (a[j][i])
                nonzero = j;
        swap(a[nonzero], a[i]);
        for (int j = 0; j < n; j++)
            if (j != i && a[j][i])
                a[j] ^= a[i];
    }
    t x;
    for (int i = 0; i < n; i++)
        x[i] = a[i][n] ^ a[i][i];
    return x;
}

이 코드는 해가 존재하고 유일하다는 조건 아래에서 방정식 $Ax = b$로부터 벡터 $x$를 구합니다. 코드를 간단하게 하기 위해 벡터 $b$가 행렬 $A$의 오른쪽에 덧붙여져 있다고 가정합니다.

#구현 세부 사항

사실 높은 최적화 수준(g++ -O3 -march=native ...)에서는 컴파일러가 결국 SIMD 명령어를 사용하여 64비트가 아닌 256비트 단위의 그룹을 사용하게 됩니다. 그러나 .count()를 구현하는 데 생각할 수 있는 가장 빠른 방법은 각 64비트 수에 대해 차례로 popcnt 명령어를 호출하는 것이므로(GCC에서는 내장 인트린직 __builtin_popcount로 사용할 수 있습니다), 이 메서드는 비트 연산보다 몇 배 느리게 동작합니다.

비트셋 연산은 처음부터 직접 구현하기도 꽤 쉽습니다. 충분히 단순한 본문을 가진 반복문만 있으면 나머지는 컴파일러가 모두 알아서 처리하며, 이 과정에 어떤 흑마법도 필요하지 않습니다.