Reverse Bits

Reverse Bits looks trivial and catches many candidates with one bug: stopping early. It tests whether you can move bits between two numbers with shifts, and whether you respect a fixed width — something Python never enforces for you.

The problem

You get a 32-bit unsigned integer. Reverse the order of its 32 bits — bit 0 becomes bit 31, bit 1 becomes bit 30, and so on — and return the result as an unsigned integer.

Example 1. 43261596 → 964176192.

input : 00000010100101000001111010011100   (43261596)output: 00111001011110000010100101000000   (964176192)

Example 2. 1 → 2147483648. The single 1 bit travels from position 0 to position 31, which is 2³¹.

Constraints. The input has exactly 32 bits, including leading zeros.

Clarifying questions

• Are the leading zeros part of the input? Yes — this is the whole point. 1 is 31 zeros and a 1, and all 32 positions are reversed.
• Signed or unsigned output? Unsigned, so the answer can be up to 4,294,967,295. (In Java the method would return a signed int, and the bit pattern is what counts.)
• Will it be called many times? Possibly — that is the usual follow-up.

Approach 1: the simple way

Turn the number into a 32-character binary string, reverse the string, and parse it back.

def reverse_bits_string(n: int) -> int:    """Format as 32 binary digits, reverse the text, parse it back."""    return int(format(n, "032b")[::-1], 2)

format(n, "032b") pads to 32 digits, which handles the leading zeros correctly. This is O(32) time and it is correct. It is not "too slow"; the issue is that it dodges the question. An interviewer asking this wants to see you move bits with shifts, and in C or Java there is no convenient string route. Mention it as a check, then write the bit version.

The key insight

Think of two stacks of bits. Take bits off the bottom of the input, one at a time, with n & 1 and n >>= 1. Put each one onto the bottom of the result, after first shifting the result left to make room: result = (result << 1) | bit.

The first bit taken from the input is bit 0. It is placed into the result first, and then 31 more shifts push it up to position 31. The last bit taken, bit 31, is placed last and stays at position 0. The order has flipped.

The width matters. The loop must run exactly 32 times, even if the input runs out of 1 bits early, because the later shifts are what move the early bits into place.

Approach 2: shift out, shift in, 32 times

1def reverse_bits(n: int, width: int = 32) -> int:2    """Move bits one at a time from the bottom of n to the bottom of result."""3    result = 04    for _ in range(width):5        result = (result << 1) | (n & 1)    # make room, then append n's lowest bit6        n >>= 1                             # drop the bit we just used7    return result

Step by step:

1. result << 1 moves everything placed so far one position up.
2. | (n & 1) drops n's lowest bit into the empty position 0.
3. n >>= 1 exposes the next bit.
4. After width rounds, every bit has moved.

The width parameter defaults to 32. Here it lets us dry-run a readable 8-bit case.

Dry run with width = 8 on 13 = 00001101. The answer should be 10110000 = 176.

Look at rounds 5 to 8. n is already 0, and a loop written as while n: would have stopped after round 4 and returned 11 — the bits reversed but sitting in the wrong place. The last four rounds do no reading, only shifting, and that shifting is what makes the answer 176.

Complexity. O(32) time — O(w) for width w — and O(1) space.

Approach 3: swap halves, then quarters, down to single bits

There is a version with no loop. Swap the two 16-bit halves. Then, inside each half, swap the two 8-bit bytes. Then the 4-bit nibbles, then 2-bit pairs, then neighbouring bits. After five swaps every bit has travelled to its mirror position.

1def reverse_bits_swap(n: int) -> int:2    """Reverse 32 bits in five swap steps using masks."""3    n = ((n >> 16) | (n << 16)) & 0xFFFFFFFF                 # swap 16-bit halves4    n = ((n >> 8) & 0x00FF00FF) | ((n << 8) & 0xFF00FF00)    # swap bytes5    n = ((n >> 4) & 0x0F0F0F0F) | ((n << 4) & 0xF0F0F0F0)    # swap nibbles6    n = ((n >> 2) & 0x33333333) | ((n << 2) & 0xCCCCCCCC)    # swap pairs7    n = ((n >> 1) & 0x55555555) | ((n << 1) & 0xAAAAAAAA)    # swap neighbours8    return n

Each mask selects the right half of every group. 0x55555555 is 0101…0101, the even positions; 0xAAAAAAAA is 1010…1010, the odd ones. Each line shifts one set of groups down, the other set up, and keeps only the bits that landed in the right place. The masks also stop Python's integer from growing past 32 bits.

That is O(log w) = 5 steps. It is how the operation is written in low-level libraries. In an interview, Approach 2 is the expected answer; knowing Approach 3 exists, and roughly how it works, is a strong extra.

All three versions returned the same result on 300 random 32-bit inputs plus 0, 1, 2³¹ and 2³² − 1.

Edge cases

• 0. Every round appends 0; the answer is 0.
• 1. The single bit must travel 31 positions: the answer is 2147483648. This is the input that exposes an early-stopping loop.
• All ones (4294967295). Reversing changes nothing.
• Reversing twice gives back the input — a free self-check in testing.

Follow-ups

• "This is called millions of times." Precompute the reversal of every byte, 256 entries. Split n into four bytes, reverse each with the table, and put them back in the opposite order. Four lookups per call.
• "Reverse only the significant bits" (so 13 = 1101 becomes 1011 = 11). Loop n.bit_length() times instead of 32.
• "In Java, the input arrives as a signed int." Use >>> to shift in zeros; >> would copy the sign bit and break the reversal for inputs with bit 31 set.