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

"모든 정수 아래엔 비트 한 줄이 있고, CPU 가 그걸 다 한 번에, 단일 명령으로 만지작거릴 수 있어. 비트 조작은 알고리즘의 빅오를 안 바꾸지만, 상수를 극적으로 줄이고 집합 전체를 숫자 하나에 패킹할 수 있어."

연산자들

비트 연산은 이진 표현에 직접 작용해: AND (&) 는 양쪽에 켜진 비트를 유지, OR (|) 는 어느 쪽이든 켜진 걸, XOR (^) 는 다른 비트를, NOT (~) 는 모든 비트를 뒤집고, 시프트 (<<, >>) 는 비트를 왼쪽이나 오른쪽으로 밀어 (왼쪽 1 시프트는 2 곱하기). 각각 단일, 번개 같은 CPU 명령. 퀘스트 전체에서 가장 저수준 도구고, 그것들로 지은 패턴 몇 개가 끊임없이 나타나.

알 가치 있는 트릭

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 항목 집합을 나타낼 수 있어, 비트 i 가 1 이면 '항목 i 가 있음'. 그러면 집합 연산이 비트 연산이 돼 — 합집합이 OR, 교집합이 AND, 멤버십이 shift-and-AND, 원소 추가가 시프트한 1 이랑 OR. 간결하고 빠르고, 비트마스크 DP 의 척추야, DP 상태가 '어느 아이템 부분집합을 썼나' 를 정수 하나로 인코딩. ~20 항목이랑 지수 부분집합-상태인 문제가 여전히 메모리에 맞고 돌아가는 법이야.

비트 연산 (AND, OR, XOR, NOT, 시프트) 은 단일 빠른 명령. 핵심 패턴: n AND (n-1) 이 가장 낮은 켜진 비트 지움 (2의 거듭제곱 확인, 비트 세기); XOR 이 쌍 상쇄 (O(1) 공간에 외톨이 원소 찾기); 비트마스크가 집합을 정수 하나에 패킹해 O(1) 집합 연산이랑 간결한 DP 상태.

가독성 주의

비트 트릭은 유혹적이고 코드를 빠르게 못 읽게 만들 수 있어 — 해독에 10분 걸리는 영리한 한 줄은 보통 틀린 선택이야. 진짜 중요할 때 비트 조작에 손대: 상수 인자가 중요한 hot 안쪽 루프, 플래그랑 권한 집합, 또는 그게 자연스러운 표현인 비트마스크 DP. 아니면, 명확한 버전을 선호해. 동료 (또는 미래의 너) 가 못 읽는 영리함은 자랑이 아니라 비용이야.

피파의 고백

XOR '외톨이 수 찾기' 트릭이 진짜 날 기쁘게 했어 — 전부 XOR, 쌍이 사라지고, 외톨이가 남고, 추가 메모리 제로. 곧장 모든 걸 비트 만지작거리려 했고 일주일 뒤 나조차 못 읽는 '영리한' 줄을 썼어. 아빠의 교정: "비트 트릭은 메스지 망치가 아니야." 빛나는 데 써 — 마스크, 플래그, 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