Spotify's "Reversed Binary Numbers" Problem I wrote some Java code for Spotify's Reversed Binary Numbers puzzle and I tested it on my machine and I am almost positive that it behaves as expected. However, when I send it to puzzle AT spotify.com it kicks it back saying I have the "wrong answer", and nothing else.

Frustrating as this is, I can't for the life of me seem to figure out why the code I have wouldn't work. I even went so far as to remove all error messages that result from bad input, thinking that maybe that was causing it to fail. I was wondering if anyone here with a keener eye than my own could possibly help me hunt down the bug? 

Here is a snippet of the most relevant portion of the code:

/**
 * Reverse the bits of an integer between 1 ≤ n ≤ 1000000000.
 *    i.e. 11 (1011) becomes 13 (1101)
 *
 * @param n The integer to reverse.
 * @return The reversed integer.
 */
public static int reverseBits(int n) {
  // 1-indexed MSB Position
  int msbPosition = findMSBPosition(n);
  int reversed = 0;

  for (int i = 0; i &lt; msbPosition; i++) {
    int mask = 1 &lt;&lt; i;
    int bit = (n &amp; mask) &gt;&gt; i;
    reversed |= (bit &lt;&lt; (msbPosition - i - 1));
  }

  return reversed;
}

/**
 * Find the 1-indexed position of the MSB of a number.
 *    i.e. For the number 11 (1011), findMSBPosition() would return 4.
 *
 * @param n The number to find the MSB for.
 * @return The 1-indexed position of the MSB.
 * @protected
 */
protected static int findMSBPosition(int n) {
  int msbPos = 0;
  int testNum = 1;
  while (testNum &lt;= n) {
    msbPos++;
    testNum &lt;&lt;= 1;
  }

  return msbPos;
}


The full code can be found in this gist.

As a caveat and as information I am NOT APPLYING TO SPOTIFY NOR HAVE ANY INTENTION TO. I'm just doing this to stay sharp and since "wrong answer" is less than helpful output I'd love to know where I messed up. Thank you so much.
I do not see any problems inside the given range. I would have used already existing methods:

public static int reverse2(final int n) {
    return Integer.valueOf(new StringBuilder(Integer.toBinaryString(n)).reverse().toString(), 2);
}


Which is probably to best readable version.



If we want to do it by ourself and do not want to create a string and stringbuilder:

With recursion:

public static int reverse3(final int newNumber, final int number) {
    if (number == 0)
        return newNumber;
    return reverse3((newNumber &lt;&lt; 1) | (number &amp; 1), number &gt;&gt; 1);
}


Without recursion:

public static int reverse4(int number) {
    int newNumber = 0;
    while (number != 0) {
        newNumber = (newNumber &lt;&lt; 1) | (number &amp; 1);
        number &gt;&gt;= 1;
    }
    return newNumber;
}




Hint: I have only considered the given range. I did not think about negative numbers.



You could try to avoid Scanner and use Integer.parseInt inside a try/catch. Who knows what they throw at you at the command line. The nextInt from Scanner does a Integer.parseInt, but it also tries to match tokens.