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

Time Complexity: Reverse Bits of a Number

O(1)

Understanding Time Complexity

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

Specifically, how does the number of steps grow when we reverse bits of a number?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

unsigned int reverseBits(unsigned int n) {
    unsigned int result = 0;
    for (int i = 0; i < 32; i++) {
        result <<= 1;
        result |= (n & 1);
        n >>= 1;
    }
    return result;
}
    

This code reverses the bits of a 32-bit unsigned integer by shifting and masking each bit.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop runs 32 times, processing one bit each time.
• How many times: Exactly 32 times, once for each bit in the number.

How Execution Grows With Input

Since the loop runs a fixed 32 times regardless of the number's value, the steps do not grow with input size.

Input Size (bits)	Approx. Operations
10	32 (fixed)
100	32 (fixed)
1000	32 (fixed)

Pattern observation: The number of operations stays the same because the bit size is fixed.

Final Time Complexity

Time Complexity: O(1)

This means the time to reverse bits does not grow with input size because the number of bits is fixed.

Common Mistake

[X] Wrong: "The time to reverse bits grows with the number's value or size."

[OK] Correct: The code always processes a fixed number of bits (32), so time depends on bit length, not the number's value.

Interview Connect

Understanding fixed-time operations like bit reversal helps you reason about low-level data manipulation efficiently, a useful skill in many coding challenges.

Self-Check

"What if we changed the input to a variable bit-length number? How would the time complexity change?"