복잡도

비트 연산 하나는 기계어 명령 하나이므로 고정 폭 정수에서는 O(1)입니다. 복잡도가 문제가 되는 것은 연산을 몇 번 반복하느냐, 그리고 마스크가 표현하는 상태가 몇 개냐입니다. 이 장에서는 popcount 방법별 비용, 부분집합 열거와 부분 마스크 열거의 비용, 비트마스크 DP의 한계를 정리합니다.

기본 연산

w비트 정수에서 AND, OR, XOR, NOT, 시프트, x & -x, x & (x - 1)은 모두 O(1) 시간, O(1) 공간입니다. Python 정수는 크기 제한이 없어서 엄밀히는 자릿수 b에 비례하는 O(b)가 걸리지만, 64비트 안쪽 값이라면 사실상 상수로 봐도 됩니다.

popcount 방법 비교

def popcount_swar(x: int) -> int:
    # 32비트 부호 없는 값 전용
    x = x - ((x >> 1) & 0x55555555)
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0F0F0F0F
    return ((x * 0x01010101) & 0xFFFFFFFF) >> 24

assert all(popcount_swar(v) == v.bit_count() for v in (0, 1, 255, 2**32 - 1, 0xDEADBEEF))

0부터 n까지 모든 수의 popcount가 필요하면 bits[i] = bits[i >> 1] + (i & 1)로 O(n)에 채울 수 있습니다.

부분집합 열거

원소가 n개면 마스크는 2^n개입니다. 각 마스크에서 n개 비트를 모두 확인하면 O(2^n * n) 시간이 듭니다. 부분집합을 리스트로 모아 두면 공간도 O(2^n * n)이지만, 제너레이터처럼 하나씩 처리하면 O(n)이면 됩니다. 대략적인 한계는 다음과 같습니다.

부분 마스크 열거와 3^n

모든 mask에 대해 그 부분 마스크를 훑는 이중 반복은 O(4^n)처럼 보이지만 실제로는 O(3^n)입니다. 각 원소는 "mask에 없음", "mask에만 있음", "sub에도 있음" 세 상태 중 하나이기 때문입니다. n = 15면 3^15는 약 1,400만이라 충분히 돌릴 수 있습니다.

n = 4
pairs = 0
for mask in range(1 << n):
    sub = mask
    while True:
        pairs += 1
        if sub == 0:
            break
        sub = (sub - 1) & mask
print(pairs, 3 ** n)   # 81 81

크기가 정해진 부분집합

크기 k인 부분집합만 필요할 때 2^n개 마스크를 모두 돌며 popcount로 거르면 여전히 O(2^n)입니다. 조합 수 C(n, k)가 2^n보다 훨씬 작다면 itertools.combinations처럼 조합만 직접 만드는 편이 O(C(n, k) * k)로 빠릅니다. 마스크 형태가 꼭 필요하면 고스퍼의 방법(Gosper's hack)으로 popcount가 같은 다음 마스크를 O(1)에 구할 수 있습니다.

def next_same_popcount(x: int) -> int:
    low = x & -x
    ripple = x + low
    return (((ripple ^ x) >> 2) // low) | ripple


mask, n = 0b0011, 4
while mask < (1 << n):
    print(format(mask, "04b"), end=" ")   # 0011 0101 0110 1001 1010 1100
    mask = next_same_popcount(mask)

비트마스크 DP

상태 수가 2^n이고 상태마다 n가지 전이를 보면 O(2^n * n), 외판원 문제처럼 상태가 (집합, 마지막 정점)이면 O(2^n * n^2) 시간과 O(2^n * n) 공간입니다. n = 20인 외판원 문제는 약 4억 번의 연산이라 C++에서는 가능하지만 Python에서는 어렵습니다. 모든 순열을 보는 O(n!)과 비교하면 n = 15에서 1.3조 대 약 740만으로 차이가 큽니다.

import math
for n in (10, 15, 20):
    print(n, math.factorial(n), (1 << n) * n * n)

다른 표현과 비교

정리

비트 연산 자체는 O(1)이고, 비용은 반복 횟수와 상태 수에서 나옵니다. 부분집합 열거는 O(2^n * n), 모든 부분 마스크 쌍은 O(3^n), 비트마스크 DP는 보통 O(2^n * n)이나 O(2^n * n^2)입니다. 그래서 비트마스크 기법은 n이 대략 20 안팎일 때 빛나고, 그보다 크면 다른 접근을 찾아야 합니다.