Clearing a specific bit in a register in Embedded C - Time & Space Complexity

Time Complexity: Clearing a specific bit in a register

O(1)

Understanding Time Complexity

We want to understand how the time to clear a bit in a register changes as the input changes.

Specifically, how does the work grow when we clear a bit in a register?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void clear_bit(volatile unsigned int *reg, unsigned int bit_pos) {
    *reg &= ~(1U << bit_pos);
}
    

This code clears a specific bit in a hardware register by using bitwise operations.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single bitwise AND and shift operation.
• How many times: Exactly once per function call, no loops or repeated steps.

How Execution Grows With Input

Clearing a bit always takes the same amount of work, no matter which bit or register.

Input Size (bit position)	Approx. Operations
0	1
15	1
31	1

Pattern observation: The number of operations stays the same regardless of input size.

Final Time Complexity

Time Complexity: O(1)

This means clearing a bit takes a constant amount of time no matter which bit you clear.

Common Mistake

[X] Wrong: "Clearing a higher bit takes longer because the shift is bigger."

[OK] Correct: Bit shifts and bitwise operations are done in fixed time by the processor, so the position does not affect speed.

Interview Connect

Knowing that bitwise operations run in constant time helps you write efficient low-level code and explain performance clearly.

Self-Check

"What if we cleared multiple bits in a loop? How would the time complexity change?"