개념

비트 연산(bit manipulation)은 정수를 0과 1의 나열로 보고, 그 자리 하나하나를 직접 읽고 바꾸는 기법입니다. CPU는 정수를 원래 이진수로 저장하므로 AND, OR, XOR, 시프트 같은 연산은 대개 명령어 하나로 끝납니다. 그래서 비트 연산은 빠르고 메모리를 적게 쓰며, 집합이나 플래그처럼 "있다/없다"를 여러 개 묶어 다루는 문제를 아주 짧은 코드로 표현하게 해 줍니다. 이 장에서는 이진 표현, 2의 보수, 기본 연산자와 자주 쓰는 용어를 정리합니다.

이진 표현

정수 13은 이진수로 1101입니다. 오른쪽 끝 자리가 0번 비트이고 왼쪽으로 갈수록 번호가 커집니다. i번 비트의 자리값은 2^i이므로 1101은 8 + 4 + 0 + 1 = 13입니다.

가장 오른쪽 비트를 최하위 비트(LSB), 가장 왼쪽의 1을 최상위 비트(MSB)라고 부릅니다. Python에서는 bin(), format(), int(문자열, 2)로 이진 표현을 오갈 수 있습니다.

print(bin(13))             # 0b1101
print(format(13, "08b"))   # 00001101 (8자리로 맞춤)
print(int("1101", 2))      # 13
print((13).bit_length())   # 4: 필요한 비트 수

2의 보수

컴퓨터는 음수를 대부분 2의 보수(two's complement)로 저장합니다. n비트 정수에서 -x는 x의 모든 비트를 뒤집고 1을 더한 값, 즉 ~x + 1입니다. 8비트라면 5는 00000101, -5는 11111011입니다. 이렇게 하면 덧셈 회로 하나로 양수와 음수를 함께 계산할 수 있고, 0의 표현도 하나뿐입니다. n비트 부호 있는 정수의 범위는 -2^(n-1)부터 2^(n-1) - 1까지라서 32비트 int는 -2147483648부터 2147483647까지입니다. 최상위 비트가 1이면 음수로 읽힙니다.

기본 연산자

x << k는 x * 2^k와 같고, 양수에서 x >> k는 x // 2^k와 같습니다. NOT은 2의 보수 때문에 ~x == -x - 1이 됩니다.

a, b = 12, 10
print(a & b, a | b, a ^ b)   # 8 14 6
print(~a)                    # -13
print(3 << 2, 12 >> 2)       # 12 3
print(-12 >> 1)              # -6: 부호를 유지하는 산술 시프트

비트 하나 다루기

i번 비트를 다루는 네 가지 기본 동작은 모두 마스크 1 << i로 만듭니다.

• 켜기(set): x | (1 << i)
• 끄기(clear): x & ~(1 << i)
• 뒤집기(toggle): x ^ (1 << i)
• 확인(test): (x >> i) & 1 또는 (x & (1 << i)) != 0

x = 0b1010
print(bin(x | (1 << 0)))    # 0b1011
print(bin(x & ~(1 << 1)))   # 0b1000
print(bin(x ^ (1 << 3)))    # 0b10
print((x >> 3) & 1)         # 1

언제 쓰는가

• 원소가 20개 남짓인 집합을 정수 하나로 표현하고 모든 부분집합을 훑을 때
• 여러 개의 켜짐/꺼짐 상태(권한, 옵션, 기능 플래그)를 한 값에 담을 때
• 2의 거듭제곱 판별, 홀짝 판별, 나머지 계산(x & (2^k - 1))을 빠르게 할 때
• 짝을 이루는 값 속에서 하나만 다른 값을 찾는 XOR 문제

용어

• 마스크(mask): 관심 있는 비트만 1로 켠 정수입니다. 집합을 나타낼 때는 "비트마스크"라고 부릅니다.
• popcount: 켜진 비트(1)의 개수입니다. 해밍 가중치라고도 합니다.
• 최하위 1비트(lowest set bit): 가장 오른쪽에 있는 1입니다. x & -x로 얻습니다.
• 논리 시프트와 산술 시프트: 오른쪽으로 밀 때 왼쪽을 0으로 채우면 논리, 부호 비트로 채우면 산술 시프트입니다.

언어마다 다른 점

같은 식이라도 언어에 따라 결과가 달라질 수 있습니다. Python 정수는 크기 제한이 없어 1 << 100도 정확하고, 음수는 왼쪽으로 1이 끝없이 이어진 것처럼 다뤄집니다. JavaScript는 비트 연산 전에 숫자를 32비트 부호 있는 정수로 바꾸므로 1 << 31이 음수가 되고, 부호 없이 읽으려면 >>> 0을 씁니다. Java도 int가 32비트라 같은 일이 생기며 >>>로 0을 채우는 시프트를 합니다. C++에서는 부호 없는 타입을 써야 오버플로와 정의되지 않은 동작을 피할 수 있습니다. 자세한 내용은 구현 장과 실무 활용 장에서 다룹니다.

정리

비트 연산은 정수를 비트의 배열로 보고 AND, OR, XOR, NOT, 시프트로 다룹니다. 음수는 2의 보수로 저장되므로 -x == ~x + 1이 성립합니다. 비트 하나를 켜고 끄고 뒤집고 확인하는 네 동작과 마스크라는 생각만 익히면, 이후 장의 부분집합 열거와 비트마스크 DP를 자연스럽게 이해할 수 있습니다.