algo · 15

비트 조작 트릭

비트마스크XOR비트연산

비트 조작은 정수를 이진수 비트의 나열로 보고 AND, OR, XOR, NOT, 시프트 같은 연산으로 비트를 직접 다루는 기법입니다. 정수 하나가 비트 수십 개를 담고 있어서, 비트 연산 한 번이 여러 값을 동시에 처리하는 효과를 냅니다. 그래서 짧고 빠른 코드가 나오고, 메모리를 아끼는 데에도 씁니다.

비트 조작의 매력은 몇 가지 관용구(트릭)에 있습니다. n & (n - 1)로 가장 낮은 1을 지우고, XOR로 쌍을 이룬 값을 지우고, 정수 하나로 집합을 표현하는 비트마스크가 대표적입니다. 이 토픽에서는 연산자가 비트에 하는 일, n & (n - 1) 트릭, 비트마스크 집합을 단계별로 봅니다.

핵심 개념

비트 연산자

AND(&)는 둘 다 1일 때, OR(|)은 하나라도 1일 때, XOR(^)은 서로 다를 때 1입니다. NOT(~)은 모든 비트를 뒤집습니다.

핵심 개념

시프트

고정 폭 정수에서 <<는 2의 거듭제곱을 곱한 효과(넘친 비트는 버려짐)를, >>는 2의 거듭제곱으로 내림 나눗셈한 효과를 냅니다.

핵심 개념

n & (n - 1)

n의 가장 낮은 1 하나를 지운 값입니다. n - 1은 가장 낮은 1이 0이 되고 그 아래가 모두 1이 되기 때문에 AND하면 그 부분이 사라집니다.

핵심 개념

2의 거듭제곱 판별

2의 거듭제곱은 1이 하나뿐이라 n & (n - 1)이 0입니다. n이 양수일 때만 이 판별이 맞습니다.

핵심 개념

XOR의 성질

a ^ a = 0이고 a ^ 0 = a이며 교환법칙과 결합법칙이 성립합니다. 그래서 쌍으로 나오는 값은 모두 사라지고 홀로 나온 값만 남습니다.

핵심 개념

비트마스크

정수의 각 비트를 집합의 원소 하나로 대응시킵니다. 추가는 |, 삭제는 & ~, 확인은 &, 토글은 ^로 한 번에 처리합니다.

연산 한 번이 O(1)입니다 — 정수가 한 기계어에 들어가는 크기이면 비트 연산은 값의 비트 수와 상관없이 한 번에 끝납니다. 비트를 하나씩 확인하는 반복문보다 짧고 빠릅니다.

1의 개수를 세는 반복이 1의 개수만큼입니다 — n & (n - 1)을 0이 될 때까지 반복하면 1이 k개인 수는 k번에 끝납니다. 비트를 모두 훑으면 비트 수만큼 반복해야 합니다.

비트마스크는 원소 수에 제한이 있습니다 — C·자바처럼 고정 폭 정수에서는 정수 하나가 담는 비트 수가 한계입니다. 32비트 int는 원소 32개, 64비트 long은 64개까지이고 그 이상은 비트 배열 같은 다른 구조가 필요합니다.

부분집합은 2^n개입니다 — 원소가 n개이면 0부터 2^n - 1까지의 정수가 모든 부분집합에 하나씩 대응해, 반복문 하나로 모두 열거합니다. 원소가 20개이면 약 100만 개입니다.

이 시각화에서 확인할 것 — "비트 연산자" 탭에서 같은 두 수에 연산자를 적용했을 때 자리별로 어떻게 바뀌는지를, "n & (n-1) 트릭" 탭에서 가장 낮은 1이 지워지는 과정을, "비트마스크 집합" 탭에서 비트 하나가 켜지고 꺼질 때 집합이 변하는 모습을 STEP으로 확인하세요.

비트 조작의 배경

컴퓨터는 모든 값을 비트로 저장하므로 비트 연산은 CPU가 명령어로 직접 지원하는 기본 연산입니다. C 언어는 비트 연산자를 언어에 포함했고, 브라이언 커니핸(Brian Kernighan)과 데니스 리치(Dennis Ritchie)의 "The C Programming Language"에는 2의 보수 체계에서 x &= (x - 1)이 x의 가장 오른쪽 1비트를 지우는 이유를 설명하고 이를 이용해 비트 세기를 빠르게 만들라는 연습 문제가 실려 있습니다. 비트 트릭을 모아 놓은 책으로 헨리 워런(Henry S. Warren Jr.)의 "Hacker's Delight"가 널리 알려져 있습니다.

