C/C++로 정수의 설정된 비트(Set Bit) 개수 세는 방법

설정된 비트(set bit)를 세는 것이란 주어진 정수에서 1의 개수를 세는 것을 의미합니다. 이를 해결하기 위한 다양한 방법이 존재하는데, 여기서는 정수의 이진수 표현(바이너리)에서 문자열에 포함된 1의 개수를 세는 방법을 살펴보겠습니다.

1의 개수를 세려면 문자열을 순회하면서 각 요소를 하나씩 확인하고, 문자열 내 모든 1을 카운트하면 됩니다. 예를 들어 입력값이 17이라면 출력은 2가 됩니다. 왜냐하면 17의 이진수 표현인 10001에는 1이 두 개 포함되어 있기 때문입니다.

입력: 양의 정수를 입력하세요: 6
출력: 2

동작 원리 설명

6의 이진수 표현은 110이며, 설정된 비트(1)는 2개입니다.

이 반복(iterative) 방식은 비트 하나당 한 번의 반복을 수행합니다. 즉, 숫자의 모든 비트를 처음부터 끝까지 순회하며 더 이상 설정된 비트가 없을 때 반복이 종료됩니다. 최악의 경우, 최상위 비트만 설정된 32비트 워드라면 32번의 반복을 거치게 됩니다. 이 방법은 가장 간단한 솔루션으로, 1이 드물게 분포되어 있고 하위 비트(lsb) 쪽에 위치해 있을 때 특히 유용합니다.

예제 코드

#include <stdio.h>
int main(void) {
    unsigned int n = 34;
    int c;
    for (c = 0; n; n >>= 1) {
        c += n & 1;
    }
    printf("%d\n", c);
}

코드 설명

위 코드는 n을 오른쪽 시프트(>>= 1)하면서 가장 오른쪽 비트(n & 1)가 1인지 검사하여 카운트합니다. n이 0이 되면 모든 비트를 확인한 것이므로 루프가 종료됩니다. 위 예제에서 34의 이진수는 100010이므로 결과값으로 2가 출력됩니다.