Register bit manipulation patterns in Embedded C - Time & Space Complexity

Time Complexity: Register bit manipulation patterns

O(1)

Understanding Time Complexity

When working with register bit manipulation, it is important to understand how the number of operations changes as we manipulate bits.

We want to know how the time to set, clear, or toggle bits grows with the number of bits involved.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Set bits in a register based on a mask
void set_bits(volatile unsigned int *reg, unsigned int mask) {
    *reg |= mask;
}

// Clear bits in a register based on a mask
void clear_bits(volatile unsigned int *reg, unsigned int mask) {
    *reg &= ~mask;
}

// Toggle bits in a register based on a mask
void toggle_bits(volatile unsigned int *reg, unsigned int mask) {
    *reg ^= mask;
}
    

This code sets, clears, or toggles bits in a hardware register using bitwise operations with a mask.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Single bitwise operation (OR, AND, XOR) on the register and mask.
• How many times: Exactly once per function call, no loops or repeated steps.

How Execution Grows With Input

Each operation works on the entire register at once, regardless of how many bits are set in the mask.

Input Size (bits in mask)	Approx. Operations
8	1
16	1
32	1

Pattern observation: The time to perform the operation stays the same no matter how many bits are involved.

Final Time Complexity

Time Complexity: O(1)

This means the operation takes the same amount of time no matter how many bits you change.

Common Mistake

[X] Wrong: "Changing more bits means the operation takes longer because it has to handle each bit separately."

[OK] Correct: Bitwise operations work on the whole register at once, so the number of bits set in the mask does not affect the time.

Interview Connect

Understanding that bitwise register operations run in constant time helps you reason about embedded system performance and write efficient low-level code.

Self-Check

"What if we used a loop to set or clear bits one by one instead of a single bitwise operation? How would the time complexity change?"