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