C++로 이진수 표현에서 세트 비트 개수가 홀수인 정수의 개수 구하기

숫자 n이 주어졌을 때, 1부터 n까지의 정수 중 이진수 표현에서 세트 비트(set bit, 값이 1인 비트)의 개수가 홀수인 정수가 몇 개 있는지 구하는 문제입니다. 예시를 통해 살펴보겠습니다.

입력

n = 10

출력

1부터 10 사이에는 이진수 표현에서 세트 비트 개수가 홀수인 정수가 총 5개 존재합니다. 실제로 확인해 보면 1(1), 2(10), 4(100), 7(111), 8(1000)이 해당됩니다.

알고리즘

숫자 N을 초기화합니다.
이진수 형태에서 세트 비트의 개수를 세는 함수를 작성합니다.
결과를 저장할 카운트 변수를 0으로 초기화합니다.
1부터 N까지 반복하는 루프를 작성합니다.
- 각 정수의 세트 비트 개수를 계산합니다.
- 세트 비트 개수가 홀수라면 카운트를 1 증가시킵니다.
카운트를 반환합니다.

구현

다음은 위 알고리즘을 C++로 구현한 코드입니다.

#include <bits/stdc++.h>
using namespace std;

// 이진수에서 세트 비트(1)의 개수를 세는 함수
int getSetBitsCount(int n) {
    int count = 0;
    while (n) {
        if (n % 2 == 1) {
            count += 1;
        }
        n /= 2;
    }
    return count;
}

// 세트 비트 개수가 홀수인 정수의 개수를 세는 함수
int getOddSetBitsIntegerCount(int n) {
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (getSetBitsCount(i) % 2 == 1) {
            count += 1;
        }
    }
    return count;
}

int main() {
    int n = 10;
    cout << getOddSetBitsIntegerCount(n) << endl;
    return 0;
}

출력 결과

위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

동작 원리 설명

getSetBitsCount 함수는 숫자를 2로 나누면서 나머지가 1일 때마다 카운트를 증가시키는 방식으로 세트 비트를 셉니다. 이는 이진수의 각 자릿값을 확인하는 것과 동일합니다.

getOddSetBitsIntegerCount 함수는 1부터 N까지 모든 정수에 대해 위 함수를 호출하고, 세트 비트 개수가 홀수인 경우만 카운트합니다. 전체 시간 복잡도는 O(N × log N)입니다.

참고: 비트 연산을 활용하면 더 효율적으로 구현할 수 있습니다. 예를 들어 n & 1로 최하위 비트를 확인하고 n >>= 1로 오른쪽 시프트하거나, Brian Kernighan 알고리즘(n &= (n - 1))을 사용하면 세트 비트 개수만큼만 반복하게 되어 성능을 개선할 수 있습니다.