__builtin_popcount() 들여다보기

1. 알고리즘의 목적

Popcount(Population Count) 알고리즘은 이진수에서 1의 개수를 세는 연산입니다. 컴퓨터 과학에서 이 연산은 다양한 분야에 활용됩니다:

해밍 거리(Hamming distance) 계산
오류 검출 및 수정 코드
패턴 인식
암호학
비트 조작이 필요한 각종 알고리즘

특히 대용량 데이터나 실시간 처리가 필요한 경우, 효율적인 popcount 구현은 성능에 큰 영향을 미칩니다.

2. 알고리즘 이름

이 알고리즘은 여러 이름으로 알려져 있습니다:

Popcount (Population Count)
해밍 가중치(Hamming Weight) 계산 알고리즘
SWAR(SIMD Within A Register) 비트 카운팅
병렬 비트 카운팅(Parallel Bit Counting)

우리가 살펴볼 특정 구현은 “분할 정복(Divide and Conquer)” 방식을 활용한 효율적인 비트 카운팅 알고리즘입니다.

3. 코드

int popcount(unsigned int n) { 
    n = (n >> 1 & 0x55555555) + (n & 0x55555555); 
    n = (n >> 2 & 0x33333333) + (n & 0x33333333); 
    n = (n >> 4 & 0x0F0F0F0F) + (n & 0x0F0F0F0F); 
    n = (n >> 8 & 0x00FF00FF) + (n & 0x00FF00FF); 
    n = (n >> 16 & 0x0000FFFF) + (n & 0x0000FFFF); 
    return n; 
}

이 코드는 단 5번의 연산으로 32비트 정수의 모든 1의 개수를 계산합니다.

4. 원리 설명

병렬 처리 방식

이 알고리즘의 핵심은 병렬 처리입니다. 일반적인 방법으로는 모든 비트를 순차적으로 검사해야 하지만, 이 방식은 여러 비트를 동시에 처리합니다.

단계별 분석

첫 번째 단계: 2비트 그룹화

n = (n >> 1 & 0x55555555) + (n & 0x55555555);

여기서 0x55555555는 이진수로 01010101...(홀수 위치에만 1) 입니다.

실제 작동 방식을 살펴보겠습니다:

(n & 0x55555555): 원래 숫자의 홀수 위치 비트만 남깁니다.
(n >> 1 & 0x55555555): 원래 숫자를 1비트 오른쪽으로 시프트하여 짝수 위치 비트를 홀수 위치로 이동시킨 후, 홀수 위치만 남깁니다.
두 값을 더하면 각 2비트 그룹의 1의 개수가 저장됩니다.

왜 이 연산이 2비트 그룹의 1의 개수를 계산하는지 자세히 살펴보겠습니다:

원래 숫자의 임의의 2비트 그룹을 [b₁, b₀]라고 합시다(b₁은 짝수 위치, b₀는 홀수 위치 비트).

(n & 0x55555555)는 이 그룹에서 [0, b₀]를 추출합니다.
(n >> 1 & 0x55555555)는 [0, b₁]을 얻습니다.
두 값을 더하면: [0, b₀] + [0, b₁] = [0, b₀+b₁]가 됩니다.

b₀와 b₁은 각각 0 또는 1이므로, 그 합 b₀+b₁은 0, 1, 또는 2가 될 수 있습니다. 이 값은 정확히 해당 2비트 그룹에 있는 1의 개수와 일치합니다!

예를 들어:

그룹이 [0,0]이면 → 1의 개수 = 0 → 결과 = [0,0]
그룹이 [0,1] 또는 [1,0]이면 → 1의 개수 = 1 → 결과 = [0,1]
그룹이 [1,1]이면 → 1의 개수 = 2 → 결과 = [1,0]

두 번째 단계: 4비트 그룹화

n = (n >> 2 & 0x33333333) + (n & 0x33333333);

여기서 0x33333333는 이진수로 00110011...입니다.

이 단계에서는 이전 단계의 결과(2비트 그룹의 카운트)를 4비트 그룹으로 합칩니다. 마찬가지로:

(n & 0x33333333)는 하위 2비트를 유지
(n >> 2 & 0x33333333)는 상위 2비트를 가져와서 마스킹
두 값을 더하면 4비트 그룹의 1의 개수가 저장됩니다.

나머지 단계

이후 단계들도 동일한 패턴으로 진행됩니다:

8비트 그룹화: n = (n >> 4 & 0x0F0F0F0F) + (n & 0x0F0F0F0F);
16비트 그룹화: n = (n >> 8 & 0x00FF00FF) + (n & 0x00FF00FF);
32비트 그룹화: n = (n >> 16 & 0x0000FFFF) + (n & 0x0000FFFF);

시프트 연산에서 정보 손실이 없는 이유

시프트 연산(>>)을 하면 일부 비트가 밀려나갈 수 있지만, 이 알고리즘에서는 정보 손실이 발생하지 않습니다. 그 이유는:

각 단계에서 우리는 “현재 단위 그룹의 1의 개수”를 계산합니다.
시프트 연산은 그룹의 오른쪽 부분을 왼쪽으로 가져오는 역할을 합니다.
마스킹 연산은 필요한 부분만 추출합니다.
덧셈 연산은 두 부분의 카운트를 합쳐 더 큰 그룹의 총 카운트를 계산합니다.

이 과정에서 마스킹과 시프트는 항상 상호 보완적으로 작동하여 모든 비트 정보가 최종 결과에 반영됩니다.

시간 복잡도와 효율성

이 알고리즘의 시간 복잡도는 O(5)입니다. 32 = 2^5 이기 때문이죠.

현대 CPU에는 POPCNT라는 전용 명령어가 있어서 이 연산을 하드웨어 수준에서 더 빠르게 수행할 수 있지만, 이 알고리즘은 그러한 명령어가 없는 환경에서도 효율적으로 비트 카운팅을 수행할 수 있도록 합니다.

여러 언어에서 이 알고리즘을 사용한 popcount 함수를 제공합니다.

C/C++: __builtin_popcount(), std::popcount()
Java: Integer.bitCount()
Rust: u32::count_ones()
Python: bin(n).count('1') 또는 gmpy2.popcount()

프데달면프로데뷔함

🔍 탐색기