AND for masking bits in Embedded C - Time & Space Complexity

Time Complexity: AND for masking bits

O(n)

Understanding Time Complexity

We want to understand how the time it takes to mask bits using AND changes as the input size grows.

How does the number of operations grow when we apply AND to mask bits in data?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

unsigned int mask_bits(unsigned int value, unsigned int mask) {
    return value & mask;
}

void process_array(unsigned int *arr, unsigned int *masks, int n) {
    for (int i = 0; i < n; i++) {
        arr[i] = mask_bits(arr[i], masks[i]);
    }
}
    

This code applies a bitwise AND mask to each element in an array of integers.

Identify Repeating Operations

• Primary operation: The for-loop that applies the AND mask to each array element.
• How many times: It runs once for each element in the array, so n times.

How Execution Grows With Input

As the array size grows, the number of AND operations grows directly with it.

Input Size (n)	Approx. Operations
10	10 AND operations
100	100 AND operations
1000	1000 AND operations

Pattern observation: The operations increase in a straight line as input size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to mask bits grows directly with the number of elements you process.

Common Mistake

[X] Wrong: "Masking bits with AND is always constant time no matter how many elements there are."

[OK] Correct: While one AND operation is constant time, doing it for many elements means the total time grows with the number of elements.

Interview Connect

Understanding how simple bitwise operations scale helps you explain efficiency clearly and shows you know how loops affect performance.

Self-Check

"What if we nested the masking inside another loop that runs m times? How would the time complexity change?"

Practice

1. What does the bitwise AND operation with a mask do in embedded C?

easy

A. It adds the mask value to the original number.

B. It keeps only the bits where the mask has 1s and turns off others.

C. It flips all bits in the original number.

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

Solution

1. Step 1: Understand bitwise AND with mask

   The AND operation compares each bit of two numbers and returns 1 only if both bits are 1.

2. Step 2: Apply mask logic

   Using a mask with 1s keeps those bits from the original number; 0s turn off bits.

3. Final Answer:

   It keeps only the bits where the mask has 1s and turns off others. -> Option B

4. Quick Check:

   AND with mask = keep bits [OK]

Hint: Mask with 1 keeps bits; 0 clears bits [OK]

Common Mistakes:

• Thinking AND flips bits
• Confusing AND with addition
• Assuming AND shifts bits

2. Which of the following is the correct syntax to mask the lower 4 bits of a variable val in embedded C?

easy

A. val & 0xF

B. val | 0xF

C. val << 4

D. val ^ 0xF

Solution

1. Step 1: Identify mask for lower 4 bits

   Lower 4 bits mask is 0xF (binary 00001111).

2. Step 2: Apply bitwise AND syntax

   Use val & 0xF to keep only lower 4 bits.

3. Final Answer:

   val & 0xF -> Option A

4. Quick Check:

   AND with 0xF masks lower 4 bits [OK]

Hint: Use & with 0xF to keep lower 4 bits [OK]

Common Mistakes:

• Using OR instead of AND
• Using XOR which toggles bits
• Using shift instead of mask

3. What is the output of the following code?

unsigned char val = 0xAB;  // 10101011 in binary
unsigned char mask = 0x0F; // 00001111 in binary
unsigned char result = val & mask;
printf("%02X", result);

medium

A. 0B

B. AF

C. 0A

D. AB

Solution

1. Step 1: Convert values to binary

   val = 10101011, mask = 00001111.

2. Step 2: Perform bitwise AND

   10101011 & 00001111 = 00001011 (binary) = 0x0B (hex).

3. Final Answer:

   0B -> Option A

4. Quick Check:

   AND keeps lower 4 bits = 0B [OK]

Hint: AND keeps bits where mask is 1 [OK]

Common Mistakes:

• Reading hex incorrectly
• Confusing mask bits
• Assuming output is original val

4. The following code is intended to mask the upper 4 bits of val, but it does not work as expected. What is the error?

unsigned char val = 0xAB;  // 10101011
unsigned char mask = 0xF0; // 11110000
unsigned char result = val | mask;
printf("%X", result);

medium

A. Mask value is incorrect

B. Missing parentheses around expression

C. Variable types are wrong

D. Using OR (|) instead of AND (&) for masking

Solution

1. Step 1: Understand masking operation

   Masking to keep bits requires AND (&), not OR (|).

2. Step 2: Identify incorrect operator

   The code uses OR which sets bits instead of masking.

3. Final Answer:

   Using OR (|) instead of AND (&) for masking -> Option D

4. Quick Check:

   Masking needs AND, not OR [OK]

Hint: Mask bits with & not | [OK]

Common Mistakes:

• Using OR instead of AND
• Changing mask value unnecessarily
• Assuming parentheses fix bitwise errors

5. You have a 16-bit sensor data stored in uint16_t data. The upper 8 bits represent temperature, and the lower 8 bits represent humidity. How do you extract only the temperature value using AND masking?

hard

A. temperature = (data | 0xFF00) >> 8;

B. temperature = data & 0x00FF;

C. temperature = (data & 0xFF00) >> 8;

D. temperature = data >> 8;

Solution

1. Step 1: Identify mask for upper 8 bits

   Upper 8 bits mask is 0xFF00 (binary 11111111 00000000).

2. Step 2: Apply AND and shift right

   Use (data & 0xFF00) to keep upper bits, then shift right 8 to get value.

3. Final Answer:

   temperature = (data & 0xFF00) >> 8; -> Option C

4. Quick Check:

   Mask upper 8 bits and shift right [OK]

Hint: Mask upper bits with 0xFF00 then shift right 8 [OK]

Common Mistakes:

• Masking lower bits instead
• Using OR instead of AND
• Forgetting to shift after masking