XOR for toggling bits in Embedded C - Time & Space Complexity

Time Complexity: XOR for toggling bits

O(1)

Understanding Time Complexity

We want to see how the time to toggle bits changes as the number of bits grows.

How does the work needed grow when we toggle more bits?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void toggle_bits(unsigned int *num, unsigned int mask) {
    *num = *num ^ mask;
}
    

This code toggles bits in a number using XOR with a mask.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: One XOR operation on the whole number.
• How many times: Exactly once per call, no loops or recursion.

How Execution Grows With Input

The time to toggle bits stays the same no matter how many bits we have.

Input Size (bits)	Approx. Operations
8	1 XOR operation
32	1 XOR operation
64	1 XOR operation

Pattern observation: The operation count does not increase with input size.

Final Time Complexity

Time Complexity: O(1)

This means toggling bits takes the same amount of time no matter how many bits are involved.

Common Mistake

[X] Wrong: "Toggling more bits means more time because each bit changes separately."

[OK] Correct: XOR toggles all bits in one step using a single operation, so time does not grow with bit count.

Interview Connect

Understanding how bitwise operations work efficiently shows you know how low-level code runs fast, a useful skill in many embedded and systems tasks.

Self-Check

"What if we toggled bits one by one in a loop instead of using XOR? How would the time complexity change?"

Practice

1. What does the XOR operator (^) do when used to toggle bits in embedded C?

easy

A. It shifts bits to the left by the mask value.

B. It flips bits where the mask has 1s and leaves others unchanged.

C. It clears all bits to 0 regardless of the mask.

D. It sets all bits to 1 regardless of the mask.

Solution

1. Step 1: Understand XOR operation basics

   XOR flips bits where the mask bit is 1 and keeps bits unchanged where mask bit is 0.

2. Step 2: Apply to toggling bits

   Using XOR with a mask toggles only the bits set in the mask, leaving others unchanged.

3. Final Answer:

   It flips bits where the mask has 1s and leaves others unchanged. -> Option B

4. Quick Check:

   XOR toggles bits = D [OK]

Hint: XOR flips bits only where mask bits are 1 [OK]

Common Mistakes:

• Thinking XOR sets bits to 1 always
• Confusing XOR with AND or OR
• Assuming XOR shifts bits

2. Which of the following is the correct syntax to toggle the 3rd bit (bit 2) of a variable flags using XOR in embedded C?

easy

A. flags = flags ^ (1 << 2);

B. flags = flags | (1 << 2);

C. flags = flags & ~(1 << 2);

D. flags = flags << 2;

Solution

1. Step 1: Identify toggle operation syntax

   To toggle a bit, XOR (^) with a mask having 1 at that bit position is used.

2. Step 2: Check each option

   flags = flags ^ (1 << 2); uses XOR with (1 << 2) which correctly toggles bit 2. Others set, clear, or shift bits incorrectly.

3. Final Answer:

   flags = flags ^ (1 << 2); -> Option A

4. Quick Check:

   Toggle bit syntax = B [OK]

Hint: Use XOR with (1 << bit_position) to toggle bits [OK]

Common Mistakes:

• Using OR instead of XOR to toggle
• Using AND with negated mask to clear bits
• Using shift operator alone

3. What is the output of the following code snippet?

unsigned char flags = 0b00001100;
flags = flags ^ 0b00000110;
printf("0x%02X", flags);

medium

A. 0x06

B. 0x0E

C. 0x0A

D. 0x12

Solution

1. Step 1: Convert initial flags and mask to binary

   flags = 00001100 (0x0C), mask = 00000110 (0x06)

2. Step 2: Apply XOR operation bitwise

   00001100 ^ 00000110 = 00001010 (0x0A)

3. Final Answer:

   0x0A -> Option C

4. Quick Check:

   0x0C ^ 0x06 = 0x0A [OK]

Hint: XOR flips bits where mask is 1, calculate bitwise [OK]

Common Mistakes:

• Adding values instead of XORing
• Misreading binary bits
• Confusing hex output format

4. The following code is intended to toggle bit 1 of status. What is the error?

unsigned int status = 0x01;
status = status & (1 << 1);

medium

A. The code should use OR operator to toggle bits.

B. The mask should be shifted by 2, not 1.

C. The variable should be unsigned char, not unsigned int.

D. Using AND instead of XOR will clear bits instead of toggling.

Solution

1. Step 1: Analyze the operator used

   The code uses AND (&) with mask, which clears bits not set in mask instead of toggling.

2. Step 2: Identify correct operator for toggling

   XOR (^) is the correct operator to toggle bits, not AND (&).

3. Final Answer:

   Using AND instead of XOR will clear bits instead of toggling. -> Option D

4. Quick Check:

   Toggle needs XOR, not AND [OK]

Hint: Toggle bits only with XOR, AND clears bits [OK]

Common Mistakes:

• Confusing AND with XOR for toggling
• Incorrect bit shift amount
• Wrong data type assumption

5. You have a 8-bit register reg initially set to 0b10101010. You want to toggle bits 1, 3, and 5 simultaneously using XOR. Which mask should you use and what will be the final value of reg after toggling?

hard

A. Mask: 0b00101010; Final reg: 0b10000000

B. Mask: 0b01010101; Final reg: 0b11111111

C. Mask: 0b00101010; Final reg: 0b10000010

D. Mask: 0b00010101; Final reg: 0b10111111

Solution

1. Step 1: Create mask for bits 1, 3, and 5

   Bits are zero-indexed from right. Bit 1 = 0b00000010, bit 3 = 0b00001000, bit 5 = 0b00100000. OR them: 0b00101010.

2. Step 2: XOR reg with mask

   reg = 0b10101010 ^ 0b00101010 = 0b10000000.

3. Final Answer:

   Mask: 0b00101010; Final reg: 0b10000000 -> Option A

4. Quick Check:

   Toggle bits 1,3,5 with mask 0x2A = 0x80 [OK]

Hint: Combine bits with OR for mask, XOR to toggle all at once [OK]

Common Mistakes:

• Wrong mask bits set
• Miscounting bit positions
• Incorrect XOR result calculation