In this article, we shall explore the various ways we can find the Nearest smaller and greater numbers with same number of set bits for given number.

We shall see two approaches

1. The brute force approach
2. The Bit manipulation

Table of contents:

1. Understanding the problem
2. Brute-force approach
3. Time Complexity for this approach
4. Bit manipulation approach
   • Nearest Greater Number
   • Nearest Lesser Number
5. Time Complexity

So, let's get started!

Understanding the problem

Suppose we are given a number, say 103. We need to find the nearest smaller and greater numbers which have the same number of set bits i.e. '1' bits in their binary representation. For nearest greater number, we have

103 = 1 1 0 0 1 1 1
104 = 1 1 0 1 0 0 0
105 = 1 1 0 1 0 0 1
106 = 1 1 0 1 0 1 0
107 = 1 1 0 1 0 1 1

We see that 107 has the same number of set bits as 103. So, 107 is the nearest greater number with the same set bits as 103.

Similarly, to find the nearest smaller number with the same number of set bits, we can go backwards. We will arrive at 94 whose binary representation is -

94 = 1 0 1 1 1 1 0

103, 107 and 94- all have 5 set bits. Let us see how we can solve this problem.

Brute-force approach

The brute force approach takes the given number and counts the number of set bits in it. Then, to find the nearest greater number with the same number of set bits, we keep incrementing the number by 1 and check it for the number of set bits. If it is found to be equal, we return the number as the answer. Similarly, to find the nearest number lesser than our number, we decrement the given number by 1 iteratively, until either the number becomes 0 or a number with the same number of set bits is found.

In C++, we need a couple of functions to get this done. Let's see how:

1. The count1() function which takes in a number as parameter and returns the number of '1' bits in it. We do this by ANDing the last bit with 1 to check if it is 1, and then we do a left shift on the number. This goes on while the number is not 0.

int count1(int n)
{
    int ones=0;
    while(n){
        if(n&1==1){
            ones++;
        }
        n=n>>1;
    }
    return ones;
}

2. The nearestgreater()/nearestlesser() function. nearestlesser() and nearestgreater() take in a integer parameter and decrement/increment iteratively and check the number of set bits. When the answer is found, the loop is broken and the value is returned.

int nearestgreater(int n){
   int m=n+1;
   int base=count1(n);
   while(m){
    if(count1(m)==base){
        return m;
    }
    m++;
   }
}
int nearestlesser(int n){
   int m=n-1;
   int base=count1(n);
   while(m){
    if(count1(m)==base){
        return m;
    }
    m--;
   }
}

So, we have the overall code:

#include <bits/stdc++.h>
using namespace std;

int count1(int n)
{
    int one=0;
    while(n){
        if(n&1==1){
            one++;
        }
        n=n>>1;
    }
    return one;
}

int nearestgreater(int n){
   int m=n+1;
   int base=count1(n);
   while(m){
    if(count1(m)==base){
        return m;
    }
    m++;
   }
}

int nearestlesser(int n){
   int m=n-1;
   int base=count1(n);
   while(m){
    if(count1(m)==base){
        return m;
    }
    m--;
   }
}

int main()
{
    int i=103,j=107;
    int m=nearestgreater(i);
    cout<<m<<" "<<count1(m)<<endl;
    int p=nearestlesser(j);
    cout<<p<<" "<<count1(p);
    return 0;
}

We get the following output:

107 5
103 5

Time Complexity for this approach

The brute force approach has a O(N logN) time complexity, since it iterates over and over until a possible answer is found, and for every interation, it checks the number of set bits using a function call.
Since, number of bits in a number n is log₂n+1, so time complexity of count1() is O(log n).
An iterative call will make the overall time complexity O(nlog n).

The maximum number of cases to be checked will be N in case all the bits need to be shifted for the larger/smaller number.

Bit manipulation approach

In this approach, we shall use a bunch of bitwise operators to find the nearest greater and smaller number with the same number of set bits. This will require a bit by bit analysis of numbers on our end to see what changes we must make to solve our problem.

Nearest Greater Number

We have the number 103 (1 1 0 0 1 1 1), and the nearest greater number 107 (1 1 0 1 0 1 1). Now, for any number, since we need to maintain the same number of set bits and yet, increase the value, we shall try to change a zero bit to one, and counter this by turning a different one bit to zero.

