Find the nearest numbers that have same number of 1s for an integer

Problem

Given an integer, print the next smallest and next largest number that have the same number of 1 bits in their binary representation.

Example
Next higher number for 3 is 5. i.e. (00000011 => 00000101)
Likewise next lower number of 5 is 3.

Solution

Method 1 - Adding or subtracting 1 until we have same number of 1s
For the next largest, keep adding 1 to the number until find the number that has same number of 1 bits. For the next smallest, keep decreasing 1.

public static int findNextSmallest(int number) {  
    int result = number - 1;  
    while (Integer.bitCount(result) != Integer.bitCount(number))  
        result--;  
    return result;  
}  
   
public static int findNextLargest(int number) {  
    int result = number + 1;  
    while (Integer.bitCount(result) != Integer.bitCount(number))  
        result++;  
    return result;  
}

Definitely gonna work but terribly boring. We know this is not what the interviewer expects, he wants some bit manipulation.

Method 2- Change the bits

For getting the next higher number

Traverse from right to left i.e. LSB to MSB. Once we’ve passed a 1, turn on the next 0. We’ve now increased the number by 2^i. Yikes!
Example: xxxxx011100 becomes xxxxx111100.
Turn off the one that’s just to the right side of that. We’re now bigger by 2^i - 2^(i-1).
Example: xxxxx111100 becomes xxxxx101100
Make the number as small as possible by rearranging all the 1s to be as far right as possible:
Example: xxxxx101100 becomes xxxxx100011

For the next smaller number
We can do something like this.

int getNextSmaller(int num) {  
    return ~getNextLarger(~num);  
}  

```i.e. follow the above algorithm for number's complement.  
  
Java code

public static boolean GetBit(int n, int index) {
return ((n & (1 « index)) > 0);
}

public static int SetBit(int n, int index, boolean b) {
if (b) {
return n | (1 « index);
} else {
int mask = ~(1 « index);
return n & mask;
}
}

public static int GetNext_NP(int n) {
if (n <= 0)
return -1;
int index = 0;
int countOnes = 0;

// Find first one.  
while (!GetBit(n, index))  
    index++;  
   
// Turn on next zero.  
while (GetBit(n, index)) {  
    index++;  
    countOnes++;  
}  
n = SetBit(n, index, true);  

// Turn off previous one  
index--;  
n = SetBit(n, index, false);  
countOnes--;  

// Set zeros  
for (int i = index - 1; i >= countOnes; i--) {  
    n = SetBit(n, i, false);  
}  

// Set ones  
for (int i = countOnes - 1; i >= 0; i--) {  
    n = SetBit(n, i, true);  
}  
   
return n;

}

public static int GetPrevious_NP(int n) {
if (n <= 0)
return -1; // Error

int index = 0;  
int countZeros = 0;  

// Find first zero.  
while (GetBit(n, index))  
    index++;  

// Turn off next 1.  
while (!GetBit(n, index)) {  
    index++;  
    countZeros++;  
}  
n = SetBit(n, index, false);  

// Turn on previous zero  
index--;  
n = SetBit(n, index, true);  
countZeros--;  

// Set ones  
for (int i = index - 1; i >= countZeros; i--) {  
    n = SetBit(n, i, true);  
}  

// Set zeros  
for (int i = countZeros - 1; i >= 0; i--) {  
    n = SetBit(n, i, false);  
}  

return n;

}

**References**  

*   [http://tianrunhe.wordpress.com/2012/03/09/find-the-nearest-numbers-that-have-same-number-of-1s-for-an-integer/](http://tianrunhe.wordpress.com/2012/03/09/find-the-nearest-numbers-that-have-same-number-of-1s-for-an-integer/)
*   [http://stackoverflow.com/questions/5498130/bit-manipulationprint-the-next-smallest-and-largest-numbers-with-same-no-of-1-b](http://stackoverflow.com/questions/5498130/bit-manipulationprint-the-next-smallest-and-largest-numbers-with-same-no-of-1-b)
*   [http://www.slideshare.net/gkumar007/bits-next-higher-presentation](http://www.slideshare.net/gkumar007/bits-next-higher-presentation)

Problem

Solution

See also