Why bitwise operations are essential in embedded in Embedded C - Performance Analysis

Time Complexity: Why bitwise operations are essential in embedded

O(1)

Understanding Time Complexity

Bitwise operations are very common in embedded programming because they work directly with bits, the smallest data units.

We want to understand how the time to run bitwise operations changes as input size grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

unsigned int set_bit(unsigned int num, int pos) {
    return num | (1U << pos);
}

unsigned int clear_bit(unsigned int num, int pos) {
    return num & ~(1U << pos);
}

unsigned int toggle_bit(unsigned int num, int pos) {
    return num ^ (1U << pos);
}
    

This code sets, clears, or toggles a single bit in an integer using bitwise operations.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Single bitwise operation per function call.
• How many times: Each function runs a fixed number of steps regardless of input size.

How Execution Grows With Input

Each bitwise operation works on fixed-size data (like 32 bits), so the time does not grow with input size.

Input Size (bits)	Approx. Operations
8	3
16	3
32	3

Pattern observation: The number of operations stays the same no matter how many bits the number has.

Final Time Complexity

Time Complexity: O(1)

This means the time to perform bitwise operations is constant and does not increase with input size.

Common Mistake

[X] Wrong: "Bitwise operations take longer as the number gets bigger because there are more bits to handle."

[OK] Correct: Bitwise operations work on fixed-size registers, so they take the same time regardless of the number's size.

Interview Connect

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

Self-Check

"What if we used a loop to set multiple bits one by one? How would the time complexity change?"

Practice

1. Why are bitwise operations essential in embedded systems?

easy

A. They allow direct control of individual hardware bits efficiently.

B. They simplify writing high-level user interfaces.

C. They automatically optimize memory usage without programmer input.

D. They replace the need for any arithmetic operations.

Solution

1. Step 1: Understand embedded system needs

   Embedded systems often interact directly with hardware registers where each bit controls a specific function.

2. Step 2: Role of bitwise operations

   Bitwise operations let programmers set, clear, or check these individual bits efficiently without affecting others.

3. Final Answer:

   They allow direct control of individual hardware bits efficiently. -> Option A

4. Quick Check:

   Bitwise = hardware bit control [OK]

Hint: Bitwise = control bits directly in hardware [OK]

Common Mistakes:

• Thinking bitwise operations are for UI design
• Assuming bitwise auto-optimizes memory
• Confusing bitwise with arithmetic operations

2. Which of the following is the correct syntax to set the 3rd bit of a variable flags in embedded C?

easy

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

B. flags = flags & (1 << 3);

C. flags = flags ^ (1 << 3);

D. flags = flags << 3;

Solution

1. Step 1: Identify bit position and operation

   The 3rd bit means bit index 2 (counting from 0). To set a bit, use OR with 1 shifted left by that bit index.

2. Step 2: Check each option

   flags = flags | (1 << 2); correctly uses OR and shifts 1 by 2. flags = flags & (1 << 3); uses AND which clears bits, flags = flags ^ (1 << 3); toggles bit, flags = flags << 3; shifts the whole variable.

3. Final Answer:

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

4. Quick Check:

   Set bit = OR with 1<

Hint: Set bit = OR with 1 shifted to bit position [OK]

Common Mistakes:

• Using AND instead of OR to set bits
• Confusing bit index counting from 1 instead of 0
• Using XOR which toggles instead of sets

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

unsigned char flags = 0b00001010;
flags = flags & ~(1 << 3);
printf("%u", flags);

medium

A. 8

B. 10

C. 2

D. 0

Solution

1. Step 1: Analyze initial value and bit to clear

   flags starts as binary 00001010 (decimal 10). Bit 3 (zero-based) is the 4th bit from right, which is currently 1.

2. Step 2: Apply bitwise AND with negated mask

   Mask is (1 << 3) = 00001000. Negated mask is 11110111. ANDing clears bit 3: 00001010 & 11110111 = 00000010 (decimal 2).

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Clear bit 3 = 2 [OK]

Hint: Clear bit = AND with negated (1 << bit) [OK]

Common Mistakes:

• Forgetting to negate mask before AND
• Miscounting bit positions starting at 1
• Assuming XOR clears bits

4. Identify the error in this code snippet intended to toggle the 1st bit of status:

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

medium

A. Using OR instead of AND for toggling.

B. Incorrect bit position; should use (1 << 1).

C. Missing parentheses around the entire expression.

D. Using AND instead of XOR to toggle the bit.

Solution

1. Step 1: Understand toggling operation

   Toggling a bit means flipping it: 0 to 1 or 1 to 0. This is done using XOR with 1 at that bit position.

2. Step 2: Analyze given code

   The code uses AND with (1 << 0), which clears all bits except bit 0, not toggling it.

3. Final Answer:

   Using AND instead of XOR to toggle the bit. -> Option D

4. Quick Check:

   Toggle bit = XOR with 1<

Hint: Toggle bit = XOR with 1 shifted to bit [OK]

Common Mistakes:

• Using AND or OR instead of XOR to toggle
• Confusing bit positions starting at 1
• Assuming toggling clears bits

5. You have a hardware register reg where bits 0-3 represent sensor states. Write a bitwise expression to check if sensors 1 and 3 (bits 0 and 2) are both ON (set to 1). Which expression correctly returns true if both are ON?

hard

A. (reg & (1 << 1)) && (reg & (1 << 3))

B. (reg & ((1 << 0) | (1 << 2))) == ((1 << 0) | (1 << 2))

C. (reg | ((1 << 0) & (1 << 2))) == ((1 << 0) & (1 << 2))

D. (reg ^ ((1 << 0) | (1 << 2))) == 0

Solution

1. Step 1: Identify bits to check

   Bits 0 and 2 correspond to sensors 1 and 3. We want to confirm both bits are set to 1.

2. Step 2: Understand bitwise check for multiple bits

   Using AND with mask of bits 0 and 2, then comparing result to mask ensures both bits are ON.

3. Step 3: Evaluate options

   (reg & ((1 << 0) | (1 << 2))) == ((1 << 0) | (1 << 2)) correctly uses AND with mask and compares to mask. (reg | ((1 << 0) & (1 << 2))) == ((1 << 0) & (1 << 2)) misuses OR and AND. (reg & (1 << 1)) && (reg & (1 << 3)) checks wrong bits (1 and 3). (reg ^ ((1 << 0) | (1 << 2))) == 0 uses XOR which is incorrect for this check.

4. Final Answer:

   (reg & ((1 << 0) | (1 << 2))) == ((1 << 0) | (1 << 2)) -> Option B

5. Quick Check:

   Check bits ON = AND mask == mask [OK]

Hint: Check bits ON = AND with mask equals mask [OK]

Common Mistakes:

• Using OR instead of AND for checking bits
• Checking wrong bit positions
• Using XOR which does not confirm both bits set