OR for setting bits in Embedded C - Time & Space Complexity

Time Complexity: OR for setting bits

O(1)

Understanding Time Complexity

We want to understand how the time needed to set bits using OR changes as we work with more bits.

How does the number of operations grow when setting bits in a number?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

unsigned int set_bits(unsigned int num, unsigned int mask) {
    return num | mask;
}
    

This code sets bits in num where mask has bits set, using the OR operation.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Bitwise OR operation between two numbers.
• How many times: The OR operation is done once per call, affecting all bits simultaneously.

How Execution Grows With Input

The OR operation works on all bits at once, so the time does not increase with more bits in a noticeable way.

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

Pattern observation: The time stays about the same no matter how many bits are involved.

Final Time Complexity

Time Complexity: O(1)

This means the time to set bits using OR does not grow with input size; it stays constant.

Common Mistake

[X] Wrong: "Setting bits with OR takes longer if the number has more bits."

[OK] Correct: The OR operation works on all bits at once inside the processor, so it takes the same time regardless of bit size.

Interview Connect

Knowing that bitwise OR runs in constant time helps you explain efficiency clearly and shows you understand how low-level operations work.

Self-Check

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