C++で同じセットビット数を持つ次に大きい数を求める方法

本記事では、与えられた数値 n より大きく、かつ2進表現におけるセットビット（1のビット）の数が n と同じである数値を求める方法を解説します。

2進表現における「1」のビットのことをセットビットと呼びます。

具体例

まず、以下の入出力例を見てみましょう。

入力

124

出力

143

124 を2進数で表すと 1111100（セットビット数：5）、143 を2進数で表すと 10001111（セットビット数：5）となり、両者が同じセットビット数を持つことが確認できます。

アルゴリズム

• 数値 n を初期化します。

• セットビットの数をカウントする関数を作成します。

• 反復変数を n + 1 で初期化します。

• 無限ループを作成し、以下の処理を繰り返します。

  • 現在調べている数値のセットビット数が n のセットビット数と一致するかどうかを確認します。

  • 一致する数値が見つかったら、その数値を返します。

  • 見つからない場合は、数値を1つ増やして再度確認します。

実装

以下は、上記のアルゴリズムをC++で実装した例です。

#include <bits/stdc++.h>
using namespace std;
int getSetBitsCount(int n) {
    int count = 0;
    while (n) {
        if (n % 2 == 1) {
            count += 1;
        }
        n /= 2;
    }
    return count;
}
int getNextGreaterElementWithSameSetBits(int n) {
    int setBitsCount = getSetBitsCount(n);
    int i = n + 1;
    while (true) {
        if (setBitsCount == getSetBitsCount(i)) {
            return i;
        }
        i += 1;
    }
}
int main() {
    int n = 124;
    cout << getNextGreaterElementWithSameSetBits(n) << endl;
    return 0;
}

実行結果

上記のコードを実行すると、以下の結果が得られます。

143

補足：計算量について

この方法はシンプルで理解しやすい反面、条件を満たす数が見つかるまで順番に調べる必要があるため、数値が大きい場合は処理に時間がかかることがあります。より効率的な手法としては、ビット操作を活用した Snoob（Same Number Of One Bits）アルゴリズム が知られています。これは「右端のセットビットの並びを操作して、少ない計算量で次の数を直接求める」方法で、競技プログラミングなどでも広く使われています。まずは本記事のような素朴なアプローチでロジックを理解し、その後ビット演算による最適化に挑戦するのがおすすめです。