알고리즘
비트 연산은 정수를 이진 비트로 보고 AND·OR·XOR·시프트로 다루는 기법으로, 집합·플래그·비트마스크 DP를 빠르고 간결하게 표현합니다.
비트 연산(bit manipulation)은 정수를 0과 1의 나열로 보고 AND, OR, XOR, NOT, 시프트로 원하는 비트를 읽고, 켜고, 끄고, 뒤집는 기법입니다. 컴퓨터는 정수를 이진수로, 음수를 2의 보수로 저장하므로 이 연산들은 대개 CPU 명령 하나로 끝납니다. x & -x로 최하위 1비트를 구하고 x & (x - 1)로 그 비트를 지우는 것처럼, 짧은 식 하나가 반복문을 대신하기도 합니다.
비트 연산이 중요한 이유는 원소 20개 남짓의 집합을 정수 하나로 표현해 모든 부분집합을 훑거나, 집합을 상태로 쓰는 비트마스크 DP를 가능하게 하기 때문입니다. 코딩 테스트에는 부분집합 열거, XOR 성질, popcount 문제가 자주 나오고, 실무에서는 파일 권한, 기능 플래그, 서브넷 계산, 해시 테이블, 비트맵 인덱스에 쓰입니다. 다만 Python의 크기 제한 없는 정수, JavaScript의 32비트 변환과 >>>, Java의 >>>, C++의 부호 없는 타입처럼 언어마다 규칙이 달라 주의해야 합니다.
공부는 이진수와 2의 보수를 손으로 바꿔 보는 것에서 시작하는 것이 좋습니다. 이어서 비트 하나를 켜고, 끄고, 뒤집고, 확인하는 네 가지 동작을 익히고, 0부터 2^n - 1까지 마스크를 돌며 부분집합을 출력해 봅니다. 그다음 부분 마스크 열거와 할당 문제, 외판원 문제 같은 비트마스크 DP로 넘어가고, 마지막으로 사용하는 언어의 정수 폭과 시프트 규칙을 확인하면 됩니다.
음수는 모든 비트를 뒤집고 1을 더한 2의 보수로 저장됩니다. 왼쪽 시프트는 2를 곱하고 오른쪽 시프트는 2로 나누며, 언어에 따라 산술 시프트와 논리 시프트가 나뉩니다.
1 << i 마스크와 OR, AND NOT, XOR로 i번 비트를 켜고 끄고 뒤집습니다. x & -x는 최하위 1비트를, x & (x - 1)은 그 비트를 지운 값을 줍니다.
n개 원소의 부분집합은 0부터 2^n - 1까지의 정수와 일대일로 대응하며, 합집합·교집합·차집합이 비트 연산 한 번으로 끝납니다.
켜진 비트 수는 x &= x - 1 반복이나 내장 함수로 셉니다. a ^ a = 0 성질로 짝 없는 값 찾기, 해밍 거리, 그레이 코드를 간단히 풉니다.
popcount는 x &= x - 1로 최하위 1비트를 하나씩 지우며 켜진 비트 수를 셉니다. subsets는 0부터 2^n - 1까지 마스크를 돌며 i번 비트가 켜진 원소를 골라 모든 부분집합을 만듭니다. 마지막 줄은 12 & -12가 최하위 1비트인 4, 12 & 11이 그 비트를 지운 8, x ^ x가 0임을 보여 줍니다. python bit_manipulation.py로 실행합니다.
bit_manipulation.py
def popcount(x: int) -> int:
count = 0
while x:
x &= x - 1 # clear the lowest set bit
count += 1
return count
def subsets(items):
n = len(items)
for mask in range(1 << n):
yield mask, [items[i] for i in range(n) if (mask >> i) & 1]
for mask, chosen in subsets(["a", "b", "c"]):
print(format(mask, "03b"), popcount(mask), chosen)
x = 12
print(x & -x, x & (x - 1), x ^ x) # 4 8 0
python bit_manipulation.py비트 연산 에 관해 묻고, 경험을 나누고, 의견을 주고받는 곳입니다.
아직 토론이 없습니다. 첫 이야기를 시작해 보세요.
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.