Checking if a bit is set in Embedded C - Time & Space Complexity

Time Complexity: Checking if a bit is set

O(1)

Understanding Time Complexity

We want to understand how the time to check a bit changes as the input changes.

Specifically, how long does it take to find out if a certain bit is set in a number?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

unsigned int isBitSet(unsigned int num, unsigned int pos) {
    return (num & (1U << pos)) != 0;
}
    

This code checks if the bit at position pos in num is set (1) or not (0).

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.

How Execution Grows With Input

The time to check a bit does not grow with the size of the number or the bit position.

Input Size (bit position)	Approx. Operations
10	1
100	1
1000	1

Pattern observation: The operation count stays the same no matter the input size.

Final Time Complexity

Time Complexity: O(1)

This means the time to check a bit is constant and does not depend on the input size.

Common Mistake

[X] Wrong: "Checking a bit takes longer if the bit position is higher."

[OK] Correct: Bitwise operations run in constant time regardless of which bit is checked.

Interview Connect

Knowing that bit checks are constant time helps you write efficient low-level code and answer questions confidently.

Self-Check

"What if we checked multiple bits one by one in a loop? How would the time complexity change?"

Practice

1. What does the expression (num & (1 << 3)) != 0 check in embedded C?

easy

A. If the 1st bit (bit 0) of num is set to 1

B. If the 4th bit (bit 3) of num is set to 1

C. If num is equal to 8

D. If num is an even number

Solution

1. Step 1: Understand the bit shift operation

   The expression 1 << 3 shifts 1 left by 3 bits, creating a mask with only the 4th bit set (value 8).

2. Step 2: Apply bitwise AND to check the bit

   The bitwise AND num & (1 << 3) isolates the 4th bit of num. If this result is not zero, the bit is set.

3. Final Answer:

   Checks if the 4th bit (bit 3) of num is set to 1 -> Option B

4. Quick Check:

   Bitwise AND with mask = non-zero means bit set [OK]

Hint: Use (1 << bit) & num to check bit set quickly [OK]

Common Mistakes:

• Confusing bit position with bit value
• Forgetting bits start at 0
• Using OR instead of AND to check bits

2. Which of the following is the correct syntax to check if the 2nd bit (bit 1) of variable x is set in embedded C?

easy

A. if (x & 1) { /* bit is set */ }

B. if (x | (1 << 1)) { /* bit is set */ }

C. if (x << 1) { /* bit is set */ }

D. if (x & (1 << 1)) { /* bit is set */ }

Solution

1. Step 1: Identify the mask for bit 1

   The mask for the 2nd bit is 1 << 1, which equals 2.

2. Step 2: Use bitwise AND to check the bit

   Using x & (1 << 1) checks if bit 1 is set. If the result is non-zero, the bit is set.

3. Final Answer:

   if (x & (1 << 1)) { /* bit is set */ } -> Option D

4. Quick Check:

   Bitwise AND with shifted 1 checks bit [OK]

Hint: Use & with (1 << bit) to check bits, not | or << alone [OK]

Common Mistakes:

• Using bitwise OR (|) instead of AND (&)
• Using left shift on variable instead of mask
• Checking wrong bit position

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

unsigned int num = 13; // binary 1101
if (num & (1 << 2))
    printf("Bit 2 is set\n");
else
    printf("Bit 2 is not set\n");

medium

A. Compilation error

B. Bit 2 is not set

C. Bit 2 is set

D. No output

Solution

1. Step 1: Convert num to binary and identify bit 2

   Number 13 in binary is 1101. Bits are numbered from 0 (rightmost). Bit 2 is the third bit from right, which is 1.

2. Step 2: Check bit 2 using bitwise AND

   The expression num & (1 << 2) equals 13 & 4 which is 4 (non-zero), so the condition is true.

3. Final Answer:

   Bit 2 is set -> Option C

4. Quick Check:

   Bit 2 in 1101 is 1, so output is "Bit 2 is set" [OK]

Hint: Convert number to binary, check bit position with mask [OK]

Common Mistakes:

• Miscounting bit positions starting at 1 instead of 0
• Assuming bit 2 is zero without checking
• Confusing bitwise AND with OR

4. The following code is intended to check if bit 5 of flags is set. What is the error?

unsigned int flags = 0x20;
if (flags & 5 << 1) {
    // bit is set
}

medium

A. Incorrect operator precedence causes wrong mask

B. Bit shift should be on variable, not constant

C. Missing parentheses around bit shift

D. Using bitwise OR instead of AND

Solution

1. Step 1: Analyze operator precedence in expression

   The expression flags & 5 << 1 is evaluated as flags & (5 << 1) due to operator precedence (<< higher than &).

2. Step 2: Understand the intended mask and fix

   The intended mask is 1 << 5 to check bit 5. The current expression does not create the correct mask.

3. Final Answer:

   Incorrect operator precedence causes wrong mask -> Option A

4. Quick Check:

   Use parentheses: flags & (1 << 5) to fix [OK]

Hint: Always use parentheses around (1 << bit) mask [OK]

Common Mistakes:

• Not using parentheses causing wrong evaluation
• Shifting wrong constant (5 instead of 1)
• Confusing bit positions and mask values

5. You have an 8-bit status register status. Write a condition to check if either bit 1 or bit 3 is set. Which of the following is correct?

hard

A. if (status & ((1 << 1) | (1 << 3))) { /* bit 1 or 3 set */ }

B. if ((status & (1 << 1)) && (status & (1 << 3))) { /* bit 1 or 3 set */ }

C. if (status | (1 << 1) | (1 << 3)) { /* bit 1 or 3 set */ }

D. if (status & (1 << (1 + 3))) { /* bit 1 or 3 set */ }

Solution

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

   Use bitwise OR to combine masks: (1 << 1) | (1 << 3) creates a mask with bits 1 and 3 set.

2. Step 2: Use bitwise AND to check if either bit is set

   Check if status & mask is non-zero to confirm if either bit is set.

3. Final Answer:

   if (status & ((1 << 1) | (1 << 3))) { /* bit 1 or 3 set */ } -> Option A

4. Quick Check:

   Combine masks with |, check with & for any bit set [OK]

Hint: Combine bit masks with | inside parentheses before & [OK]

Common Mistakes:

• Using && instead of | to combine masks
• Using + instead of | causing wrong mask
• Using bitwise OR on variable instead of mask