• Our first observation should be that the number will only increase if the zero-to-one transition happens to the left of the one-to-zero transition. That is, the 8-bit must change from zero to one if we want to increase the number after switching the 4-bit from one to zero.
• Our second observation is that we are looking for the nearest greater number. So, we cannot just switch any random left zero to one and a right one to zero. We must ensure that the increase in value is minimal. This can be achieved by scanning the bits right to left and selecting the first zero bit which has a one bit on its immediate right.

Observe this:

                      C
       103 = 1  1  0  0  1  1  1
bit index:   6  5  4  3  2  1  0

The rightmost zero with a one to the right of it is present at index 3. (Please note that we begin indexing from 0.)

So, we switch the 0 bit to 1 and end up temporarily with this: 1 1 0 1 1 1

1. Now, we need to counter this move by changing one of the set bits on the right to 0. Since the increase must be minimal, all the bits on the right of the changed bit(say position C) must be arranged in the manner where they form the most minimum number. That is, the 0's must come in the higher indexes and the 1's must come at the lower ones. We shall also switch a set bit to 0.

Let's take a different example to make this even clearer:

                      C
       412 = 1  1  0  0  1  1  1  0  0
bit index:   8  7  6  5  4  3  2  1  0

The zero bit we pick is at index 5. Now, we must rearrange the bits to the right of C to giving the overall number a minimal increment. So, we arrange the zeroes first and then, the ones. We also change one set bit to 0. So, we get:

                      C
       412 = 1  1  0  0  1  1  1  0  0
bit index:   8  7  6  5  4  3  2  1  0

NEW:         1  1  0  1  0  0  0  1  1 = 419

So, we have now understood what we need to do. Let us see how we can use bitwise operators to accomplish this.

1. First, we shall find the position of zero bit which we must change to one. Here, C=5.
2. As we look for this zero bit, we count the number of 0 and 1 bits on the way. Let count0 be the number of zeroes and count1 be the number of ones. Here, count0=2 and count1=3. Note that C=count0+count1.
3. Now, we set the right bits to the sequence of (count0)+1 zero bits and (count1)-1 one bits, i.e. in this case 3 zeroes followed by 2 ones: 0 0 0 1 1.
   This can be done as follows:

int nearestgreater(int n)
{

	int tempvar = n;
	int count0 = 0;
	int count1 = 0;

	while (((tempvar & 1) == 0) && (tempvar != 0))
	{
               count0 ++;
		tempvar >>= 1;
	}
	while ((tempvar & 1)==1)
	{
               count1++;
		tempvar >>= 1;
	}

	if (count0 +count1 == 31 || count0 +count1== 0)
		return -1;

        int C = count0 + count1; //1

	n |= (1 << C); //2

	n &= ~((1 << C) - 1); //3

	n |= (1 << (count1 - 1)) - 1; //4

	return n;
}

In this function:

• The two while loops analyze the bits from the right and stop at the point where bit is 0 with 1 on its right.
• If all the bits are 0 or 1, then, return -1 and exit.
• We need to set the bit at position C. So, take a new 1 bit and shift it leftwards by C steps. So, the the number begins 1 0 0 0 0 0...(C-1 zeroes). This number is OR'ed with the given number. Since any bit OR'ed with 1 is 1, so we have set our bit at the required index.
• Next, we set all the bits after Cth bit as 0. For this, we take (1<<C). Example:

C=5
count0=2 
count1=3
So, suppose x=(1<<C)=1 0 0 0 0 0.

A direct AND with 1<<C is useless as we know that int objects are 32 bits long. So, when we write 10000, the one bit actually has a lot of zeroes on its left. We don't mention them because they add no value to the number. So, if we directly AND n with 1<<C, all the bits in n to the left of position C will get AND'ed with 0 and turn 0. So, let's work around this.

    x=(1<<C)=1 0 0 0 0 0.
Subtracting 1 from x, we get
    x-1=0 1 1 1 1 1
Now, negating this, we have
  ~(x-1)=1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0. 
  So, when we AND this with n, all the bits AND'ed with 0 turn 0. The rest remain unaffected.

• Now that every bit on the right of C position is set to 0, we shall set the last count1-1 bits to 1. We do this as follows:

 y=1<<(Count1-1)= 1<<2 = 100.
 Negating y,
     we get y=011.
     We OR n with y to get the required bits set as needed.
     So, n= 1  1  0  1  0  0  0  1  1.

Thus, we have arrived at our desired number.

Nearest Lesser Number

