흔한 비트 조작(bit-manipulation) 기법은 무엇인가요?

Question

Accepted Answer

**비트 조작(Bit manipulation)**은 AND, OR, XOR, NOT, 시프트를 사용하여 정수의 이진 표현을 직접 다룹니다. 간결하고 분기 없는 매우 빠른 연산을 가능하게 합니다. ## 핵심 연산 ```python x & 1 # x가 홀수인가? (최하위 비트) x << 1 # 2를 곱함 x >> 1 # 2로 정수 나눗셈 x & (1 << k) # 비트 k가 설정되어 있는가? x | (1 << k) # 비트 k 설정 x & ~(1 << k) # 비트 k 해제 x ^ (1 << k) # 비트 k 토글 ``` ## 유용한 기법 ```python x & (x - 1) # 최하위 설정 비트를 지움 x & (x - 1) == 0 # x가 2의 거듭제곱인가? (x>0) x & (-x) # 최하위 설정 비트를 분리 bin(x).count('1') # popcount (설정된 비트의 개수) ``` ## 예시: 단 하나의 수 찾기 (XOR 기법) ```python def single_number(nums): result = 0 for n in nums: result ^= n # 쌍은 상쇄됨: a ^ a == 0 return result # 짝 없는 단 하나의 값만 남음 single_number([4, 1, 2, 1, 2]) # -> 4 ``` ## 복잡도 비트 연산은 O(1)입니다. 위의 XOR 순회는 **O(n) 시간, O(1) 공간**입니다. ## 언제 사용하나 / 함정 **비트마스크**(부분집합 열거, 상태에 대한 DP), 플래그, 빠른 연산, 저수준/임베디드 코드에 사용하세요. 부호 비트, 언어별 시프트 동작, 가독성을 주의하세요 — 명확하지 않은 기법에는 주석을 다세요. ## 왜 중요한가 비트 조작은 면접에서 놀라움을 주는 우아한 O(1) 공간 해법(XOR 단일 수 기법 같은)을 만들어 냅니다. 비트마스크 DP는 많은 조합적 상태 공간 문제를 다룰 수 있게 만듭니다. 매 사이클이 중요한 시스템, 그래픽, 압축, 성능이 중요한 코드에서 필수적입니다.