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

Time Complexity: Setting a specific bit in a register

O(1)

Understanding Time Complexity

We want to see how the time needed changes when we set a bit in a register.

How does the number of steps grow as the input changes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void set_bit(volatile unsigned int *reg, unsigned int bit_pos) {
    *reg |= (1U << bit_pos);
}
    

This code sets one specific bit in a hardware register using bitwise OR and a shift.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single bit shift and bitwise OR operation.
• How many times: Exactly once per function call.

How Execution Grows With Input

Setting a bit always takes the same number of steps, no matter which bit position is chosen.

Input Size (bit position)	Approx. Operations
10	1
100	1
1000	1

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

Final Time Complexity

Time Complexity: O(1)

This means the time to set a bit does not grow with the bit position; it is always constant.

Common Mistake

[X] Wrong: "Setting a higher bit position takes more time because the shift is bigger."

[OK] Correct: The shift operation is done in hardware and takes the same time regardless of bit position.

Interview Connect

Understanding constant time operations like setting a bit helps you explain how low-level code runs efficiently and why some operations are very fast.

Self-Check

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