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

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

O(n)

Understanding Time Complexity

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

We want to understand how the time to perform these operations changes as the size of the input number grows.

Scenario Under Consideration

Analyze the time complexity of the following bit manipulation operations.

# Example bit operations on integers
x = 42  # binary: 101010
y = 15  # binary: 001111

and_result = x & y      # AND operation
or_result = x | y       # OR operation
xor_result = x ^ y      # XOR operation
not_result = ~x         # NOT operation
left_shift = x << 2     # Left shift by 2 bits
right_shift = x >> 1    # Right shift by 1 bit
    

This code performs basic bitwise operations on two integers.

Identify Repeating Operations

Each bitwise operation processes bits one by one internally.

• Primary operation: Bitwise AND, OR, XOR, NOT, and shifts.
• How many times: Once per bit of the input number.

How Execution Grows With Input

The number of bits depends on the size of the number (n bits).

Input Size (bits)	Approx. Operations
10	About 10 bit operations
100	About 100 bit operations
1000	About 1000 bit operations

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

Final Time Complexity

Time Complexity: O(n)

This means the time to do bit operations grows linearly with the number of bits in the number.

Common Mistake

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

[OK] Correct: Actually, the time depends on how many bits the number has, so bigger numbers take proportionally more time.

Interview Connect

Understanding bit manipulation time helps you write efficient code and explain performance clearly in interviews.

Self-Check

"What if we used fixed-size 32-bit integers instead of arbitrary large integers? How would the time complexity change?"

Practice

1. What is the result of the bitwise AND operation between 5 and 3? (5 = 0101, 3 = 0011 in binary)

easy

A. 1

B. 7

C. 6

D. 0

Solution

1. Step 1: Convert numbers to binary

   5 in binary is 0101, 3 in binary is 0011.

2. Step 2: Perform bitwise AND

   0101 AND 0011 = 0001 (only bits set in both numbers remain set).

3. Final Answer:

   1 -> Option A

4. Quick Check:

   5 & 3 = 1 [OK]

Hint: AND keeps bits set in both numbers only [OK]

Common Mistakes:

• Confusing AND with OR operation
• Not converting numbers to binary before operation
• Assuming decimal addition instead of bitwise AND

2. Which of the following is the correct syntax to perform a left shift by 2 bits on variable x in Python?

easy

A. x <<< 2

B. x >> 2

C. x << 2

D. x >>| 2

Solution

1. Step 1: Understand left shift operator in Python

   Left shift is done using << operator, shifting bits to the left.

2. Step 2: Check syntax options

   Only x << 2 correctly shifts bits left by 2 places.

3. Final Answer:

   x << 2 -> Option C

4. Quick Check:

   Left shift uses << operator [OK]

Hint: Use << for left shift, >> for right shift [OK]

Common Mistakes:

• Using >>> which is not valid in Python
• Confusing left shift with right shift operator
• Using invalid operators like >>|

3. What is the output of the following Python code?

num = 12  # binary 1100
result = num >> 2
print(result)

medium

A. 6

B. 0

C. 48

D. 3

Solution

1. Step 1: Convert number and apply right shift

   12 in binary is 1100. Right shifting by 2 bits removes last two bits: 1100 >> 2 = 0011.

2. Step 2: Convert shifted binary back to decimal

   0011 in binary is 3 in decimal.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   12 >> 2 = 3 [OK]

Hint: Right shift divides number by 2^shift count [OK]

Common Mistakes:

• Confusing right shift with left shift
• Not converting binary back to decimal
• Assuming shift multiplies instead of divides

4. Identify the error in the following code snippet:

value = 10
result = ~value << 1
print(result)

medium

A. Result is -22 due to operator precedence

B. RuntimeError due to invalid shift

C. Result is 21 due to incorrect bitwise NOT

D. SyntaxError due to incorrect operator usage

Solution

1. Step 1: Evaluate bitwise NOT and shift

   ~10 equals -11 (because ~x = -x-1). Then shifting left by 1 bit multiplies by 2: -11 << 1 = -22.

2. Step 2: Check operator precedence and final value

   Because ~ has higher precedence, ~10 is evaluated first, then shifted. So result is -22, but print shows -22.

3. Final Answer:

   Result is -22 due to operator precedence -> Option A

4. Quick Check:

   ~10 << 1 = -22 [OK]

Hint: Bitwise NOT flips bits, watch operator precedence [OK]

Common Mistakes:

• Assuming ~10 is positive
• Ignoring operator precedence between ~ and <<
• Expecting shift to apply before NOT

5. Given two integers a = 9 and b = 14, which expression will toggle the bits where a and b differ?

hard

A. a | b

B. a ^ b

C. a & b

D. ~a

Solution

1. Step 1: Understand toggling bits where numbers differ

   Toggling bits means flipping bits that are different between two numbers.

2. Step 2: Identify bitwise XOR operation

   XOR (^) returns 1 where bits differ and 0 where bits are same, effectively toggling differing bits.

3. Final Answer:

   a ^ b -> Option B

4. Quick Check:

   XOR toggles differing bits [OK]

Hint: XOR flips bits where inputs differ [OK]

Common Mistakes:

• Using AND or OR which do not toggle bits
• Confusing NOT (~) with XOR
• Assuming OR toggles bits