Print the next smallest and next largest number that have the same number of 1 bits in their binary representation

Question

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

How can I improve this?

void printNextNumber(int num){
    int inputNumOfBits = calcBits(num);

    int  nextLargest = num + 1, nextSmallest = num - 1;

    //nextLargest
    while (true){
        if (calcBits(nextLargest) == inputNumOfBits){
            break;
        }
        nextLargest++;
    }

    //nextSmallest
    while (true){
        if (calcBits(nextSmallest) == inputNumOfBits){
            break;
        }
        nextSmallest--;
    }
    System.out.println("Next largest: " + nextLargest);
    System.out.println("Next smallest: " + nextSmallest);
}

private int calcBits(int x){
    int count = 0;
    int i = 0;

    while (i < 32){
        if ((x & (1<<i)) != 0){
            count++;
        }
        i++;
    }
    return count;
}

Answer 1

Using java.lang.Integer.bitCount():

public int nextWithSameBitCount(int i) {
    int bitCount = Integer.bitCount(i);
    do {
        i++;
    } while(Integer.bitCount(i) != bitCount);
    return i;
}

Answer 2

You are solving this the "mathematical" way.

what about the "lego" way?

Your number consists of a string with "1"s and "0"s.

[edit]
thanks to @graybeard who pointed that the method must be changed to fulfill the requirement:

The next bigger number is when you switch the position of the most right "0" that is followed by a "1" with that following "1".

int nextBigger(int number){
  char[] binaryDigits = BigIntger.valueOf(number).toString(2).toCharArray();
  int lastZeroFollowedByIndex = findLastZeroFollowedByOneIn(binaryDigits);
  binaryDigits[lastZeroFollowedByIndex]    = '1';     
  binaryDigits[lastZeroFollowedByIndex +1] = '0';
  return new BigInteger(new String(binaryDigits),2).intValue();
}

Answer 3

    int  nextLargest = num + 1, nextSmallest = num - 1;

The general rule is one assignment per line. So either

    int nextLargest = num + 1,
        nextSmallest = num - 1;

or

    int nextLargest = num + 1;
    int nextSmallest = num - 1;

The latter may be a bit more readable.

    //nextLargest
    while (true){
        if (calcBits(nextLargest) == inputNumOfBits){
            break;
        }
        nextLargest++;
    }

This seems more complicated than it needs to be. Consider

    while (calcBits(nextLargest) != inputNumOfBits) {
        nextLargest++;
    }

This does the same thing in fewer lines.

It doesn't really seem necessary to have a comment that just says on what variable you are operating.

    int i = 0;

    while (i < 32){
        if ((x & (1<<i)) != 0){
            count++;
        }
        i++;
    }

You don't need to do this much math. Consider

    while (x != 0) {
        if (x & 1 != 0) {
            count++;
        }

        x >>>= 1;
    }

This does away with the i variable altogether and works entirely with the temporary x variable.

Answer 4

How can I improve [the code presented]?

Comment your code.
Specify whether negative numbers are to be considered, and how those are represented.
Describe the algorithm you use.

To elaborate on my comment to Timothy Truckle's answer, an adoption of source code found in Warren, Henry S.: Hacker's Delight, Addison-Wesley, 9780321842688 (with ancestry in HAKMEM) - invented time and again:

 /** next bigger number with same weight.
  * Overflows silently.
  * @return 0 if <code>bits</code> is 0 or ~0 */
    static int nextPermutation(int bits) {
        if (0 == bits || ~0 == bits)
            return 0; // throw?
        final int
            smallestBit = bits & -bits,
        // clears all bits in least significant run of 1s,
        //  sets the next more significant one
            ripple = bits + smallestBit,
            oneRunPlus = bits ^ ripple, // longer by one
            leastRun = oneRunPlus/smallestBit, // aligned
            oneRunMinus = leastRun >> 2; // shorter by one
        return ripple | oneRunMinus;
    }
 /** next smaller number with same weight.
  * Silently gives funny results if called with 2ⁿ-1
  *  (just one run of 1s in the least significant positions).
  * @return ~0 if <code>bits</code> is 0 or ~0 */
    static int previousPermutation(int bits) {
        return ~nextPermutation(~bits);
    }

(For decent handling of most significant bit set (see previousPermutation(), too), use oneRunMinus = (oneRunPlus >>> 2) / smallestBit - just slightly harder to read and explain.)

Answer 5

Before I hint you to a better program let's dissect your program for optimisation. Find my inputs as COMMENTS in the program:

void printNextNumber(int num){
    // COMMENT: Do you wish to support negative numbers. If not, you could save time barring them.
    // COMMENT: How about if the number is 0, why go through all the hassles.
    // COMMENT: If its power of 2, next largest is *2 and smallest is /2 :) Just a tip in case you want faster exit.

    int inputNumOfBits = calcBits(num);
    // COMMENT: Nitpick: The name should reflect numOfSetBits and function getNumOfSetBits 

    int  nextLargest = num + 1, nextSmallest = num - 1;

    //nextLargest
    while (true){
        if (calcBits(nextLargest) == inputNumOfBits){
            break;
        }
        nextLargest++;
    }

    //nextSmallest
    while (true){
        if (calcBits(nextSmallest) == inputNumOfBits){
            break;
        }
        nextSmallest--;
    }
    System.out.println("Next largest: " + nextLargest);
    System.out.println("Next smallest: " + nextSmallest);
}

private int calcBits(int x){
    int count = 0;
    int i = 0;

    while (i < 32){ 
        //COMMENT: Why worry if "(1<<i)" is greater than x. Have that check.
        if ((x & (1<<i)) != 0){
            count++;
        }
        i++;
    }
    return count;
    //COMMENT: For this same algorithm, how about dividing x i.e 
    // while(x>0) { if(x&1 ==1) count++; x=x>>1;}
}

About the algo:

• For "calcBits" there are algorithm of O(1) complexity. Try exploring those.
• Try searching for "get next number with same set bits" and you will get better algorithms. Example: http://algorithmsandme.in/2014/04/next-smallest-number-with-same-number-of-bits-set/
• Same applies for get next smallest number. Play the bits.