Nearest numbers with the same number of set bits

Observation: Consider the location of two bits for a number ‘n’ as ‘i’  and ‘j’. To maintain the same number of 1 bit in ‘n’, if we flip the ‘i-th’ bit from 1 to 0, we must convert the ‘j-th’ bit from 0 to 1. If ‘i’ is to the left of ‘j’ then the number will increase. Otherwise, it will decrease. 

1. To find the next smallest number:

Let 'next' be the next smallest number to ‘n’ having the same count of ‘1’ bits as ‘n’. To obtain 'next' from ‘n’ we observe:

• In ‘n’, if we flip a bit from 0 to 1 then we must flip a bit from 1 to 0.
• 'next' can be greater than ‘n’ only if the flipped 0 bit was left to the 1 bit.
• 'next' has to be greater than ‘n’ but not too big, so we need to flip the rightmost 0 bit, which has a 1 bit on its right, i.e., the rightmost non-trailing zero.

Steps to obtain 'next':

• Initialize 'next = n’ and perform the following bit operations on 'next'.
• Let ‘r’ be the position of the rightmost non-trailing zero in 'next'. Flip the bit at position ‘r’ from 0 to 1.
• Let ‘c’ be the number of 1’s to the right of ‘r’, which means ‘r > c’. Set all the bits to the right of ‘r’ to 0.
• After this, 'next' becomes greater than ‘n’ and has ‘c-1’ less 1’s than ‘n’. So, we need to flip ‘c-1’ bits of 'next' from 0 to 1 to make the 'next' the smallest number greater than ‘n’ having the same count of ‘1’ bits as n.
• All the ‘r-1’ bits to the right of ‘r’ are 0 and ‘r > c’. Flip the rightmost ‘c-1’ bits from 0 to 1 to get the smallest valid value of 'next'. Return 'next' as the answer.

2. To find the previous largest number:

Let 'prev' be the previous largest number to ‘n’ having the same count of ‘1’ bits as ‘n’. we follow a similar approach as above. Instead of flipping the rightmost non-trailing zero, the only difference is that we flip the rightmost non-trailing one because here, we want 'prev' to be smaller than ‘n’.

Steps to obtain 'prev':

• Initialize 'prev = n’ and perform the following bit operations on 'prev'.
• Let ‘r’ be the rightmost non-trailing one in 'prev' and ‘c’ be the number of 1’s to the right of ‘r’, which means ‘c+1 < r’.
• Set the bit at ‘r’ and all the bits to the right of ‘r’ to 0.
• After this, 'prev' becomes smaller than ‘n’ and has ‘c+1’ less 1s than ‘n’. So, we need to flip ‘c+1’ bits from the right of ‘r’ from 0 to 1 to make 'prev' the largest number smaller than ‘n’ having the same count of ‘1’ bits as ‘n’.
• All the ‘r-1’ bits to the right of ‘r’ are 0 and ‘r > c+1’. Flip ‘c+1’ bits immediately to the right of ‘r’ from 0 to 1 to get the largest valid value of 'prev'. Return 'prev' as the answer.

This approach is similar to the bit-manipulation approach, but we want to use as little bit-manipulation as possible.

1. To find the next smallest number:

Let 'next' be the next smallest number to ‘n’ having the same count of ‘1’ bits as ‘n’.

If ‘r’ is the position of the rightmost non-trailing zero in ‘n’, ‘c1’ is the number of 1’s to the right of ‘r’, and ‘c0’ is the number of trailing 0’s in ‘n’, we have ‘r = c0 + c1’.

After initializing ‘next = n’, in our previous approach we performed the following operations on ‘next’:

• Set the ‘r-th’ bit to one.
• Set all the bits to the right of ‘r’ to zero.
• Set the rightmost ‘c1-1’ bits to one.
• Observe that we can quickly do the first two steps by flipping all the trailing 0’s to 1 (making all the bits to the right of ‘r’ one) and then adding one. Here adding one flips all the 1’s to the right of ‘r’ to zero and sets the ‘r-th’ bit to one. We can write this arithmetically as follows:
  • ‘next += 2^(c0) - 1’ (Set trailing 0’s to 1, making all the bits to the right of ‘r’ one)
  • ‘next += 1’ (Flip all 1’s to the right of ‘r’ to 0 and set ‘r-th’ bit to one)
  • Similarly, we can perform the third step, ‘next += 2^(c1-1) - 1’ (Flip the rightmost ‘c1-1’ bits from 0 to 1)
  • After writing the above steps in a single equation, we get:
    • ‘next = n + (2^(c0) - 1) + 1 + (2^(c1-1) - 1)’ (Initially, ‘next = n’) Therefore, ‘next = n + 2^(c0) + 2^(c1-1) - 1’

2. To find the previous largest number:

Let ‘prev’ be the previous largest number to ‘n’ having the same count of ‘1’ bits as ‘n’.

If ‘r’ is the position of the rightmost non-trailing one in ‘n’, ‘c0’ is the number of 0’s to the right of ‘r’, and ‘c1’ is the number of trailing 1’s in ‘n’, we have ‘r = c0 + c1’.

After initializing ‘prev = n’, in our previous approach, we performed the following operations on ‘prev’:

• Set the ‘r-th’ bit to zero.
• Set all the bits to the right of ‘r’ to one.
• Set the rightmost ‘c0-1’ bits to zero.
• We can do the first two steps arithmetically as follows:
  • ‘prev -= 2^(c1) - 1’ (Remove the trailing 1’s, making all the bits to the right of ‘r’ zero)
  • ‘prev -= 1’ (Flip all 0’s to the right of ‘r’ to 1 and the ‘r-th’ bit from one to zero)
  • Similarly, we can perform the third step, ‘prev -= 2^(c0-1) - 1’ (Flip the rightmost ‘c0-1’ bits from 1 to 0)
  • After writing the above steps in a single equation, we get:
    • ‘prev = n - (2^(c1) - 1) - 1 - (2^(c0-1) - 1)’ (Initially, ‘prev = n’)
    • Therefore, ‘prev = n - 2^(c1) - 2^(c0-1) + 1’

Note: We can calculate ‘2^x’ efficiently using the left-shift (‘<<’) operator.

‘2^x = 1<<x’ (Here, ‘x >= 0’ and ‘2^x’ is in the valid integer range)