동작 원리

이 장에서는 작은 예를 손으로 따라가며 비트 연산 기법이 왜 맞는지 확인합니다. 최하위 1비트 x & -x, 1비트 지우기 x & (x - 1), popcount, 비트마스크로 부분집합 열거, 부분 마스크 열거, 비트마스크 DP, XOR 기법을 차례로 봅니다.

x & -x: 최하위 1비트

x = 12라고 합시다. 8비트로 쓰면 00001100입니다. -x는 ~x + 1이므로 다음과 같이 구합니다.

~x에서 최하위 1비트 아래쪽은 모두 1이 되고, 거기에 1을 더하면 받아올림이 그 1비트 자리에서 멈춥니다. 그래서 그 자리만 x와 -x가 함께 1이고 위쪽은 서로 반대, 아래쪽은 모두 0입니다. AND 결과는 최하위 1비트 하나만 남습니다. 펜윅 트리(BIT)가 다음 구간으로 이동할 때 쓰는 연산이 바로 이것입니다.

x & (x - 1): 최하위 1비트 지우기

x - 1은 최하위 1비트를 0으로 바꾸고 그 아래를 모두 1로 바꿉니다. 12 = 1100이면 11 = 1011이고, AND 하면 1000 = 8이 됩니다. 이 성질로 두 가지를 바로 얻습니다.

• 2의 거듭제곱 판별: x > 0 and (x & (x - 1)) == 0
• 켜진 비트 세기(브라이언 커니핸 방법): 0이 될 때까지 지운 횟수가 popcount입니다.

x = 13(1101)에서 popcount를 따라가 봅니다.

반복 횟수가 켜진 비트 수와 같으므로, 비트가 드문 수일수록 빨리 끝납니다.

def popcount(x: int) -> int:
    count = 0
    while x:
        x &= x - 1
        count += 1
    return count

print(popcount(13), popcount(255), (13).bit_count())  # 3 8 3

비트마스크로 부분집합 열거

원소가 n개인 집합 ["a", "b", "c"]의 부분집합은 2^n = 8개이고, 0부터 7까지의 정수와 일대일로 대응합니다. mask의 i번 비트가 1이면 i번 원소를 고른 것입니다.

items = ["a", "b", "c"]
n = len(items)
for mask in range(1 << n):
    chosen = [items[i] for i in range(n) if (mask >> i) & 1]
    print(format(mask, "03b"), chosen)

집합 연산도 정수 연산이 됩니다. 합집합은 OR, 교집합은 &, 차집합은 a & ~b, 원소 i 포함 여부는 (a >> i) & 1입니다.

부분 마스크 열거

어떤 mask의 부분집합만 훑고 싶다면 sub = (sub - 1) & mask를 반복합니다. mask = 1011이면 1011, 1010, 1001, 1000, 0011, 0010, 0001을 거쳐 0에서 끝납니다. 1을 빼면 그 아래가 1로 바뀌고, mask와 AND 하면 mask 밖의 비트가 지워지므로 "mask 안에서 하나 작은 수"로 내려가는 셈입니다.

mask = 0b1011
sub = mask
while True:
    print(format(sub, "04b"))
    if sub == 0:
        break
    sub = (sub - 1) & mask

비트마스크 DP 맛보기

상태에 "지금까지 고른 원소의 집합"이 들어가면 그 집합을 정수로 바꿔 배열 인덱스로 씁니다. 예를 들어 n명에게 n개의 일을 하나씩 맡길 때 비용 합의 최솟값은, dp[mask] = mask에 든 일을 앞의 popcount(mask)명에게 배정한 최소 비용으로 정의하면 됩니다. 다음 사람 번호가 popcount(mask)로 정해지므로 상태가 2^n개뿐이고, 각 상태에서 아직 안 맡긴 일 n개를 시도해 O(2^n * n)에 풀립니다. 자세한 코드는 연습 문제 장에서 다룹니다.

XOR 기법

XOR은 a ^ a == 0, a ^ 0 == a이고 교환·결합 법칙이 성립합니다. 그래서 모든 값이 두 번씩 나오고 하나만 한 번 나오는 목록을 전부 XOR 하면 짝은 사라지고 그 하나만 남습니다. [4, 1, 2, 1, 2]는 4 ^ 1 ^ 2 ^ 1 ^ 2 = 4입니다.

from functools import reduce

print(reduce(lambda a, b: a ^ b, [4, 1, 2, 1, 2]))   # 4
a, b = 0b1100, 0b1010
print(bin(a ^ b), (a ^ b).bit_count())              # 0b110 2: 서로 다른 비트 수(해밍 거리)

정리

x & -x는 최하위 1비트를 남기고, x & (x - 1)은 그것을 지웁니다. 0부터 2^n - 1까지의 정수는 n개 원소의 모든 부분집합이고, (sub - 1) & mask는 부분 마스크를 차례로 내려갑니다. 이 몇 가지 동작이 비트마스크 DP와 XOR 문제의 바탕입니다.