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

Practice

1. What does the expression REGISTER |= (1 << 3); do in embedded C?

easy

A. Clears the 3rd bit (bit position 2) of REGISTER to 0

B. Sets the 4th bit (bit position 3) of REGISTER to 1 without changing other bits

C. Toggles all bits of REGISTER

D. Resets REGISTER to zero

Solution

1. Step 1: Understand bit shifting

   The expression 1 << 3 shifts the number 1 three places to the left, resulting in binary 00001000, which targets bit position 3.

2. Step 2: Apply bitwise OR to set bit

   Using |= with this mask sets bit 3 to 1 in REGISTER without changing other bits.

3. Final Answer:

   Sets the 4th bit (bit position 3) of REGISTER to 1 without changing other bits -> Option B

4. Quick Check:

   Bit shift + OR sets specific bit = A [OK]

Hint: Use |= with (1 << bit) to set that bit only [OK]

Common Mistakes:

• Confusing bit positions starting from 1 instead of 0
• Using & instead of | to set bits
• Thinking it clears bits instead of setting

2. Which of the following is the correct syntax to set bit 5 of a register named PORTA?

easy

A. PORTA = 1 << 5;

B. PORTA ^= (1 << 5);

C. PORTA &= ~(1 << 5);

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

Solution

1. Step 1: Identify correct operator to set bit

   To set a bit without affecting others, use bitwise OR assignment |= with a mask.

2. Step 2: Check the bit mask and syntax

   1 << 5 creates a mask for bit 5. Combining with |= sets that bit.

3. Final Answer:

   PORTA |= (1 << 5); -> Option D

4. Quick Check:

   Use |= with shifted 1 to set bit [OK]

Hint: Use |= with (1 << bit) to set bit correctly [OK]

Common Mistakes:

• Using = instead of |= overwrites all bits
• Using &= ~ to clear bits, not set
• Using ^= toggles bits instead of setting

3. Given unsigned char REG = 0x12; (binary 00010010), what is the value of REG after executing REG |= (1 << 4);?

medium

A. 0x32

B. 0x12

C. 0x16

D. 0x10

Solution

1. Step 1: Convert initial REG value to binary

   0x12 in binary is 00010010. Bit positions (0 to 7) from right to left.

2. Step 2: Calculate mask and apply OR

   1 << 4 is 00010000 (bit 4 set). OR with 00010010 results in 00110010 (0x32).

3. Final Answer:

   0x32 -> Option A

4. Quick Check:

   0x12 | 0x10 = 0x32 [OK]

Hint: Convert hex to binary, OR with mask, convert back [OK]

Common Mistakes:

• Miscounting bit positions starting from 1
• Confusing hex and decimal values
• Using &= or ^= instead of |=

4. Identify the error in the following code snippet intended to set bit 2 of REG:

unsigned char REG = 0x00;
REG = REG & (1 << 2);

medium

A. Using & instead of | clears all bits except bit 2

B. Bit shift operator << is used incorrectly

C. REG should be declared as int, not unsigned char

D. No error, code correctly sets bit 2

Solution

1. Step 1: Analyze bitwise AND usage

   The code uses & with mask (1 << 2), which clears all bits except bit 2.

2. Step 2: Understand effect on REG

   Since REG starts at 0, AND with mask results in 0, not setting bit 2. To set bit 2, OR |= should be used.

3. Final Answer:

   Using & instead of | clears all bits except bit 2 -> Option A

4. Quick Check:

   Use |= to set bits, & clears bits [OK]

Hint: Use |= to set bits, & clears bits [OK]

Common Mistakes:

• Confusing & and | operators
• Assuming &= sets bits
• Ignoring initial value of REG

5. You have a 16-bit register REG16 initially set to 0x0000. Write the correct statement to set bits 0, 7, and 15 simultaneously without affecting other bits.

hard

A. REG16 = (1 << 0) | (1 << 7) | (1 << 15);

B. REG16 = (1 << 0) & (1 << 7) & (1 << 15);

C. REG16 |= (1 << 0) | (1 << 7) | (1 << 15);

D. REG16 |= (1 << 0) & (1 << 7) & (1 << 15);

Solution

1. Step 1: Create mask for bits 0, 7, and 15

   Use bitwise OR to combine masks: (1 << 0) | (1 << 7) | (1 << 15) sets bits 0, 7, and 15.

2. Step 2: Use |= to set bits without clearing others

   Using |= applies the mask to REG16, setting those bits while preserving others.

3. Final Answer:

   REG16 |= (1 << 0) | (1 << 7) | (1 << 15); -> Option C

4. Quick Check:

   Combine masks with | and set with |= [OK]

Hint: Combine bit masks with | and set with |= [OK]

Common Mistakes:

• Using & instead of | to combine masks
• Using = overwrites all bits, losing previous data
• Using & instead of | in assignment