비트 조작 쉽게 이해하기: 연산자, 요령, 예제

비트 조작이 해결하는 문제

정수는 비트의 나열이며, 많은 문제가 사실 그 비트에 관한 것입니다. rwx 같은 파일 권한, 기능 플래그, 네트워크 마스크, 픽셀 색상, 옵션의 압축된 집합, 체크섬과 해시가 그렇습니다. 비트 연산자를 쓰면 여러 비트를 한 번의 연산으로 읽고 바꿀 수 있어 메모리를 적게 쓰고 매우 빠릅니다.

코딩 인터뷰에서도 비트 요령이 자주 나오는데, 다른 모든 수가 두 번씩 나올 때 한 번만 나오는 수를 찾는 것처럼 우아한 O(1) 공간 풀이를 주기 때문입니다.

연산자

예제에서는 a = 12(이진수 1100)와 b = 10(이진수 1010)을 사용합니다.

a, b = 12, 10
print(bin(a), bin(b))         # 0b1100 0b1010
print(a & b, a | b, a ^ b)    # 8 14 6
print(~a, a << 1, a >> 2)     # -13 24 3
print(f"{a ^ b:04b}")         # 0110
print(int("1010", 2))         # 10

단일 비트 연산

비트 위치는 오른쪽 끝(최하위 비트)을 0으로 해서 셉니다. 마스크 1 << i는 i번째 비트만 켜져 있습니다.

예제: 켜진 비트 세기

브라이언 커니핸(Brian Kernighan)의 방법은 남은 것이 없을 때까지 가장 낮은 켜진 비트를 지우므로, 비트 위치마다가 아니라 1인 비트마다 한 번씩 반복합니다. x = 44(이진수 101100)의 추적입니다.

def count_bits(x):
    count = 0
    while x:
        x &= x - 1        # drop the lowest set bit
        count += 1
    return count

print(count_bits(44))     # 3
print((44).bit_count())   # 3
print((44).bit_length())  # 6

int.bit_count()는 파이썬 3.10부터 사용할 수 있습니다. int.bit_length()는 부호를 제외하고 수를 이진수로 쓰는 데 필요한 비트 수를 반환합니다.

파이썬에서 자주 쓰는 요령

from functools import reduce
from operator import xor

# Every number appears twice except one: pairs cancel out with XOR.
print(reduce(xor, [4, 1, 2, 1, 2]))   # 4

# Swap two integers without a temporary variable (for illustration only).
x, y = 5, 9
x ^= y; y ^= x; x ^= y
print(x, y)                            # 9 5

# Bitmask as a set: enumerate all subsets of 3 items.
items = ["a", "b", "c"]
for mask in range(1 << len(items)):
    print(mask, [items[i] for i in range(len(items)) if mask >> i & 1])
# 0 []
# 1 ['a']
# 2 ['b']
# 3 ['a', 'b']
# 4 ['c']
# 5 ['a', 'c']
# 6 ['b', 'c']
# 7 ['a', 'b', 'c']

마스크 0은 공집합, 5(이진수 101)는 ['a', 'c'], 7은 세 항목 전체입니다. 비트마스크 동적 계획법은 마스크를 상태로 사용하는 같은 아이디어이며, 작은 입력에 대한 외판원 문제처럼 최대 20개 정도의 항목을 다루는 문제에 쓰입니다.

고전적인 요령 두 가지가 더 있습니다. x & 1은 홀수에서 1이고, 0부터 n까지의 모든 수와 리스트의 모든 값을 XOR하면 빠진 수 하나를 찾을 수 있습니다.

시간 복잡도와 공간 복잡도

비트마스크는 가능한 원소마다 비트 하나를 사용하므로, 64개의 불리언 변수나 리스트 항목 대신 64개의 플래그 집합이 64비트 정수 하나에 들어갑니다.

흔한 실수

• 음수: 파이썬 정수는 부호 비트가 무한히 많은 것처럼 동작하므로 ~5는 -6이고 bin(-5)는 2의 보수 문자열이 아니라 -0b101입니다. 32비트 패턴을 보려면 값을 마스크하세요. -5 & 0xFFFFFFFF.
• 파이썬에서 음수의 오른쪽 시프트는 산술 시프트입니다. -8 >> 1은 -4이고 -1 >> 10은 여전히 -1입니다.
• 고정 폭 언어에서의 오버플로: Java나 C에서 32비트 int의 1 << 31은 음수가 되거나 정의되지 않은 동작이 됩니다. 64비트 타입을 사용하고 1L << 40 또는 1ULL << 40을 쓰세요.
• 논리 연산자와 비트 연산자 혼동: and와 or(C 계열 언어에서는 &&, ||)는 참/거짓 값을 반환하지만 &와 |는 비트 단위로 동작합니다.
• 가독성: x * 2를 x << 1로 바꿔도 최신 컴파일러나 파이썬에서는 속도 이점이 없고 코드를 읽기 어렵게 만들 뿐입니다.

실제 활용

• 유닉스 파일 권한: chmod 754는 3비트 그룹 세 개를 설정합니다(rwx = 4 + 2 + 1).
• 네트워킹: IPv4 서브넷 마스크에서 ip & mask는 CIDR 블록의 네트워크 주소를 줍니다.
• 플래그와 옵션: 파이썬의 re.IGNORECASE | re.MULTILINE과 enum.Flag는 OR로 옵션을 결합합니다.
• 그래픽과 색상: 24비트 RGB 값은 빨강, 초록, 파랑을 (r << 16) | (g << 8) | b로 묶습니다.
• 자료구조와 알고리즘: 블룸 필터, 비트셋, 펜윅 트리(i & -i 사용), 해싱과 체크섬.
• 코딩 인터뷰 문제: 하나만 있는 수, 비트 세기, 2의 거듭제곱, 비트 뒤집기, 빠진 수, 비트마스크로 부분집합 구하기, + 없이 두 정수 더하기.