Next greater integer having one more number of set bits in C++

We are given a number n, we have to find the number that is greater than n with one more set bit than n in its binary representation.

The digit 1 in the binary representation is called set bit.

Let's see an example.

Input

124

Output

125

Algorithm

• Initialise the number n.

• Write a function get the count of number of set bits.

• Initialise the iterative variable with n + 1.

• Write an infinite loop.

  • Check for the number of set bits for numbers greater than n.

  • Return the number when you find it.

Implementation

Following is the implementation of the above algorithm in 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; }

Output

If you run the above code, then you will get the following result.

125