숫자로 확인하기

연산자 — a = 01101010(106), b = 00111100(60)일 때 a & b = 40, a | b = 126, a ^ b = 86입니다. a << 1 = 212로 2배가 되고, a >> 2 = 26은 4로 나눈 몫입니다.

NOT — ~a는 8비트로 보면 10010101(149)이고, 부호 있는 정수에서는 같은 비트가 -107이며 ~x = -x - 1을 만족합니다.

2의 거듭제곱 — 8(1000)은 7(0111)과 AND하면 0이라 2의 거듭제곱입니다. 12(1100)는 11(1011)과 AND하면 8(1000)이 남아 아닙니다.

1의 개수 — 13(1101)은 13 → 12 → 8 → 0으로 세 번 만에 0이 되므로 1이 3개입니다. 12 & -12 = 4처럼 n & -n은 가장 낮은 1만 남깁니다.

비트마스크 — C, E, G를 넣으면 mask = 84(1010100)입니다. E를 확인하면 0이 아니라 있고 D는 0이라 없으며, E를 토글하고 C를 삭제하면 mask = 64로 G만 남습니다.

코드 확인 — 파이썬과 자바가 같은 연산에서 같은 값을 냅니다. 배열 [4, 1, 2, 1, 2]를 모두 XOR하면 4가 남습니다.

자주 하는 오해

괄호 없이 n & (n-1) == 0이라고 써도 된다 — 자바와 C에서는 비교 연산자가 비트 AND보다 우선순위가 높아 n & ((n-1) == 0)으로 묶입니다. 자바에서는 int와 boolean을 AND하는 컴파일 오류가 나고, C에서는 의도와 다르게 계산됩니다. (n & (n-1)) == 0으로 괄호를 쳐야 합니다.

n & (n-1) == 0이면 항상 2의 거듭제곱이다 — n이 0일 때도 0이 되므로 n > 0 조건이 함께 필요합니다.

오른쪽 시프트는 항상 왼쪽을 0으로 채운다 — 부호 있는 정수의 산술 시프트(>>)는 부호 비트로 채웁니다. 자바에서 -8 >> 1은 -4이고, 0으로 채우는 >>>를 쓰면 2147483644가 됩니다.

시프트는 얼마든지 밀어도 된다 — 정수의 비트 수 이상으로 밀면 언어마다 다르게 동작합니다. 자바는 시프트 거리의 하위 비트만 쓰므로 int에서 1 << 32는 1이고, C는 정의되지 않은 동작입니다.

비트마스크는 원소가 몇 개든 쓸 수 있다 — 고정 폭 정수에서는 정수의 비트 수가 한계입니다. 자바에서 원소가 64개를 넘으면 BitSet 같은 구조를 씁니다.

면접에서 이렇게 물어요

면접 질문

정수가 2의 거듭제곱인지 비트로 판별하려면?

n > 0이고 (n & (n - 1)) == 0이면 2의 거듭제곱입니다. 2의 거듭제곱은 1이 하나뿐이고, n - 1은 그 1을 0으로 바꾸고 아래 비트를 모두 1로 만들기 때문입니다.

면접 질문

한 번만 나타나는 원소를 O(n) 시간 O(1) 공간으로 찾으려면?

나머지가 모두 두 번씩 나온다면 모든 원소를 XOR합니다. 같은 값끼리 XOR하면 0이 되고 0과의 XOR은 그대로이므로 한 번 나온 값만 남습니다.

면접 질문

정수에서 1인 비트의 개수는 어떻게 세나요?

n &= n - 1을 n이 0이 될 때까지 반복하며 횟수를 셉니다. 1의 개수만큼만 반복합니다. 자바에는 Integer.bitCount가 있습니다.

면접 질문

집합의 모든 부분집합을 비트로 어떻게 열거하나요?

원소가 n개이면 0부터 (1 << n) - 1까지의 정수 하나하나가 부분집합 하나이고, 정수의 i번 비트가 1이면 i번째 원소가 들어 있습니다.

