비트 연산 기법

비트 연산이란

비트 연산(bit manipulation)은 정수를 비트의 나열로 보고 자리별로 논리 연산을 하는 기법이다. 연산 하나가 CPU 명령 하나라 빠르고, 정수 하나에 참·거짓 여러 개를 담을 수 있어 메모리도 적게 쓴다. 저수준 시스템 코드, 해시 함수, 플래그 묶음, 그리고 상태를 정수로 압축하는 알고리즘에서 쓴다. 음수가 비트로 어떻게 표현되는지는 데이터의 표현의 2의 보수 절에 있다.

연산자	이름	규칙	예 (`a = 0b1100`, `b = 0b1010`)
`&`	AND	둘 다 1이면 1	`0b1000`
`\|`	OR	하나라도 1이면 1	`0b1110`
`^`	XOR	서로 다르면 1	`0b0110`
`~`	NOT	모든 비트 반전. 2의 보수에서 `~x == -x - 1`	`~12 == -13`
`<<`	왼쪽 시프트	비트를 왼쪽으로 밀고 0을 채운다	`1 << 3 == 8`
`>>`	오른쪽 시프트	비트를 오른쪽으로 민다	`12 >> 2 == 3`

자주 쓰는 관용구

목적	코드	설명
k번째 비트가 1인가	`(n >> k) & 1` 또는 `n & (1 << k) != 0`	파이썬·C에서 `&`가 `!=`보다 우선순위가 낮으므로 `(n & (1 << k)) != 0`처럼 괄호를 친다
k번째 비트 켜기	`n \|= 1 << k`
k번째 비트 끄기	`n &= ~(1 << k)`
k번째 비트 뒤집기	`n ^= 1 << k`
2ᵏ 곱하기·나누기	`n << k`, `n >> k`	음수의 `>>`는 0 쪽이 아니라 음의 무한대 쪽으로 내림한다(`-7 >> 1 == -4`)
2의 거듭제곱인가	`n > 0 and n & (n - 1) == 0`	2의 거듭제곱은 1비트가 하나뿐이다. `n - 1`은 그 비트를 끄고 아래를 모두 1로 만든다. 0을 따로 걸러야 한다
최하위 1비트만 남기기	`n & -n`	2의 보수에서 `-n == ~n + 1`이라 가장 낮은 1비트만 겹친다. 펜윅 트리의 인덱스 이동에 쓴다
최하위 1비트 지우기	`n & (n - 1)`	반복하면 1비트 개수만큼 돈다(브라이언 커니핸 방법)
1비트 개수(popcount)	Python 3.10+ `n.bit_count()`, Java `Integer.bitCount(n)`, C++20 `std::popcount(n)`	하드웨어 명령으로 처리된다
10진수 ↔ 2진수	Python `bin(n)`, `int(s, 2)`. JavaScript `n.toString(2)`, `parseInt(s, 2)`. Java `Integer.toBinaryString(n)`, `Integer.parseInt(s, 2)`	직접 구현하면 2로 나눈 나머지를 모아 뒤집는다

XOR의 성질

XOR는 a ^ a = 0, a ^ 0 = a이고 교환·결합 법칙이 성립한다. 그래서 짝을 이룬 값은 서로 지워진다.

한 번만 나온 수 찾기: 다른 수가 모두 두 번씩 나오면 전체를 XOR한 값이 답이다. 공간 O(1).
빠진 수 찾기: 0~n 중 하나가 빠진 배열이면 0^1^…^n과 배열 전체를 XOR한 값이 빠진 수다. 합 공식(n(n+1)/2 - sum)과 달리 오버플로가 없다.
임시 변수 없는 교환: a ^= b; b ^= a; a ^= b. 다만 a와 b가 같은 메모리를 가리키면 둘 다 0이 되고, 현대 컴파일러에서는 임시 변수를 쓰는 편이 더 빠르다. 원리를 묻는 질문 외에는 쓰지 않는다.

비트마스크로 집합 표현하기

원소가 w개(보통 w ≤ 64) 이하인 집합은 정수 하나로 나타낼 수 있다. i번째 비트가 1이면 i번째 원소가 들어 있다는 뜻이다.

집합 연산	비트 연산
합집합·교집합·차집합	`A \| B`, `A & B`, `A & ~B`
원소 추가·제거·포함 여부	위의 비트 켜기·끄기·검사
원소 개수	popcount
전체 집합	`(1 << w) - 1`

소문자 문자열의 글자 집합은 26비트 마스크 하나로 표현된다. 두 단어가 공통 글자를 가지는지는 마스크를 AND해 0이 아닌지만 보면 되므로, 단어 쌍을 많이 비교하는 문제에서 매번 집합을 만드는 것보다 훨씬 빠르다.

def letter_mask(word):
    mask = 0
    for c in word:
        mask |= 1 << (ord(c) - ord('a'))
    return mask
 
share = letter_mask("apple") & letter_mask("plum") != 0   # True ('p', 'l')

0부터 2ⁿ - 1까지의 정수를 차례로 보면 n개 원소의 모든 부분집합을 훑는다(완전 탐색). 방문한 원소 집합을 상태로 쓰는 외판원 문제 같은 비트마스크 DP도 같은 표현을 쓴다.

언어별 주의점

언어	정수 폭	주의
C·C++·Java	고정 폭(32·64비트)	부호 있는 정수의 오버플로는 C·C++에서 미정의 동작이다(C의 정수 자료형과 형 변환). `1 << 31`은 `int` 범위를 넘으므로 C·C++은 `1LL << 31`·`1ULL << k`, Java는 `1L << 31`처럼 폭을 맞춘다. Java는 부호를 무시하는 `>>>`가 따로 있다
JavaScript	비트 연산 시 32비트 부호 있는 정수로 바꾼다	2³¹ 이상의 수에 `\|`, `&`를 쓰면 값이 잘린다. `x >>> 0`은 부호 없는 32비트로 해석한다. 더 큰 수는 `BigInt`로 다룬다
Python	길이 제한 없는 정수	음수는 왼쪽으로 1이 무한히 이어진 것처럼 동작한다. 32비트 결과를 흉내 내려면 `& 0xFFFFFFFF`로 자르고, 최상위 비트가 1이면 `- (1 << 32)`로 음수로 되돌린다

놓치기 쉬운 경우

음수 입력: 시프트의 반올림 방향, 2의 보수 표현, 언어별 %·>> 결과가 다르다.
오버플로·언더플로: 고정 폭 언어에서 시프트 폭이 정수 폭 이상이면 결과가 정의되지 않는다.
0: 「2의 거듭제곱 판별」, 「최하위 비트」 관용구가 0에서 틀린 답을 낸다.

정리

k번째 비트 검사·켜기·끄기·뒤집기는 1 << k와 &, |, &~, ^의 조합이다.
n & (n - 1)은 최하위 1비트를 지우고, n & -n은 그것만 남긴다.
XOR는 짝을 지운다. 한 번만 나온 수, 빠진 수를 공간 O(1)에 찾는다.
작은 집합은 정수 하나로 표현하고 집합 연산을 비트 연산으로 바꾼다.
정수 폭과 음수 처리는 언어마다 다르니 고정 폭 언어에서는 타입 폭을, 파이썬에서는 마스크를 챙긴다.

버그 제보