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

↓

NOT (~) flips bits of one number

↓

Left Shift (<<) moves bits left

↓

Right Shift (>>) moves bits right

↓

Result is new number after operation

↓

End

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

Execution Sample

DSA C#

int a = 5;  // 0101 in binary
int b = 3;  // 0011 in binary
int c = a & b; // AND operation
Console.WriteLine(c);

This code does bitwise AND on 5 and 3, then prints the result.

Execution Table

Step	Operation	Bit Position	Bit of a	Bit of b	Result Bit	Result Binary	Result Decimal
1	AND	3 (8's place)	0	0	0	0000	0
2	AND	2 (4's place)	1	0	0	0000	0
3	AND	1 (2's place)	0	1	0	0000	0
4	AND	0 (1's place)	1	1	1	0001	1
5	Final Result	-	-	-	-	0001	1

💡 All bits processed for AND operation, final result is 1.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
a (decimal)	5	5	5	5	5	5
a (binary)	0101	0101	0101	0101	0101	0101
b (decimal)	3	3	3	3	3	3
b (binary)	0011	0011	0011	0011	0011	0011
Result (binary)	----	0000	0000	0000	0001	0001
Result (decimal)	----	0	0	0	1	1

Key Moments - 3 Insights

Why does the AND operation result in 1 when only the last bit is 1 in both numbers?

Because AND only sets a bit to 1 if both bits at that position are 1. In the execution_table rows 1-4, only at bit 0 both bits are 1, so result bit is 1 there.

What happens if we apply NOT (~) to a number like 5?

NOT flips every bit. For 5 (0101), NOT flips to 1010 in 4 bits, which is -6 in signed 32-bit integers. This is why NOT results can look negative due to two's complement.

How does left shift (<<) affect the binary number?

Left shift moves all bits to the left by the shift amount, adding zeros on the right. For example, 5 (0101) << 1 becomes 1010 (10 decimal). This doubles the number.

Visual Quiz - 3 Questions

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

A 1

B 0

C Depends on a only

D Depends on b only

💡 Hint

Check row 2 in execution_table under 'Result Bit' column.

At which step does the final decimal result become 1 in the AND operation?

A Step 2

B Step 4

C Step 5

D Step 1

💡 Hint

Look at the 'Result Decimal' column and find when it shows 1.

If we change b to 7 (0111), how would the result decimal change after AND with a=5?

A Result becomes 5

B Result becomes 7

C Result becomes 1

D Result becomes 3

💡 Hint

AND operation keeps bits set in both numbers; check bits of 5 (0101) and 7 (0111).

Concept Snapshot

Bit Manipulation Basics:
- AND (&): 1 if both bits 1
- OR (|): 1 if any bit 1
- XOR (^): 1 if bits differ
- NOT (~): flips bits
- Left Shift (<<): moves bits left, adds 0s
- Right Shift (>>): moves bits right, drops bits
Use to manipulate numbers at bit level efficiently.

Full Transcript

This lesson shows how bitwise operations work on two numbers. We start with numbers 5 and 3, represented in binary as 0101 and 0011. We apply the AND operation bit by bit, comparing each bit position. Only where both bits are 1 does the result bit become 1. The final result is 1 (0001 in binary). We track each bit's comparison and the result bit in the execution table. We also discuss how NOT flips bits, and how left and right shifts move bits to multiply or divide numbers by powers of two. This helps understand how computers manipulate data efficiently at the bit level.

Practice

1. What does the bitwise AND operator (&) do when applied to two bits?

easy

A. Returns 0 only if both bits are 0

B. Returns 1 if either bit is 1

C. Flips the bits from 0 to 1 and 1 to 0

D. Returns 1 only if both bits are 1

Solution

1. Step 1: Understand bitwise AND operation

   The AND operator compares each bit of two numbers and returns 1 only if both bits are 1.

2. Step 2: Apply to example bits

   For bits 1 & 1, result is 1; for 1 & 0 or 0 & 1 or 0 & 0, result is 0.

3. Final Answer:

   Returns 1 only if both bits are 1 -> Option D

4. Quick Check:

   AND = 1 only if both bits 1 [OK]

Hint: AND returns 1 only when both bits are 1 [OK]

Common Mistakes:

• Confusing AND with OR operator
• Thinking AND flips bits
• Assuming AND returns 1 if either bit is 1

2. Which of the following is the correct syntax to perform a left shift by 2 on an integer variable x in C#?

easy

A. x >> 2;

B. x << 2;

C. x <<< 2;

D. x >> 2 <<;

Solution

1. Step 1: Recall left shift operator syntax in C#

   The left shift operator is << and used as x << n to shift bits left by n places.

2. Step 2: Identify correct syntax among options

   x << 2; uses x << 2; which is correct. x >> 2; is right shift, C uses invalid operator, D is invalid syntax.

3. Final Answer:

   x << 2; -> Option B

4. Quick Check:

   Left shift syntax is x << n [OK]

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

Common Mistakes:

• Using >>> which is invalid in C#
• Confusing left shift with right shift
• Adding extra symbols after shift operator

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

int a = 5; // binary 0101
int b = 3; // binary 0011
int c = a ^ b;
Console.WriteLine(c);

medium

A. 2

B. 7

C. 6

D. 8

Solution

1. Step 1: Convert numbers to binary and apply XOR

   5 in binary is 0101, 3 is 0011. XOR (^) returns 1 if bits differ, else 0.

2. Step 2: Calculate XOR bit by bit

   0101 ^ 0011 = 0110 (binary), which is 6 in decimal.

3. Final Answer:

   6 -> Option C

4. Quick Check:

   5 ^ 3 = 6 [OK]

Hint: XOR sets bits where inputs differ [OK]

Common Mistakes:

• Confusing XOR with OR or AND
• Calculating decimal sum instead of XOR
• Misreading binary values

4. Identify the error in the following C# code snippet that attempts to invert bits of an integer num:

int num = 12;
int inverted = ~num();
Console.WriteLine(inverted);

medium

A. Using parentheses after variable name num()

B. Using bitwise NOT operator incorrectly

C. Missing semicolon after int num = 12

D. Console.WriteLine cannot print integers

Solution

1. Step 1: Check usage of variable num

   The code uses num() which looks like a function call but num is an integer variable, so parentheses are invalid.

2. Step 2: Confirm bitwise NOT operator usage

   The bitwise NOT operator ~ is correctly used before the variable, so no error there.

3. Final Answer:

   Using parentheses after variable name num() -> Option A

4. Quick Check:

   Variables don't use () [OK]

Hint: Variables are not functions; no () after variable names [OK]

Common Mistakes:

• Thinking ~num() is valid syntax
• Assuming missing semicolon error
• Believing Console.WriteLine can't print integers

5. Given an integer n = 8, which expression correctly checks if n is a power of two using bit manipulation in C#?

hard

A. (n & (n - 1)) == 0

B. (n | (n - 1)) == 0

C. (n ^ (n - 1)) == 0

D. (~n & (n - 1)) == 0

Solution

1. Step 1: Understand the power of two property

   A number is a power of two if it has exactly one bit set to 1 in binary.

2. Step 2: Apply bitwise trick

   For such numbers, n & (n - 1) clears the lowest set bit. If result is 0, n was a power of two.

3. Final Answer:

   (n & (n - 1)) == 0 -> Option A

4. Quick Check:

   Power of two check uses n & (n-1) == 0 [OK]

Hint: Power of two if n & (n-1) equals zero [OK]

Common Mistakes:

• Using OR or XOR instead of AND
• Forgetting to compare result to zero
• Misunderstanding bitwise NOT usage