C++でセットビットが1つ多い次に大きい整数を求める方法

問題概要

ある数値 n が与えられたとき、2進表現におけるセットビット（1になっているビット）の数が n より1つ多く、かつ n より大きい数値を見つける必要があります。

なお、2進表現における「1」のビットはセットビットと呼ばれます。

具体例を見てみましょう。

入力

124

出力

125

124 の2進表現は 1111100 で、セットビットは5個です。一方、125 の2進表現は 1111101 で、セットビットは6個あります。つまり 125 は、「124 より大きく、かつセットビットが1つ多い」という条件を満たす整数だというわけです。

アルゴリズム

• 数値 n を初期化します。
• セットビットの個数を数える関数を作成します。
• 反復用の変数を n + 1 で初期化します。
• 無限ループを作成します。
  • n より大きい各数値について、セットビット数を順番に調べます。
  • 条件を満たす数値が見つかった時点で、その数値を返します。

C++での実装例

以下は、上記アルゴリズムを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 getNextGreaterElementWithOneMoreSetBit(int n) {
   int setBitsCount = getSetBitsCount(n);
   int i = n + 1;
   while (true) {
      if (setBitsCount + 1 == getSetBitsCount(i)) {
         return i;
      }
      i += 1;
   }
}
int main() {
   int n = 124;
   cout << getNextGreaterElementWithOneMoreSetBit(n) << endl;
   return 0;
}

実行結果

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

125

補足：計算量について

この実装は非常にシンプルで理解しやすい反面、答えが遠くにある場合は反復回数が増え、時間計算量が大きくなる可能性があります。ビット演算を活用すれば、より効率的に解を求めることも可能です。まずは本記事のような素直な実装でロジックをしっかり理解し、その後ビット操作による最適化に挑戦するのがおすすめです。