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?"

Practice

1. Which bitwise operator is used to set a specific bit in a register without changing other bits?
Example: Set bit 3 in register REG

easy

A. Bitwise OR (|)

B. Bitwise AND (&)

C. Bitwise XOR (^)

D. Bitwise NOT (~)

Solution

1. Step 1: Understand setting a bit

   Setting a bit means making that bit 1 without changing others.

2. Step 2: Use bitwise OR

   Bitwise OR with 1 at the target bit sets it to 1, others stay same.

3. Final Answer:

   Bitwise OR (|) -> Option A

4. Quick Check:

   Set bit = OR [OK]

Hint: Use OR (|) to set bits without changing others [OK]

Common Mistakes:

• Using AND (&) to set bits (it clears bits)
• Using XOR (^) which toggles bits
• Using NOT (~) which inverts all bits

2. Which of the following C code snippets correctly clears bit 2 of a register named REG?

easy

A. REG = REG | (1 << 2);

B. REG = REG << 2;

C. REG = REG ^ (1 << 2);

D. REG = REG & ~(1 << 2);

Solution

1. Step 1: Understand clearing a bit

   Clearing means setting the bit to 0 without changing others.

2. Step 2: Use AND with NOT mask

   AND with NOT of (1 shifted to bit 2) clears bit 2.

3. Final Answer:

   REG = REG & ~(1 << 2); -> Option D

4. Quick Check:

   Clear bit = AND with NOT mask [OK]

Hint: Clear bits with AND and NOT mask (~) [OK]

Common Mistakes:

• Using OR (|) which sets bits
• Using XOR (^) which toggles bits
• Using shift (<<) alone which moves bits

3. Given REG = 0b00001100;, what is the value of REG after executing REG ^= (1 << 3);?

medium

A. 0b00001100

B. 0b00000100

C. 0b00011100

D. 0b00001000

Solution

1. Step 1: Understand XOR toggling

   XOR toggles the bit: if 1 becomes 0, if 0 becomes 1.

2. Step 2: Toggle bit 3 of REG

   Bit 3 is currently 1 (0b00001100). Toggling it changes it to 0, so REG becomes 0b00000100.

3. Final Answer:

   0b00000100 -> Option B

4. Quick Check:

   XOR toggles bit 3 from 1 to 0 [OK]

Hint: XOR (^) flips bits: 1->0 or 0->1 [OK]

Common Mistakes:

• Thinking XOR sets bit instead of toggling
• Confusing bit positions (count from 0)
• Not converting binary correctly

4. What is wrong with this code to check if bit 4 of REG is set?

if (REG & (1 << 4) == 1) {
  // bit 4 is set
}

medium

A. The comparison '== 1' is incorrect; it should check if result is non-zero.

B. The shift operator '<<' is used wrongly; it should be '>>'.

C. The bit number 4 is out of range for an 8-bit register.

D. The code should use OR (|) instead of AND (&) to check bits.

Solution

1. Step 1: Understand bit check expression

   REG & (1 << 4) returns non-zero if bit 4 is set, zero if not.

2. Step 2: Fix comparison

   Comparing to 1 is wrong because bit 4 corresponds to value 16, not 1. Should check if result != 0.

3. Final Answer:

   The comparison '== 1' is incorrect; it should check if result is non-zero. -> Option A

4. Quick Check:

   Check bits by testing non-zero result [OK]

Hint: Check bits by testing if (REG & mask) != 0 [OK]

Common Mistakes:

• Comparing bit check result to 1 instead of non-zero
• Using shift right (>>) instead of left (<<)
• Using OR (|) to check bits which sets bits

5. You want to toggle bits 0, 2, and 5 of an 8-bit register REG simultaneously. Which code correctly does this?

hard

A. REG = REG & ~( (1 << 0) | (1 << 2) | (1 << 5) );

B. REG = REG | ( (1 << 0) & (1 << 2) & (1 << 5) );

C. REG ^= (1 << 0) | (1 << 2) | (1 << 5);

D. REG ^= (1 << 1) | (1 << 3) | (1 << 5);

Solution

1. Step 1: Understand toggling multiple bits

   Toggling means flipping bits. XOR (^) with mask flips bits where mask has 1.

2. Step 2: Create mask for bits 0, 2, and 5

   Mask is (1<<0) | (1<<2) | (1<<5) which sets bits 0, 2, and 5 to 1.

3. Step 3: Apply XOR with mask

   REG ^= mask flips those bits simultaneously.

4. Final Answer:

   REG ^= (1 << 0) | (1 << 2) | (1 << 5); -> Option C

5. Quick Check:

   Toggle bits with XOR and combined mask [OK]

Hint: Toggle multiple bits with XOR and combined mask [OK]

Common Mistakes:

• Using AND with NOT mask which clears bits
• Using AND (&) instead of OR (|) to combine masks
• Using wrong bit positions in mask