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

Practice

1. What does the expression register &= ~(1 << 3); do in embedded C?

easy

A. Sets the 3rd bit of the register to 1

B. Clears the 3rd bit of the register (sets it to 0) without changing other bits

C. Toggles the 3rd bit of the register

D. Clears all bits of the register

Solution

1. Step 1: Understand bit shifting and negation

   The expression 1 << 3 shifts 1 to the left by 3 bits, creating a mask with only the 3rd bit set (00001000).

2. Step 2: Apply bitwise NOT and AND assignment

   The bitwise NOT ~(1 << 3) flips all bits, making the 3rd bit 0 and others 1. ANDing this with the register clears only the 3rd bit.

3. Final Answer:

   Clears the 3rd bit of the register (sets it to 0) without changing other bits -> Option B

4. Quick Check:

   Clear bit 3 = register &= ~(1 << 3) [OK]

Hint: Use AND with NOT mask to clear a bit [OK]

Common Mistakes:

• Confusing clearing with setting a bit
• Using OR instead of AND
• Not applying bitwise NOT before AND

2. Which of the following is the correct syntax to clear bit 5 of a variable named reg?

easy

A. reg &= ~(1 << 5);

B. reg |= ~(1 << 5);

C. reg = reg & (1 << 5);

D. reg = reg | (1 << 5);

Solution

1. Step 1: Identify the operation to clear a bit

   Clearing a bit means setting it to 0. This is done by ANDing with the negation of the bit mask.

2. Step 2: Check each option's operation

   reg &= ~(1 << 5); uses &= ~(1 << 5), which correctly clears bit 5. Others either set or incorrectly manipulate bits.

3. Final Answer:

   reg &= ~(1 << 5); -> Option A

4. Quick Check:

   Clear bit 5 = reg &= ~(1 << 5) [OK]

Hint: Clear bit with AND and NOT mask [OK]

Common Mistakes:

• Using OR (|) instead of AND (&)
• Forgetting to negate the mask
• Assigning instead of using compound assignment

3. Given unsigned char reg = 0b11111111; and the operation reg &= ~(1 << 2);, what is the binary value of reg after execution?

medium

A. 0b11111011

B. 0b11111101

C. 0b11110111

D. 0b11111110

Solution

1. Step 1: Identify the bit to clear

   Bit 2 means the third bit from the right (0-based index). The mask is 1 << 2 = 0b00000100.

2. Step 2: Apply clearing operation

   Negate mask: ~0b00000100 = 0b11111011. AND with reg: 0b11111111 & 0b11111011 = 0b11111011.

3. Final Answer:

   0b11111011 -> Option A

4. Quick Check:

   Clear bit 2 from 0xFF = 0xFB (binary 11111011) [OK]

Hint: Clear bit 2 flips that bit to 0 only [OK]

Common Mistakes:

• Clearing wrong bit index
• Not negating the mask
• Confusing bit positions (1-based vs 0-based)

4. What is wrong with this code snippet if the goal is to clear bit 4 of reg?

reg = reg & (1 << 4);

medium

A. It causes a syntax error

B. It correctly clears bit 4

C. It sets all bits except bit 4 to 0, not clearing bit 4

D. It toggles bit 4 instead of clearing

Solution

1. Step 1: Analyze the operation performed

   The expression reg & (1 << 4) keeps only bit 4 and clears all others, effectively zeroing all bits except bit 4.

2. Step 2: Compare with correct clearing method

   To clear bit 4, we must AND with the negation of the mask: reg &= ~(1 << 4);. The given code does not do this.

3. Final Answer:

   It sets all bits except bit 4 to 0, not clearing bit 4 -> Option C

4. Quick Check:

   AND with mask keeps only that bit [OK]

Hint: AND with mask keeps only that bit, not clears it [OK]

Common Mistakes:

• Using AND with mask instead of negated mask
• Confusing clearing with masking
• Expecting toggling behavior

5. You have a 16-bit register uint16_t reg = 0xFFFF;. You want to clear bits 0, 4, and 15 simultaneously. Which code correctly does this?

hard

A. reg |= ( (1 << 0) | (1 << 4) | (1 << 15) );

B. reg &= ( (1 << 0) | (1 << 4) | (1 << 15) );

C. reg |= ~( (1 << 0) | (1 << 4) | (1 << 15) );

D. reg &= ~( (1 << 0) | (1 << 4) | (1 << 15) );

Solution

1. Step 1: Create a mask for bits to clear

   Bits 0, 4, and 15 correspond to masks 1<<0, 1<<4, and 1<<15. OR them to combine: (1<<0) | (1<<4) | (1<<15).

2. Step 2: Negate mask and AND with register

   Negate the combined mask to get zeros at bits 0,4,15 and ones elsewhere. AND with reg clears those bits.

3. Final Answer:

   reg &= ~( (1 << 0) | (1 << 4) | (1 << 15) ); -> Option D

4. Quick Check:

   Clear multiple bits by AND with negated OR mask [OK]

Hint: Combine bits with OR, negate, then AND to clear multiple bits [OK]

Common Mistakes:

• Using OR instead of AND to clear bits
• Not negating the combined mask
• Clearing only one bit instead of all three