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 basic steps computers use to handle numbers at the smallest level.

We want to understand how the time needed changes when we do these operations on numbers of different sizes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

unsigned int a = 29;       // 0001 1101
unsigned int b = 15;       // 0000 1111

unsigned int c_and = a & b;  // AND operation
unsigned int c_or = a | b;   // OR operation
unsigned int c_xor = a ^ b;  // XOR operation
unsigned int c_not = ~a;     // NOT operation
unsigned int c_left = a << 2; // Left shift by 2
unsigned int c_right = a >> 2; // Right shift by 2
    

This code performs basic bit operations on two numbers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Each bitwise operation processes all bits of the number.
• How many times: Once per bit in the number (e.g., 32 bits for unsigned int).

How Execution Grows With Input

Each operation looks at every bit once, so the time grows with the number of bits.

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

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

Final Time Complexity

Time Complexity: O(b)

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

Common Mistake

[X] Wrong: "Bitwise operations take constant time regardless of number size."

[OK] Correct: Actually, the time depends on how many bits the number has, because each bit is processed once.

Interview Connect

Understanding bit operations and their time helps you write efficient low-level code and answer questions about performance clearly.

Self-Check

"What if we used 128-bit numbers instead of 32-bit? How would the time complexity change?"

Practice

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

easy

A. 0

B. 1

C. 6

D. 7

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 where both are 1 remain 1).

3. Final Answer:

   1 -> Option B

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 decimal to binary correctly
• Assuming bitwise AND adds numbers

2. Which of the following is the correct syntax for performing a left shift by 2 bits on an integer variable x in C++?

easy

A. x << 2;

B. x >> 2;

C. x <<< 2;

D. x >> 2 <<;

Solution

1. Step 1: Understand left shift operator

   In C++, left shift is done using << operator.

2. Step 2: Check syntax correctness

   x << 2; uses x << 2; which is correct syntax for left shift by 2 bits.

3. Final Answer:

   x << 2; -> Option A

4. Quick Check:

   Left shift uses << operator [OK]

Hint: Left shift uses <<, right shift uses >> [OK]

Common Mistakes:

• Using >>> which is not valid in C++
• Confusing left shift with right shift
• Adding extra symbols after operator

3. What is the output of the following C++ code?

int x = 12;  // binary 1100
int y = 5;   // binary 0101
int z = x ^ y;
std::cout << z << std::endl;

medium

A. 8

B. 15

C. 9

D. 7

Solution

1. Step 1: Convert numbers to binary

   x = 12 (1100), y = 5 (0101).

2. Step 2: Perform bitwise XOR

   1100 XOR 0101 = 1001 (bits differ become 1).

3. Step 3: Convert result back to decimal

   1001 in decimal is 9.

4. Final Answer:

   9 -> Option C

5. Quick Check:

   12 ^ 5 = 9 [OK]

Hint: XOR sets bits where inputs differ [OK]

Common Mistakes:

• Mixing XOR with OR or AND
• Not converting binary to decimal correctly
• Assuming XOR adds numbers

4. Identify the error in the following C++ code snippet:

int a = 8;
int b = a >> 2;
int c = ~b;
std::cout << c << std::endl;

medium

A. No error; code runs and prints the result

B. Using bitwise NOT (~) on an integer is invalid

C. Right shift operator (>>) is used incorrectly

D. Missing semicolon after variable declaration

Solution

1. Step 1: Check each operation

   Right shift (>>) on integer 8 by 2 bits is valid: 8 (1000) >> 2 = 2 (0010).

2. Step 2: Check bitwise NOT usage

   Bitwise NOT (~) on integer 2 flips bits; this is valid in C++.

3. Step 3: Verify syntax

   All semicolons are present; code compiles and runs.

4. Final Answer:

   No error; code runs and prints the result -> Option A

5. Quick Check:

   Bitwise NOT and shifts are valid [OK]

Hint: Bitwise NOT and shifts are valid on integers [OK]

Common Mistakes:

• Thinking ~ is invalid on integers
• Confusing shift direction
• Assuming missing semicolon without checking

5. Given an integer n = 29, which of the following expressions correctly clears (sets to 0) the 3rd bit (counting from 0, right to left) using bit manipulation?

hard

A. ~n & (1 << 3)

B. n | (1 << 3)

C. n ^ (1 << 3)

D. n & ~(1 << 3)

Solution

1. Step 1: Understand clearing a bit

   To clear a bit, use AND with NOT mask that has 1 at target bit.

2. Step 2: Analyze each option

   n & ~(1 << 3): n & ~(1 << 3) clears 3rd bit correctly.
   n | (1 << 3): n | (1 << 3) sets 3rd bit.
   n ^ (1 << 3): n ^ (1 << 3) toggles 3rd bit.
   ~n & (1 << 3): ~n & (1 << 3) isolates 3rd bit of inverted n, not clearing.

3. Final Answer:

   n & ~(1 << 3) -> Option D

4. Quick Check:

   Clear bit = AND with NOT mask [OK]

Hint: Clear bit: AND with NOT of bit mask [OK]

Common Mistakes:

• Using OR instead of AND to clear bits
• Confusing toggle (XOR) with clear
• Misunderstanding bit indexing