Reverse Bits (LeetCode 190)

The problem

You get a 32-bit unsigned integer n. Reverse the order of its 32 bits (bit 0 becomes bit 31, bit 1 becomes bit 30, and so on) and return the resulting unsigned integer.

Input:  43261596   (00000010100101000001111010011100)
Output: 964176192  (00111001011110000010100101000000)

Reading the input’s 32 bits backwards gives the output’s 32 bits.

How to think about it

Start with brute force. Convert to a 32-character binary string with format(n, '032b'), reverse it, and parse it back with int(s, 2). That works and is O(1) for fixed width, but it goes through strings, and interviewers want the bit operations.

The key insight: it is like reversing the digits of a number. To reverse the decimal digits of 123 you repeatedly take the last digit (% 10) and append it to the result (res * 10 + d). In binary, the last bit is n & 1, appending is (res << 1) | bit, and dropping the last bit is n >>= 1. Do it exactly 32 times, because leading zeros of n must become trailing zeros of the answer.

Why exactly 32. If you stopped when n became 0, an input like 1 would return 1 instead of 2147483648 (bit 0 moved to bit 31). The fixed count keeps the width right.

Which pattern is this? Bit manipulation: read bits with & 1 and >>, write bits with << and |. The tell is “reverse bits” or any problem that rebuilds a number bit by bit. If the function is called many times, cache the reversal of each byte and combine four lookups.

Approach

1. Set res = 0.
2. Repeat 32 times: shift res left by one and OR in n & 1, then shift n right by one.
3. Return res.

Solution

def reverse_bits(n):
    res = 0
    for _ in range(32):
        res = (res << 1) | (n & 1)   # append n's lowest bit to res
        n >>= 1                      # move to n's next bit
    return res
# reverse_bits(43261596) -> 964176192

Dry run

A small input makes the steps readable. On n = 11 (1011), the first five iterations:

The remaining 27 iterations keep shifting res left and append zeros, so 1101 ends up in the top four bits: the result is 11010000000000000000000000000000, which is 3489660928.

Complexity

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

Edge cases and pitfalls

• n = 0 returns 0.
• n = 1 returns 2147483648 (1 << 31). Stopping the loop early when n hits 0 gives 1, a common bug.
• All ones apart from bit 1 (4294967293) reverses to 3221225471.
• Signed languages. In Java, use >>> (unsigned shift). Python’s ints have no fixed width, so >> on a non-negative value is already safe.

Related problems

• Number of 1 Bits (LeetCode 191): another walk over the 32 bits of an unsigned value.
• Counting Bits (LeetCode 338): uses the same >> 1 and & 1 pair.
• Sum of Two Integers (LeetCode 371): where fixed 32-bit width really matters in Python.