C++로 숫자가 Bleak 수인지 판별하는 방법

Bleak 수란 무엇인가?

이 글에서는 특정 숫자가 Bleak(블리크) 수인지 판별하는 방법을 알아보겠습니다. Bleak 수란 어떤 양의 정수 x와 그 수의 세트 비트(set bit, 1로 설정된 비트) 개수의 합으로 표현될 수 없는 수를 의미합니다. 즉, 임의의 음이 아닌 정수 x에 대해 x + set_bit_count(x) ≠ n 이 항상 성립한다면, 그 수 n은 Bleak 수입니다.

반대로 1부터 n 미만까지의 수 중에서 자기 자신과 자신의 세트 비트 개수를 더했을 때 n이 되는 수가 하나라도 존재한다면, n은 Bleak 수가 아닙니다.

핵심 아이디어

판별 개념은 매우 간단합니다. 1부터 n-1까지의 모든 정수 i에 대해 i + set_bit_count(i) == n 인지 검사하고, 조건을 만족하는 i가 존재하면 n은 Bleak 수가 아니며, 끝까지 존재하지 않으면 n은 Bleak 수입니다.

C++ 구현 예제

#include <iostream>
using namespace std;
int set_bit_count(int x) {
    unsigned int bit_count = 0;
    while (x != 0) {
        x &= (x - 1);
        bit_count++;
    }
    return bit_count;
}
bool isBleakNumber(int n) {
    for (int i = 1; i < n; i++)
    if (i + set_bit_count(i) == n)
        return false;
    return true;
}
int main() {
    isBleakNumber(3) ? cout << "Yes\n" : cout << "No\n";
    isBleakNumber(4) ? cout << "Yes\n" : cout << "No\n";
}

실행 결과

No
Yes

코드 설명

set_bit_count 함수는 브라이언 커니핸(Brian Kernighan) 알고리즘을 활용해 세트 비트의 개수를 효율적으로 계산합니다. x &= (x - 1) 연산은 x에서 가장 오른쪽에 있는 1비트를 제거하므로, 이 과정을 반복한 횟수가 곧 세트 비트 개수가 됩니다.

isBleakNumber 함수는 1부터 n 미만까지의 수를 순회하며 각 수와 그 수의 세트 비트 개수의 합이 n과 일치하는지 확인합니다. 일치하는 경우가 있으면 false를 반환하고, 없으면 true를 반환해 n이 Bleak 수임을 나타냅니다.

예를 들어 3은 1 + set_bit_count(1) = 2, 2 + set_bit_count(2) = 3 이므로 Bleak 수가 아니지만, 4를 만족하는 조합이 존재하지 않으므로 4는 Bleak 수입니다. 이 알고리즘의 시간 복잡도는 O(n log n)입니다.