비트 수 세기(popcount)·앞뒤 0 개수

비트 개수 계산기 쉽게 이해하기 — 개념과 원리

비트 개수(popcount)는 2진수 안의 1의 개수이고, 선행 0과 후행 0은 가장 높은 1 앞과 가장 낮은 1 뒤에 있는 0의 개수입니다. 체스 엔진의 비트보드, 해밍 거리, 오류 정정 부호, 메모리 할당기, 2의 거듭제곱 크기의 해시 테이블, 필드에 필요한 비트 수를 정할 때 쓰입니다. 0부터 4,294,967,295까지의 부호 없는 32비트 수를 넣으면 모두 구해 줍니다.

계산 방법

• popcount: 맨 아래 비트를 확인하고 오른쪽으로 옮기기를 값이 0이 될 때까지 반복해 1을 셉니다.
• 선행 0: 32비트에서 가장 높은 1 앞의 0 개수(Math.clz32)이며, 0이면 32입니다.
• 후행 0: x AND −x로 가장 낮은 1만 남긴 뒤 31 − clz32로 위치를 구합니다. 0이면 32로 정합니다.
• 필요 비트 수: 32 − 선행 0, 곧 floor(log₂ x) + 1입니다. 0이면 1입니다.
• 패리티: 1의 개수가 짝수인지 홀수인지입니다.
• 2의 거듭제곱: x > 0이고 x AND (x − 1) = 0이면 해당합니다.

원리

2의 보수에서 −x는 NOT x + 1입니다. NOT x에 1을 더하면 끝의 1들이 0으로 바뀌다가 처음 만나는 0에서 멈추는데, 그 자리가 바로 x의 가장 낮은 1입니다. 그래서 x AND −x는 그 비트 하나만 남깁니다. 반대로 1을 빼면 가장 낮은 1이 0이 되고 그 아래가 모두 1이 되므로, x AND (x − 1)은 가장 낮은 1을 지웁니다. 이 값이 0이라면 1이 하나뿐이었다는 뜻이고, 이것이 2의 거듭제곱의 정의입니다.

예제 풀이

1. 입력 40은 32 + 8, 2진수로 101000입니다.
2. 1이 두 개이므로 popcount는 2, 패리티는 짝수입니다.
3. 6비트를 쓰므로 필요 비트 수는 6, 선행 0은 32 − 6 = 26입니다.
4. 40 AND −40 = 8 = 2³이므로 후행 0은 3입니다.
5. 40 AND 39 = 101000 AND 100111 = 100000 = 32로 0이 아니므로 2의 거듭제곱이 아닙니다.

결과 해석

필요 비트 수는 값을 담을 최소 필드 크기입니다. 6비트는 0~63을 표현하므로 40이 들어갑니다. 후행 0은 그 수를 나누는 가장 큰 2의 거듭제곱을 알려 줍니다(2³ = 8이 40을 나눕니다). A XOR B의 popcount는 두 비트 패턴의 해밍 거리입니다.

흔한 실수

• 8비트나 64비트 기준으로 선행 0을 세는 것(이 도구는 32비트 기준입니다)
• 0을 2의 거듭제곱으로 보는 것
• 비트 패리티를 수 자체의 홀짝과 혼동하는 것(3은 홀수지만 1이 두 개라 비트 패리티는 짝수입니다)

자주 묻는 질문

popcount를 계산하는 CPU 명령어가 있습니까?

많은 프로세서에 있습니다(x86-64의 POPCNT 등). 컴파일러는 __builtin_popcount 같은 내장 함수로 제공합니다.

다음 2의 거듭제곱으로 올림하려면 어떻게 합니까?

x > 1이면 2의 (32 − clz32(x − 1))제곱입니다.

후행 0으로 나누어떨어짐을 알 수 있습니까?

후행 0이 k개이면 2ᵏ로는 나누어떨어지고 2ᵏ⁺¹로는 나누어떨어지지 않습니다.

출처: Henry S. Warren Jr., Hacker's Delight, 2nd ed., Addison-Wesley, 2012, Chapter 5 · Ecma International, ECMA-262 ECMAScript Language Specification