Reverse Bits

The problem

n is a whole number that is never negative and fits in 32 bits, the 0s and 1s a computer stores it as. Write n as exactly 32 bits, with 0s in front if needed, and reverse their order: the last bit becomes the first and the first becomes the last. Return the number the reversed bits stand for. The answer is never negative either.

What to write

function solve(n: number): number

Input
n = 43261596

Output
964176192

Input
n = 0

Output
0

Constraints

Unsigned integer n from 0 through 4,294,967,295.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   n always has exactly 32 bits, however small it is, so the 0s in front count too: reversed, they land at the back. The reversed number can have its top bit, the leftmost of the 32, on. That makes it larger than 2 billion, so check how your language treats a number that large in bit operations.

2. Hint 2: Ask a smaller question

   Shrink the problem to 8 bits and reverse 00001101 by hand. Now do it again, taking one bit of the input at a time from the right and writing the output one bit at a time. Where must each new bit go so that the first bit you took ends up on the far left?

3. Hint 3: Name the pattern

   Moving single bits to new places signals bit manipulation. n & 1, an AND with 1, is the lowest bit of n, its rightmost. The shift << slides every bit one place left and leaves a 0 at the right end; >> slides them right and drops the lowest. OR, written |, keeps a 1 where either number has one. Read the lesson on bit manipulation.

4. Hint 4: State the invariant

   After k rounds, the result holds the rightmost k bits of the original n in reverse order, and n has lost those k bits. Each round moves one more bit across. After 32 rounds all 32 bits have moved, and the first one taken has been pushed to the leftmost place.

5. Hint 5: Sketch the pseudocode

   Set result to 0. Repeat exactly 32 times: shift result left by one, OR in the lowest bit of n, then shift n right by one. Return result. If your language's bit operators can give a negative number, read the 32 bits as unsigned, meaning never negative, before you return.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Repeat exactly 32 times: append the input's lowest bit to the output and shift the input right. In JavaScript, read the result through >>> 0 at the end so that it is never negative; Python needs no such step.

The slow way

Write n as text, 32 binary digits long, reverse the text and turn it back into a number. It is correct, but it builds and reverses strings to do what a few bit operations do directly. It also hides a trap: without the padding to 32 digits the 0s in front are lost, and 1 comes back as 1 instead of 2147483648.

The insight

Take the bits of n from the right, one at a time, and append each to the right end of the result. Every new bit pushes the earlier ones one place to the left. So the bit taken first is pushed the furthest, 31 places, to the far left, and the bit taken last stays on the far right. That is the reversed order.

Step by step

1. Start the result at 0. Every bit of 0 is off, so the result starts empty. After the loop it holds only the bits copied in from n, each in its new place.
2. Repeat 32 times, once for every bit of n. All 32 places have to move, the 0s in front of n included. A loop that stops when n runs out of 1 bits leaves the result short: 1 comes back as 1 instead of 2147483648.
3. Shift the result left and put the lowest bit of n in the gap. <<, a left shift, moves the result's bits one place left and leaves a 0 on the right. & with 1, an AND, keeps only the rightmost bit of n. |, an OR, writes that bit into the 0.
4. Shift n right to drop the bit that was copied. The right shift, >> in Python and >>> in JavaScript's reference, moves every bit of n one place right. The copied bit falls off the end, and the next bit becomes the rightmost, ready for the next round.
5. Return the result, read as an unsigned 32-bit number. Unsigned means never negative. JavaScript's bit operators read 32 bits with the leftmost one on as a negative number, so the JavaScript reference converts with >>> 0. Python integers have no fixed width, so the result is already right.

The same numbered steps are the comments in each solution.

function solve(n) {
  // 1. Start the result at 0
  let result = 0;
  // 2. Repeat 32 times, once for every bit of n
  for (let i = 0; i < 32; i++) {
    // 3. Shift the result left and put the lowest bit of n in the gap
    result = (result << 1) | (n & 1);
    // 4. Shift n right to drop the bit that was copied
    // >>> always fills the leftmost place with a 0.
    n >>>= 1;
  }
  // 5. Return the result, read as an unsigned 32-bit number
  // << and | can give a negative number; >>> 0 reads the same 32 bits as unsigned.
  return result >>> 0;
}

function solve(n: number): number {
  // 1. Start the result at 0
  let result = 0;
  // 2. Repeat 32 times, once for every bit of n
  for (let i = 0; i < 32; i++) {
    // 3. Shift the result left and put the lowest bit of n in the gap
    result = (result << 1) | (n & 1);
    // 4. Shift n right to drop the bit that was copied
    // >>> always fills the leftmost place with a 0.
    n >>>= 1;
  }
  // 5. Return the result, read as an unsigned 32-bit number
  // << and | can give a negative number; >>> 0 reads the same 32 bits as unsigned.
  return result >>> 0;
}

def solve(n):
    # 1. Start the result at 0
    result = 0
    # 2. Repeat 32 times, once for every bit of n
    for _ in range(32):
        # 3. Shift the result left and put the lowest bit of n in the gap
        result = (result << 1) | (n & 1)
        # 4. Shift n right to drop the bit that was copied
        n >>= 1
    # 5. Return the result, read as an unsigned 32-bit number
    # Python ints never wrap around, so result is already unsigned.
    return result

Example 1, traced

Input
n = 43261596

Output
964176192

Why it works

After every round the result holds the bits taken so far in reverse order, because each new bit goes in on the right and pushes the earlier ones left. Exactly 32 rounds take all 32 bits of n, the 0s in front included. By then the rightmost bit of n has been pushed left 31 times, to the far left, and every other bit sits in its mirror place.

Time and space

Time O(1), exactly 32 iterations, extra space O(1). The loop always runs exactly 32 times, whatever n is, and every round does the same few bit operations, so the time is O(1). Only the result, what is left of n and the round counter are kept, so the extra space is O(1).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Run all 32 rounds, even after n has become 0. The rounds that add 0s push the earlier bits left to their places. A loop that stops when n is 0 returns 15065253 for the first example instead of 964176192.
• In JavaScript, return the result through >>> 0. Its << and | read the leftmost of the 32 bits as a minus sign, so otherwise every odd n comes back negative: 1 returns -2147483648, not 2147483648. Python needs no conversion.
• Shift the result before you add the new bit, not after. Adding first and shifting after moves every bit one place too far: for n = 1, Python returns 4294967296 and JavaScript returns 0, where the answer is 2147483648.

Pattern

Bit manipulation. Builds on Number of 1 Bits.

Keep going