Bit Manipulation Basics AND OR XOR NOT Left Right Shift in DSA C - Time & Space Complexity

Time Complexity: Bit Manipulation Basics AND OR XOR NOT Left Right Shift

O(b)

Understanding Time Complexity

Bit manipulation operations are very fast and work directly on the bits of numbers.

We want to understand how the time needed changes as the size of the input number grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

unsigned int bitOps(unsigned int x, unsigned int y) {
    unsigned int a = x & y;      // AND
    unsigned int b = x | y;      // OR
    unsigned int c = x ^ y;      // XOR
    unsigned int d = ~x;         // NOT
    unsigned int e = x << 1;     // Left shift
    unsigned int f = y >> 1;     // Right shift
    return a + b + c + d + e + f;
}
    

This code performs basic bitwise operations on two unsigned integers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Each bitwise operation processes all bits of the input numbers.
• How many times: The operations run once each, but internally they handle each bit of the numbers.

How Execution Grows With Input

Each bitwise operation touches every bit of the input numbers.

Input Size (bits)	Approx. Operations
8	About 8 steps per operation
32	About 32 steps per operation
64	About 64 steps per operation

Pattern observation: The time grows linearly with the number of bits in the input.

Final Time Complexity

Time Complexity: O(b)

This means the time grows linearly with the number of bits in the input numbers.

Common Mistake

[X] Wrong: "Bitwise operations take constant time no matter the input size."

[OK] Correct: While bitwise operations are very fast, they actually process each bit, so the time depends on the number of bits in the input.

Interview Connect

Understanding bit manipulation time helps you write efficient low-level code and reason about performance in systems programming and algorithms.

Self-Check

"What if we used a loop to apply bitwise operations on an array of n numbers? How would the time complexity change?"