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

This updated information has been further expanded upon on my new website. You can find the updated details here: https://k5kc.com/cs/algorithms/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://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