비트 조작(Bit Manipulation)은 정수의 이진 표현을 비트 연산자로 직접 조작해 빠르고 메모리 효율적인 연산을 수행하는 기법이다. 암호학, 그래픽스, 임베디드 시스템에서 핵심적으로 사용된다.
기본 비트 연산자
| 연산자 | 기호 | 예시 | 결과 |
|---|
| AND | & | 0b1010 & 0b1100 | 0b1000 |
| OR | | | 0b1010 |
| XOR | ^ | 0b1010 ^ 0b1100 | 0b0110 |
| NOT | ~ | ~0b1010 | 0b0101... |
| 왼쪽 시프트 | << | 1 << 3 | 8 |
| 오른쪽 시프트 | >> | 8 >> 2 | 2 |
자주 쓰는 트릭
python
n = 13 # 0b1101
# 특정 비트 확인
def get_bit(n, i): return (n >> i) & 1
get_bit(13, 2) # 1 (2번째 비트)
# 특정 비트 설정
def set_bit(n, i): return n | (1 << i)
# 특정 비트 제거
def clear_bit(n, i): return n & ~(1 << i)
# 2의 거듭제곱 판별
def is_power_of_2(n): return n > 0 and (n & (n-1)) == 0
is_power_of_2(16) # True (0b10000 & 0b01111 = 0)
# 홀짝 판별
n & 1 == 0 # 짝수
# 최하위 1비트 추출
n & (-n)
# XOR로 중복 없는 원소 찾기
nums = [1,2,1,3,2]
result = 0
for n in nums: result ^= n
print(result) # 3 (유일한 원소)
python
# 방문 상태를 비트로 관리 (TSP 등)
visited = 0b0000 # 4개 도시 방문 여부
visited |= (1 << 0) # 도시 0 방문
visited |= (1 << 2) # 도시 2 방문
# visited = 0b0101
# 전체 방문 확인
all_visited = (1 << 4) - 1 # 0b1111
visited == all_visited # False
관련 개념
참고문헌
- •Hacker's Delight — Henry S. Warren Jr.
