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

Time Complexity: Set Clear Toggle a Specific Bit

O(1)

Understanding Time Complexity

We want to understand how fast we can change a specific bit in a number.

How does the time to set, clear, or toggle a bit grow as the number size changes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def set_bit(num: int, pos: int) -> int:
    return num | (1 << pos)

def clear_bit(num: int, pos: int) -> int:
    return num & ~(1 << pos)

def toggle_bit(num: int, pos: int) -> int:
    return num ^ (1 << pos)

This code sets, clears, or toggles a bit at a given position in an integer.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

Each operation takes the same amount of time regardless of the number size.

Input Size (bits in number)	Approx. Operations
10	3 simple bitwise operations
100	3 simple bitwise operations
1000	3 simple bitwise operations

Pattern observation: The time stays constant no matter how big the number is.

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 they have more bits."

[OK] Correct: Bitwise operations directly access the bit position without checking all bits, so time stays the same.

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 had to set multiple bits one by one in a loop? How would the time complexity change?"