Set Clear Toggle a Specific Bit in DSA C - Time & Space Complexity

Time Complexity: Set Clear Toggle a Specific Bit

O(1)

Understanding Time Complexity

We want to understand how fast operations like setting, clearing, or toggling a specific bit run.

How does the time to change one bit grow as the number size grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

unsigned int setBit(unsigned int num, int pos) {
    return num | (1U << pos);
}

unsigned int clearBit(unsigned int num, int pos) {
    return num & ~(1U << pos);
}

unsigned int toggleBit(unsigned int num, int pos) {
    return num ^ (1U << pos);
}
    

This code sets, clears, or toggles a single bit at position pos in the number num.

Identify Repeating Operations

Each function performs a fixed number of bitwise operations.

• Primary operation: Bitwise shift and bitwise AND, OR, XOR.
• How many times: Exactly once per function call, no loops or recursion.

How Execution Grows With Input

The number size does not affect the number of operations since only one bit is changed.

Input Size (bits)	Approx. Operations
8	3
32	3
64	3

Pattern observation: The operations stay the same regardless of input size.

Final Time Complexity

Time Complexity: O(1)

This means the time to set, clear, or toggle a bit does not grow with the size of the number.

Common Mistake

[X] Wrong: "Changing a bit takes longer for bigger numbers because there are more bits to check."

[OK] Correct: Bitwise operations directly access the bit position without checking others, so time stays constant.

Interview Connect

Knowing that bitwise operations run in constant time helps you write efficient low-level code and answer questions confidently.

Self-Check

"What if we tried to set multiple bits at once using a loop? How would the time complexity change?"