Bit Manipulation Basics AND OR XOR NOT Left Right Shift in DSA C++ - Execution Trace

Concept Flow - Bit Manipulation Basics AND OR XOR NOT Left Right Shift

Start with two numbers

↓

Choose bitwise operation

↓

Apply operation bit by bit

↓

Combine bits to get result

↓

Output result in binary/decimal

Start with two numbers, pick a bitwise operation, apply it bit by bit, then combine bits to get the result.

Execution Sample

DSA C++

int a = 5;  // 0101 in binary
int b = 3;  // 0011 in binary
int c = a & b; // AND operation

This code performs bitwise AND on 5 and 3, resulting in 1 (0001 in binary).

Execution Table

Step	Operation	Bit Position	a bit	b bit	Result bit	Result (decimal)
1	AND	3 (8's place)	0	0	0	0
2	AND	2 (4's place)	1	0	0	0
3	AND	1 (2's place)	0	1	0	0
4	AND	0 (1's place)	1	1	1	1
5	Combine bits	-	-	-	0001	1
6	END	-	-	-	-	Operation complete

💡 All bits processed, final result is 1

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
a	0101 (5)	0101	0101	0101	0101	0101
b	0011 (3)	0011	0011	0011	0011	0011
result	0000 (0)	0000	0000	0000	0001	0001 (1)

Key Moments - 3 Insights

Why does the AND operation result in 1 instead of 5 or 3?

Because AND compares each bit of a and b; only bits that are 1 in both numbers become 1. See execution_table rows 1-4 where only the last bit is 1 in both.

What happens if we apply NOT to a number?

NOT flips every bit: 0 becomes 1, 1 becomes 0. This is a bitwise inversion, not arithmetic negation.

How does left shift affect the number?

Left shift moves bits to the left, adding zeros on the right, effectively multiplying the number by 2 for each shift.

Visual Quiz - 3 Questions

Look at the execution_table, what is the result bit at bit position 2 during the AND operation?

A 0

B 1

C Undefined

D Same as a bit

💡 Hint

Check row 2 in execution_table under 'Result bit'

At which step does the final decimal result become 1?

A Step 4

B Step 5

C Step 3

D Step 2

💡 Hint

Look at the 'Result (decimal)' column in execution_table

If we replace AND with OR, what would be the result bit at bit position 1?

A 0

B 1

C Same as AND result

D Cannot determine

💡 Hint

OR sets bit to 1 if either bit is 1; check bits of a and b at position 1

Concept Snapshot

Bitwise operations work on individual bits of numbers.
AND: 1 if both bits are 1.
OR: 1 if any bit is 1.
XOR: 1 if bits differ.
NOT: flips bits.
Left shift: moves bits left, multiplies by 2.
Right shift: moves bits right, divides by 2.

Full Transcript

Bit manipulation means working with the bits inside numbers. We start with two numbers and pick an operation like AND, OR, XOR, NOT, or shifts. Each operation looks at bits one by one. For example, AND only keeps bits that are 1 in both numbers. We showed how 5 AND 3 works by checking each bit position and combining the results. Variables a and b stay the same, but the result builds bit by bit. Key points include how NOT flips bits and how shifting moves bits left or right, changing the number's value. The quiz asks about specific bits and results to help understand these steps.

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