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