C++で同じ数のセットビットを持つ次に大きい数

数値nが与えられているので、バイナリ表現のnと同じセットビット数でnより大きい数値を見つける必要があります。

2進表現の数字1はセットビットと呼ばれます。

例を見てみましょう。

入力

124

出力

143

アルゴリズム

• 番号を初期化しますn。

• 設定されたビット数のカウントを取得する関数を記述します。

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

• 無限ループを記述します。

  • nのセットビット数と等しい数のセットビット数を確認します。

  • 見つけたら番号を返します。

  • 番号を増やします。

実装

以下は、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