Reverse Bits of a Number in DSA Python - Time & Space Complexity

Time Complexity: Reverse Bits of a Number

O(1)

Understanding Time Complexity

We want to understand how the time to reverse bits in a number changes as the number size changes.

Specifically, how many steps does it take to flip all bits from right to left?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def reverse_bits(n: int) -> int:
    result = 0
    for i in range(32):
        bit = (n >> i) & 1
        result |= bit << (31 - i)
    return result

This code reverses the bits of a 32-bit integer by checking each bit and placing it in the reversed position.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A loop running 32 times to process each bit.
• How many times: Exactly 32 times, once for each bit in the integer.

How Execution Grows With Input

Since the loop runs a fixed 32 times regardless of the input number, the operations stay the same.

Input Size (n)	Approx. Operations
10 (small number)	32 steps
100 (larger number)	32 steps
1000 (even larger)	32 steps

Pattern observation: The number of steps does not grow with input size; it stays constant.

Final Time Complexity

Time Complexity: O(1)

This means the time to reverse bits is constant and does not increase as the input number grows.

Common Mistake

[X] Wrong: "The time to reverse bits depends on the value of the number or its size."

[OK] Correct: The code always processes a fixed number of bits (32), so time does not change with the number's value.

Interview Connect

Understanding fixed-time operations like bit manipulation shows you can reason about low-level efficiency, a valuable skill in many coding challenges.

Self-Check

What if we changed the code to reverse bits of a 64-bit number? How would the time complexity change?