실제 시스템에서는

플래그 옵션 — 리눅스의 open 시스템 호출은 O_RDONLY | O_CREAT처럼 옵션 비트를 OR로 합쳐 하나의 정수 인자로 전달합니다.

서브넷 마스크 — IP 주소와 서브넷 마스크를 AND하면 네트워크 주소가 나옵니다. 마스크가 어느 비트까지가 네트워크 부분인지를 나타내기 때문입니다.

자바 EnumSet — 내부를 비트 벡터로 표현하고, OpenJDK 구현은 열거형 상수가 64개 이하이면 long 하나를 씁니다(구현 세부).

함께 보면 좋은 토픽

펜윅 트리 — n & -n으로 가장 낮은 1을 쓰는 자료구조를 봅니다.

블룸 필터 — 비트 배열 하나로 집합의 소속 여부를 묻는 구조를 봅니다.

IEEE 754 부동소수점 — 실수가 비트로 저장되는 방식을 봅니다.

서브넷팅 — 서브넷 마스크와 AND 연산을 봅니다.

참고 자료

교재 — Kernighan, B. W. and Ritchie, D. M., "The C Programming Language", 2nd ed., Chapter 2 (연습 문제 2-9)

교재 — Warren, H. S., Jr., "Hacker's Delight", 2nd ed., Addison-Wesley, 2012

공식 문서 — Java Language Specification 15.19 Shift Operators

공식 문서 — Python Bitwise Operations on Integer Types

공식 문서 — Java EnumSet

공식 문서 — Linux open(2)

소스 코드 — OpenJDK RegularEnumSet

표준 문서 — RFC 917 Internet Subnets

Python — 비트 연산자와 대표 트릭

from functools import reduce
from operator import xor

a, b = 0b01101010, 0b00111100               # 106, 60
print(a & b, a | b, a ^ b, a << 1, a >> 2, ~a)
# 40 126 86 212 26 -107

def is_pow2(n):
    return n > 0 and n & (n - 1) == 0      # 가장 낮은 1을 지우면 0

print([is_pow2(n) for n in (8, 12, 1, 0)])   # [True, False, True, False]

def popcount(n):
    c = 0
    while n:
        n &= n - 1                         # 1을 하나씩 지운다
        c += 1
    return c

print(popcount(13), 12 & -12)               # 3 4  (13 = 1101, 12의 가장 낮은 1은 4)
print(reduce(xor, [4, 1, 2, 1, 2]))           # 4  (쌍은 사라지고 하나만 남는다)

AND, OR, XOR, 시프트, NOT은 정수의 각 비트를 한꺼번에 다루는 연산자입니다. 파이썬 정수는 길이 제한이 없고 음수는 무한히 긴 2의 보수로 다루므로 ~106은 -107이 됩니다(~x = -x - 1). n & (n - 1)은 n의 가장 낮은 1 하나를 지운 값입니다. 2의 거듭제곱은 1이 하나뿐이라 지우면 0이 되므로 n이 양수이고 이 값이 0이면 2의 거듭제곱입니다. n > 0을 빠뜨리면 0도 통과하는 점에 주의합니다. 같은 식을 0이 될 때까지 반복하며 횟수를 세면 1의 개수가 나옵니다. 13은 1101이라 세 번에 0이 됩니다. n & -n은 가장 낮은 1만 남기는 식입니다. 음수가 2의 보수로 표현되어 -n이 n의 비트를 반전해 1을 더한 값이기 때문입니다. XOR은 같은 값끼리 0이 되고 0과는 그대로이므로, 한 원소만 한 번 나오고 나머지는 두 번씩 나오는 배열에서 모두 XOR하면 한 번 나온 값이 남습니다. 시각화의 비트 연산자 탭과 n & (n-1) 트릭 탭이 보여 주는 과정과 같습니다.

Python — 비트마스크로 집합 다루기

mask = 0
mask |= 1 << 2                                   # C 추가
mask |= 1 << 4                                   # E 추가
mask |= 1 << 6                                   # G 추가
print(mask, bin(mask), bool(mask & (1 << 4)), bool(mask & (1 << 3)))
# 84 0b1010100 True False

