3
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ How can I improve this? comment your code. Specify whether negative numbers are to be considered, and how those are represented. Describe the algorithm you use. Tell whether you are after better code for that algorithm, or a better algorithm. (next smallest/largest ? smaller/larger, preceding/succeeding?) \$\endgroup\$ – greybeard Nov 2 '16 at 10:05
  • \$\begingroup\$ improve your wording: nextLargest - there is only one largest. There cannot be a nextLargest. So this should better be nextLarger while nextBigger fits better to the context of numbers \$\endgroup\$ – Timothy Truckle Nov 2 '16 at 10:52
  • \$\begingroup\$ //nextLargest while (){ if (){ break; better put this in a separate method, where you can return from. the "separation comment" tells you that the following code should be places in a method of its own, and the comment content gives you the name of that method. \$\endgroup\$ – Timothy Truckle Nov 2 '16 at 10:57
1
\$\begingroup\$

Using java.lang.Integer.bitCount():

public int nextWithSameBitCount(int i) {
    int bitCount = Integer.bitCount(i);
    do {
        i++;
    } while(Integer.bitCount(i) != bitCount);
    return i;
}
\$\endgroup\$
1
\$\begingroup\$

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();
}
\$\endgroup\$
  • \$\begingroup\$ (Looks too cute not to be right, still isn't correct - try with 3 (or 11).) \$\endgroup\$ – greybeard Nov 5 '16 at 16:31
  • \$\begingroup\$ (Would you believe in Integer.toBinaryString(int) and Integer.parseInt(String, int radix) (for a radix of 2…)?) \$\endgroup\$ – greybeard Nov 5 '16 at 16:36
  • \$\begingroup\$ @greybeard ok, need to adjust a little: find the most right "0" that is followed by a "1" and switch their positions... \$\endgroup\$ – Timothy Truckle Nov 5 '16 at 17:43
  • \$\begingroup\$ Well, no. It isn't easy, starting with giving an example that was meant base then, but can be read base 2. Consider 010110(22): the "same weight neighbours" are 011001(25) and 010101(21). (Or 01011(11): 01101(13) and 00111(7), respectively. It doesn't get any better for odd numbers with just one run of ones, which is why I asked about negative numbers.) \$\endgroup\$ – greybeard Nov 5 '16 at 18:29
  • \$\begingroup\$ Maybe this works: For next bigger, from the least significant run of ones, put one in the next more significant position, the rest (if any) in the least significant positions, with zeroes in every position vacated. For next smaller, just invert before&after. \$\endgroup\$ – greybeard Nov 5 '16 at 19:43
0
\$\begingroup\$
    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.

\$\endgroup\$
  • \$\begingroup\$ (while I like your rendition of bitCount(integer) better, there's, e.g, Integer.bitCount(int).) \$\endgroup\$ – greybeard Nov 5 '16 at 16:31
  • \$\begingroup\$ @greybeard That's already covered in another answer. I'm concentrating on how to make this version better--not to fix this code, but to help the poster with writing future code. It's the pattern that's important, not the solution. Not every similar problem has a built-in solution (although this one does). \$\endgroup\$ – mdfst13 Nov 5 '16 at 19:05
0
\$\begingroup\$

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.)

\$\endgroup\$
0
\$\begingroup\$

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:

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.