C++で数値がBleak（ブリーク）かどうかを判定する方法

本記事では、ある数値がBleak（ブリーク）であるかどうかを判定する方法を解説します。Bleak数とは、任意の非負整数 x に対して、x と x のセットビット数（2進表現で1となっているビットの個数）との和がその数に一致しない、すなわち x + set_bit_count(x) ≠ n が成り立つような数のことです。

言い換えれば、n = x + セットビット数(x) を満たす非負整数 x がひとつも存在しない場合、n は Bleak 数であるといえます。

判定の考え方

判定のアプローチは非常にシンプルです。1 から n-1 までの各整数 i について「i + i のセットビット数」を計算し、その結果が n と一致するかどうかを順番に確認します。一致する i が見つかれば n は Bleak 数ではなく、最後まで見つからなければ n は Bleak 数であると判定できます。

具体例を挙げると、3 は 2 + 1（2は2進数で「10」なのでセットビット数は1）と表せるため Bleak 数ではありません。一方、4 はどの整数とそのセットビット数の和としても表せないため、Bleak 数となります。

サンプルコード

セットビット数の計算には、Brian Kernighan のアルゴリズム（x &= (x - 1) を繰り返して1を消去していく手法）を使用しています。この方法により、セットビット数だけループが回るため効率的にカウントできます。

#include <iostream>
using namespace std;

// セットビット数（1になっているビットの個数）を数える関数
int set_bit_count(int x) {
    unsigned int bit_count = 0;
    while (x != 0) {
        x &= (x - 1); // 最下位の1ビットを消去
        bit_count++;
    }
    return bit_count;
}

// n が Bleak 数かどうかを判定する関数
bool isBleakNumber(int n) {
    for (int i = 1; i < n; i++) {
        if (i + set_bit_count(i) == n)
            return false; // 表せる組み合わせが存在 → Bleakではない
    }
    return true; // 見つからなかった → Bleak数
}

int main() {
    isBleakNumber(3) ? cout << "Yes\n" : cout << "No\n";
    isBleakNumber(4) ? cout << "Yes\n" : cout << "No\n";
}

実行結果

No
Yes

処理の流れと計算量

このプログラムでは、まず set_bit_count() 関数が与えられた整数のセットビット数を返します。次に isBleakNumber() 関数が 1 から n-1 までの候補をすべて調べ、条件を満たすものがあれば false（Bleakではない）を返します。

計算量については、候補の探索に O(n)、各候補のセットビット数計算に O(log n) かかるため、全体の時間計算量は O(n log n) となります。小〜中規模の数値であれば十分実用的ですが、より大きな数値を扱う場合は探索範囲の工夫（セットビット数は log₂n 以下であるため、n - log₂n 以降のみを調べればよい）によって高速化することも可能です。