mask ^= 1 << 4                                   # E 토글 (있었으므로 빠진다)
mask &= ~(1 << 2)                                # C 삭제
print(mask)                                      # 64  (G만 남음)

items = ['A', 'B', 'C']
print([[items[i] for i in range(3) if m >> i & 1] for m in range(1 << 3)])
# [[], ['A'], ['B'], ['A', 'B'], ['C'], ['A', 'C'], ['B', 'C'], ['A', 'B', 'C']]

비트마스크는 정수의 각 비트를 집합의 원소 하나로 보는 방법입니다. 원소를 넣을 때는 1 << i를 OR하고, 확인할 때는 mask & (1 << i)이 0이 아닌지 보고, 토글은 XOR, 삭제는 ~(1 << i)와 AND합니다. 위 흐름은 시각화의 비트마스크 집합 탭과 같고 마지막에 G만 남습니다. 원소가 n개이면 부분집합은 2^n개이고, 0부터 (1 << n) - 1까지의 정수가 모든 부분집합에 하나씩 대응합니다. 그래서 range(1 << n)을 도는 반복문 하나로 모든 부분집합을 열거할 수 있고, 원소가 적은 문제에서 상태를 정수 하나로 줄이는 데 자주 씁니다.

Java — 연산자와 시프트의 차이

int a = 106, b = 60;
System.out.println((a & b) + " " + (a | b) + " " + (a ^ b) + " " + (a << 1) + " " + (a >> 2) + " " + (~a));
// 40 126 86 212 26 -107

System.out.println((-8 >> 1) + " " + (-8 >>> 1));
// -4 2147483644   (>> 는 부호 비트로 채우고, >>> 는 0으로 채운다)

System.out.println(Integer.bitCount(13) + " " + Integer.toBinaryString(106));
// 3 1101010

int n = 8;
System.out.println(n > 0 && (n & (n - 1)) == 0);     // true  (괄호가 꼭 필요하다)

자바의 비트 연산자도 같은 방식으로 동작하지만 int는 32비트로 고정되어 있습니다. 오른쪽 시프트는 두 가지입니다. >>는 부호 비트를 그대로 채워 음수가 음수로 남고 -8 >> 1은 -4가 되며, >>>는 항상 0으로 채워 -8 >>> 1은 2147483644가 됩니다. 괄호도 중요합니다. 자바와 C에서는 비교 연산자(==)가 비트 AND(&)보다 우선순위가 높아서 n & (n - 1) == 0처럼 쓰면 n & ((n - 1) == 0)으로 묶여 자바에서는 컴파일 오류가 나고 C에서는 의도와 다르게 계산됩니다. 반드시 (n & (n - 1)) == 0으로 괄호를 칩니다. 파이썬은 우선순위가 반대라 괄호가 없어도 되지만 같은 습관을 들이는 것이 안전합니다. 표준 라이브러리의 Integer.bitCount는 1의 개수를 한 번에 세어 줍니다.

양의 정수 n이 2의 거듭제곱인지 판별하는 비트 연산 조건은?

2의 거듭제곱은 이진수로 1이 딱 하나 있습니다.

2의 거듭제곱은 이진수에서 1이 하나뿐입니다. n - 1은 그 1이 0이 되고 아래 비트가 모두 1이 되므로 (n & (n - 1)) 은 0이 됩니다. (단, n > 0 인 경우)

배열에서 한 원소만 한 번 나타나고 나머지는 모두 두 번씩 나타날 때, 그 원소를 O(n)에 O(1) 공간으로 찾는 방법은?

a ^ a = 0 이고 a ^ 0 = a 입니다.

같은 값끼리 XOR하면 0이 되고, 0과 XOR한 값은 그대로이므로 모든 원소를 XOR하면 쌍으로 나온 값은 사라지고 한 번만 나온 값만 남습니다.

비트마스크 mask에서 i번째 원소가 집합에 포함되어 있는지 확인하는 식은?

i번째 비트를 맨 오른쪽으로 옮긴 뒤 그 비트만 남깁니다.

mask를 오른쪽으로 i칸 시프트하면 i번째 비트가 최하위 비트가 되고, & 1로 그 비트만 확인할 수 있습니다. mask & (1 << i) 도 같은 의미입니다.