This approach is similar to the above approach. Suppose we have the number 419=110100011. Now, we need to find the nearest lesser number with the same number of bits. For this, we look for the rightmost 1 bit which has a 0 in its immediate right. We count the number of zeroes and ones on the way and store it in count0 and count1. Then, this 1 bit is switched to 0 to reduce the value of n. Now, we must counter this step by turning a 0 bit to 1 on the right side of the position C. We also manipulate the bits to the right of C to make sure the difference is minial. This involves adding all the 1 bits before the 0 bits. Let's see how this can be done in code:

int nearestlesser(int n)
{
    int tempvar = n;
    int count0 = 0;
    int count1= 0;

    while ((tempvar & 1) == 1)
    {
        count1++;
        tempvar = tempvar >> 1;
    }

    if (tempvar == 0)
        return -1;

    while (((tempvar & 1) == 0) && (tempvar!= 0))
    {
        count0++;
        tempvar  = tempvar >> 1;
    }

    int C = count0 + count1; //1

    n = n & ((~0) << (C + 1)); //2

    int dummy = (1 << (count1 + 1)) - 1; //3

    n = n | dummy << (count0 - 1); //4

    return n;
}

• First, we use two while loops to find count of 0 and 1 bits. This is stored in count0 and count1. When we find the first 1 bit with a 0 on the right, the counting stops. Here, count0=3 and count1=2. So, C=5.
• Now, once we find the bit we need to change to 0, we set about to do just that.

              C
Here, n=1 1 0 1 0 0 0 1 1.
               
       To reset all the bits from C to the right end, we
       start with ~0 and shift it C+1 times.

An obvious question would be- aren't 1 and ~0 the same thing? Like earlier, we know that int objects have 32 bits. So, ~0 is actually 1 1 1 1 1 ...32 times, and no just 1.

Now, we need to reset all the bits at C and post C.
So, we left shift ~0 C+1 times.
So,

~0<<(C+1)=~0<<6=11111111111111111111111111000000

When we AND this with n, all the bits on and after C turn 0. All the other bits remain unchanged.

• Now, from index 0 to C-1, we need to add count1+1 one bits and count0-1 zero bits, in that order. We take a dummy variable.

Here, count1=2. So, we need to add an extra one to balance the number of set bits. So,

1<<(Count1+1)=1<<3=1000.
   Subtracting 1, we get
  1<<(Count1+1)-1=0111. So, dummy=0111.

It may appear that negating 1000 can also yield 0111. But, it doesn't. You know why.

After the 0111, we also need to add count0-1 zeroes. This can easily be done using a left shift.

dummy<<(count0-1)=011100.
Now, at this stage, n=1 1 0 0 0 0 0 0 0.

So, OR'ing n with dummy<<(count0-1), we get n=110011100= 412, which is the required answer.

So, taking an overall look at the code:

#include <bits/stdc++.h>
using namespace std;

int nearestgreater(int n)
{

	int tempvar = n;
	int count0 = 0;
	int count1 = 0;

	while (((tempvar & 1) == 0) && (tempvar != 0))
	{
		count0 ++;
		tempvar >>= 1;
	}
	while ((tempvar & 1)==1)
	{
		count1++;
		tempvar >>= 1;
	}

	if (count0 +count1 == 31 || count0 +count1== 0)
		return -1;

	int C = count0 + count1; //1

	n |= (1 << C); //2

	n &= ~((1 << C) - 1); //3

	n |= (1 << (count1 - 1)) - 1; //4

	return n;
}
int nearestlesser(int n)
{
    int tempvar = n;
    int count0 = 0;
    int count1= 0;

    while ((tempvar & 1) == 1)
    {
        count1++;
        tempvar = tempvar >> 1;
    }

    if (tempvar == 0)
        return -1;

    while (((tempvar & 1) == 0) && (tempvar!= 0))
    {
        count0++;
        tempvar  = tempvar >> 1;
    }

    int C = count0 + count1; //1

    n = n & ((~0) << (C + 1)); //2

    int dummy = (1 << (count1 + 1)) - 1; //3

    n = n | dummy << (count0 - 1); //4

    return n;
}
int main()
{
	int n = 412; // input 1
	cout << nearestgreater(n) << endl;
    n=419;
    cout << nearestlesser(n)<<endl;
	return 0;
}

Time Complexity

Since this method uses 2 while loops followed by a set of constant operations. The two while loops traverse the bits of the given number. Since every number n has log₂n+1 bits. So, time complexity of the while loops= O(log n)+O(log n)=O(log n).

Time complexity of the opeartions: O(1).
So, overall complexity is O(log n)+O(1)=O(log n).

Thus, through this article at OpenGenus, we have explored the various approaches we can employ to find the nearest smaller and greater numbers with same number of set bits. Keep learning!