Reverse Bits

Difficulty: Easy Source: NeetCode

Problem

Reverse bits of a given 32-bit unsigned integer.

Example 1: Input: n = 00000010100101000001111010011100 (binary) Output: 964176192 (00111001011110000010100101000000 in binary)

Example 2: Input: n = 11111111111111111111111111111101 (binary) Output: 3221225471 (10111111111111111111111111111111 in binary)

Constraints:

• The input must be a binary string of length 32.

Follow up: If you call this function many times, how would you optimize it?

Prerequisites

Before attempting this problem, you should be comfortable with:

• Left shift (<<) — multiplies by 2, moving bits to higher positions
• Right shift (>>) — divides by 2, moving bits to lower positions
• Bitwise OR (|) — sets a bit without disturbing others
• Bitwise AND (&) — isolates specific bits

1. Brute Force (String Conversion)

Intuition

Convert the number to a 32-character binary string (zero-padded), reverse it, then convert back to an integer. Python makes this a one-liner, though it sidesteps the actual bit manipulation. The zfill(32) call is important — without it, numbers smaller than 2³¹ would produce a string shorter than 32 characters, and reversing would give the wrong answer.

Algorithm

1. Convert n to a binary string with bin(n)[2:].
2. Zero-pad to exactly 32 characters using .zfill(32).
3. Reverse the string with [::-1].
4. Convert back to integer with int(..., 2).

Solution

def reverseBits(n):
    return int(bin(n)[2:].zfill(32)[::-1], 2)


print(reverseBits(0b00000010100101000001111010011100))  # 964176192
print(reverseBits(0b11111111111111111111111111111101))  # 3221225471
print(reverseBits(0))                                   # 0
print(reverseBits(1))                                   # 2147483648

Complexity

• Time: O(1) — always exactly 32 bits
• Space: O(1) — fixed-length string

2. Bit-by-Bit Reversal

Intuition

Do it the bit manipulation way: run a loop 32 times and move each bit from n to its mirror position in result.

In each iteration:

1. Shift result one position left to make room for the next bit.
2. Read the last bit of n with n & 1 and OR it into result.
3. Right-shift n to discard the bit we just read.

After 32 iterations, result holds all 32 bits of n in reversed order.

Let’s trace a small example with n = 5 = 101 (pretending it’s 4-bit for clarity):

start:    result = 0000,  n = 0101
iter 1:   result = 0001,  n = 0010   (took bit 1)
iter 2:   result = 0010,  n = 0001   (took bit 0)
iter 3:   result = 0100,  n = 0000   (took bit 0)
iter 4:   result = 1000,  n = 0000   (took bit 0... wait, n is 0!)

Hmm — but the loop still runs all 32 (or 4) times even when n becomes 0. That’s correct: those remaining left-shifts push the already-captured bits into the higher positions of result, which is exactly what we want for the reverse.

Algorithm

1. Initialize result = 0.
2. Repeat 32 times:
   • Left-shift result by 1: result <<= 1.
   • OR in the last bit of n: result |= n & 1.
   • Right-shift n by 1: n >>= 1.
3. Return result.

Solution

def reverseBits(n):
    result = 0
    for _ in range(32):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result


print(reverseBits(0b00000010100101000001111010011100))  # 964176192
print(reverseBits(0b11111111111111111111111111111101))  # 3221225471
print(reverseBits(0))                                   # 0
print(reverseBits(1))                                   # 2147483648

Complexity

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

Common Pitfalls

Not zero-padding to 32 bits in the string approach. bin(1) gives '0b1', not 32 characters. Without .zfill(32), the reversed string represents a different number entirely.

Reversing only the significant bits. Reversing 101 gives 101 — but the full 32-bit reversal of 5 = 00000000000000000000000000000101 is 10100000000000000000000000000000 = 2684354560. Always work with all 32 bit positions.

Python integer overflow confusion. Python integers grow arbitrarily, so there’s no overflow here. The result will always be a non-negative 32-bit unsigned integer (0 to 2³² − 1), which Python handles without masking.