C++でもう1つのセットビット数を持つ次に大きい整数

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

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

例を見てみましょう。

入力

124

出力

125

アルゴリズム

• 番号を初期化します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 + 1 == getSetBitsCount(i)) {
         return i;
      }
      i += 1;
   }
}
int main() {
   int n = 124;
   cout << getNextGreaterElementWithSameSetBits(n) << endl;
   return 0;
}

出力

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

125