What is the time complexity of Reverse Bits?

The optimal solution has O(1) time complexity and O(1) space complexity.

What pattern does Reverse Bits use?

Reverse Bits uses the Bit Manipulation pattern. Extract rightmost bit, add to result (shifted left), shift input right. Repeat 32 times.

Easy Bit Manipulation ~5 min

bit-manipulation reverse-bits

Reverse bits of a given 32 bits unsigned integer.

Example 1

Input: n = 00000010100101000001111010011100

Output: 964176192 (00111001011110000010100101000000)

Example 2

Input: n = 11111111111111111111111111111101

Output: 3221225471 (10111111111111111111111111111111)

Key Insight

Extract rightmost bit, add to result (shifted left), shift input right. Repeat 32 times.

Extract rightmost bit (n & 1), shift result left and add bit, shift n right. Repeat 32 times to reverse all bits.

Pattern Recognition: When you see keywords like reverse bits bit-manipulation, think Bit Manipulation.

1 To extract the rightmost bit of n:

Answer: n & 1

AND with 1 isolates the last bit.

2 Each extracted bit should go:

Answer: To the mirrored position

Bit at position 0 goes to position 31, etc. Reverse = mirror.

3 For each of 32 bits:

Answer: result = (result << 1) | (n & 1), then n >> 1

Shift result left to make room, OR with extracted bit, shift n right to get next bit.

4 We always iterate:

Answer: Exactly 32 times

Need all 32 bits. Leading zeros in input become trailing zeros in output.

5 If input has leading zeros:

Answer: They become trailing zeros in output

Reversal means position 31 (leading) goes to position 0 (trailing).

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

Time	`O(1)`
Space	`O(1)`

Build intuition with interactive MCQs. Practice Bit Manipulation problems in the LeetEye app.