비트 조작: 1과 0으로 생각하기

"모든 정수 밑에는 비트 한 줄이 깔려 있어. 고정 폭 기계 정수라면 CPU가 그 줄을 거의 한입에 씹고, 집합 하나를 숫자 하나에 접어 넣을 수도 있어. 다만 Python 정수는 끝없이 커질 수 있어서, 기계 word 여러 개로 넘치는 순간 비용도 비트 길이를 따라 자라. 마법은 진짜야. 다만 한없이 공짜는 아니야."

연산자들

AND, OR, XOR, NOT, 시프트는 이진 표현에 직접 작용해. 고정 폭 정수에서는 흔히 상수 시간 기계어 연산이지만, Python의 임의 정밀도 정수에서는 피연산자의 word 수에 비례할 수 있어. 비트셋도 집합 연산을 word 단위로 병렬화해서 상수를 크게 줄여 주지만, 원소 우주의 크기를 무시한 진짜 O(1)이라고 부르진 마.

알아 둘 가치가 있는 트릭

2의 거듭제곱 확인: n & (n - 1) == 0은 n의 켜진 비트가 정확히 하나일 때, 즉 n이 2의 거듭제곱일 때 참이야. 1을 빼면 가장 낮은 켜진 비트와 그 아래가 전부 뒤집히거든.
켜진 비트 세기, 가장 낮은 비트 지우기: n & (n - 1)이 가장 낮은 켜진 비트를 제거해. 0이 될 때까지 돌리면 켜진 비트 개수가 나와.
XOR의 마법: a ^ a == 0이고 a ^ 0 == a야. 그래서 딱 하나만 빼고 모든 원소가 두 번씩 나타나면, 전부 XOR했을 때 쌍은 상쇄되고 외톨이만 남아. O(n) 시간과 O(1) 공간, 해시 셋도 필요 없어.

비트마스크: 정수 하나에 담는 집합

고정 폭 64비트 정수 하나는 플래그를 64개까지 담을 수 있고, Python 정수는 그보다 많은 비트도 담지만 값이 커질수록 연산 비용이 늘어나. 비트마스크 DP는 부분집합 상태를 정수 하나로 간결하게 인코딩해. '원소 20개쯤까지'라는 기준은 메모리와 시간 제한에서 나온 경험칙이지, 보편적인 경계선이 아니야.

비트 연산(AND, OR, XOR, NOT, 시프트)은 고정 폭 정수에서 흔히 단일 기계어 명령 수준으로 빠르고, 임의 정밀도 정수에서는 비트 길이를 따라 비용이 자라. 핵심 패턴: n AND (n-1)은 가장 낮은 켜진 비트를 지워(2의 거듭제곱 확인, 비트 세기). XOR은 쌍을 상쇄해(O(1) 공간으로 외톨이 찾기). 비트마스크는 집합을 정수 하나에 패킹해서 word 단위 집합 연산과 간결한 DP 상태를 줘.

가독성 주의

비트 트릭은 유혹적이고, 코드를 순식간에 못 읽게 만들 수 있어. 해독에 10분 걸리는 영리한 한 줄은 대개 틀린 선택이야. 비트 조작은 진짜로 중요해질 때 꺼내. 상수 인자가 승부를 가르는 빡빡한 안쪽 루프, 플래그와 권한 집합, 그리고 그게 자연스러운 표현인 비트마스크 DP. 그 밖에서는 명확한 버전을 골라. 동료가, 혹은 미래의 자신이 못 읽는 영리함은 자랑이 아니라 비용이야.

피파의 고백

XOR '외톨이 수 찾기' 트릭은 정말로 날 기쁘게 했어. 전부 XOR하면 쌍이 사라지고 외톨이만 남는데 추가 메모리는 0이라니. 신이 나서 곧장 모든 걸 비트로 주무르려 들었고, 일주일 뒤엔 나조차 못 읽는 '영리한' 한 줄을 쓰고 있었어. 아빠의 교정. "비트 트릭은 메스지 망치가 아니야." 빛나는 자리에 써. 마스크, 플래그, XOR 트릭, 비트마스크 DP. 다른 자리에서는 지루하고 읽기 쉬운 버전을 쓰고.

Code

2의 거듭제곱, XOR 외톨이 수, 비트마스크·python

# 2의 거듭제곱: n & (n-1) 이 가장 낮은 켜진 비트 지움. 0 결과 => 비트 하나.
def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0
print(is_power_of_two(16), is_power_of_two(18))   # True False

# XOR 트릭: 한 개 빼고 모든 수가 두 번 나타남 — O(1) 공간에 찾기.
def single_number(nums):
    result = 0
    for x in nums:
        result ^= x         # 쌍이 상쇄 (a ^ a = 0). 외톨이가 살아남음
    return result
print(single_number([4, 1, 2, 1, 2]))   # 4

# 비트마스크 = 집합: 비트 i 켜짐 = '항목 i 있음'.
mask = 0
mask |= (1 << 2)          # 항목 2 추가  -> 0b100
mask |= (1 << 5)          # 항목 5 추가  -> 0b100100
print(bool(mask & (1 << 2)))   # True  — 항목 2 가 집합에 있어?
print(bool(mask & (1 << 3)))   # False — 항목 3 이 집합에 있어?
# 합집합 = a | b, 교집합 = a & b. 부분집합을 정수 하나에 패킹,
# 정확히 비트마스크 DP 가 '어느 아이템 썼나' 를 상태로 인코딩하는 법.

Exercise

비트 추론만으로 답해 봐. (1) n AND (n-1)이 0이 되는 게 왜 n이 2의 거듭제곱이라는 증명이 돼? n = 8과 n = 12를 이진수로 직접 밟아 봐. (2) 딱 하나만 한 번 나타나고 나머지 값은 정확히 두 번씩 나타나는 리스트에서, 전부 XOR하면 왜 그 고유한 값이 나오고, 왜 추가 메모리가 필요 없어?

Hint

(1) 8 = 1000, 8−1 = 0111, AND = 0000. 켜진 비트가 하나라서 2의 거듭제곱이야. 12 = 1100, 11 = 1011, AND = 1000 ≠ 0. 켜진 비트가 하나를 넘지. (2) XOR은 결합·교환이 가능하고 a^a=0이라 모든 쌍이 0으로 상쇄되고, 외톨이 값만 0과의 XOR로 자기 자신으로 남아. 변수 하나에 누적하니 O(1) 공간이야.

연산자들

알아 둘 가치가 있는 트릭

비트마스크: 정수 하나에 담는 집합

가독성 주의

피파의 고백

Code

External links

Exercise

Progress

댓글 0