Reverse Bits

You are given a non-negative integer n that fits in 32 bits, i.e. 0 <= n < 232. Write it as exactly 32 binary digits (padding with leading zeroes), reverse the order of those 32 digits, and return the value they represent as an unsigned integer.

Bit 0 (the least significant bit) of the input becomes bit 31 of the result, bit 1 becomes bit 30, and so on. Both the input and the output are plain non-negative integers.

Example 1

Example 2

Example 3

Constraints

• 0 <= n <= 232 - 1

Pattern Path · Math, Bits & Strings · problem 35 of 169

Start simple

Format the number as a 32-character binary string, reverse it and parse it back: O(32) time and space, which is fine but avoids the bit operations the problem is about.

The key idea

Treat the input as a queue of bits that you read from the right and the output as a stack of bits you push onto the right.

Each of the 32 steps does two things: shift result left by one to make room, then copy the lowest bit of n into the freed slot with result | (n & 1). Then shift n right to expose its next bit. The first bit read from n has been shifted left 31 times by the end, so it lands in position 31; the last bit read lands in position 0. That is exactly the reversal.

The loop must run all 32 times. Stopping when n reaches 0 would forget to shift the result for the input's leading zeroes, leaving the bits in the wrong positions.

In JavaScript, bitwise operators work on signed 32-bit values, so a result with bit 31 set appears negative; >>> 0 reinterprets it as unsigned. Use >>> rather than >> to shift the input for the same reason.

Complexity

• Time: O(1) (32 iterations)
• Space: O(1)

Python

class Solution:
    def reverseBits(self, n):
        result = 0
        for _ in range(32):
            result = (result << 1) | (n & 1)  # append n's lowest bit
            n >>= 1
        return result

JavaScript

var reverseBits = function(n) {
  let result = 0;
  for (let i = 0; i < 32; i++) {
    result = (result << 1) | (n & 1); // append n's lowest bit
    n >>>= 1;
  }
  return result >>> 0; // read the 32 bits as unsigned
};

What the interviewer is checking

It tests fluency with shifts and masks, and whether you remember fixed-width details like padding and signed versus unsigned interpretation.

Mistakes to avoid

• Stopping when n becomes 0 instead of running all 32 iterations.
• In JavaScript, returning a negative number because bit 31 is set; finish with >>> 0.
• Using an arithmetic right shift (>>) on a value with the top bit set, which drags in copies of the sign bit.

Follow-ups to expect

• If this is called millions of times, how would you speed it up? (Cache reversed bytes in a table.)
• Can you do it without a loop? (Swap halves, bytes, nibbles, pairs with masks.)
• How would you count the set bits instead? (Clear lowest set bit repeatedly.)

In real software

Bit reversal is a step in the Fast Fourier Transform (bit-reversed ordering) and in CRC checksum implementations that process data least significant bit first.

Practice next