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

↓

Apply AND (&)

→Result: bits set only if both bits are 1

↓

Apply OR (|)

→Result: bits set if either bit is 1

↓

Apply XOR (^)

→Result: bits set if bits differ

↓

Apply NOT (~)

→Result: bits flipped

↓

Apply Left Shift (<<)

→Result: bits shifted left, zeros fill right

↓

Apply Right Shift (>>)

→Result: bits shifted right, sign bit or zero fill

↓

End

Start with two numbers, then apply each bitwise operation step-by-step to see how bits change.

Execution Sample

DSA C

int a = 6;  // 00000110
int b = 11; // 00001011
int c;
c = a & b;
c = a | b;
c = a ^ b;
c = ~a;
c = a << 1;
c = b >> 2;

This code applies AND, OR, XOR, NOT, left shift, and right shift on two numbers and stores results.

Execution Table

Step	Operation	Input Values (a, b)	Result (decimal)	Result (binary)	Explanation
1	AND (&)	a=6 (00000110), b=11 (00001011)	2	00000010	Bits set only where both a and b have 1
2	OR (|)	a=6 (00000110), b=11 (00001011)	15	00001111	Bits set where either a or b has 1
3	XOR (^)	a=6 (00000110), b=11 (00001011)	13	00001101	Bits set where a and b bits differ
4	NOT (~)	a=6 (00000110)	-7	11111001 (2's complement)	Bits flipped; in 8-bit signed, ~6 = -7
5	Left Shift (<< 1)	a=6 (00000110)	12	00001100	Bits shifted left by 1, zero fills right
6	Right Shift (>> 2)	b=11 (00001011)	2	00000010	Bits shifted right by 2, zeros fill left
7	End	-	-	-	All operations completed

💡 All bitwise operations applied to inputs; execution ends.

Variable Tracker

Variable	Initial	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
a	6 (00000110)	6	6	6	6	6	6	6
b	11 (00001011)	11	11	11	11	11	11	11
c	undefined	2 (00000010)	15 (00001111)	13 (00001101)	-7 (11111001)	12 (00001100)	2 (00000010)	2

Key Moments - 3 Insights

Why does NOT (~) of 6 give -7 instead of a positive number?

Because NOT flips all bits including the sign bit in two's complement representation, resulting in a negative number as shown in step 4 of the execution_table.

Why does left shift (<<) multiply the number by 2?

Left shift moves bits to the left, adding a zero on the right, effectively doubling the number as seen in step 5 where 6 becomes 12.

What happens to bits shifted out in right shift (>>)?

Bits shifted out on the right are discarded, and zeros fill in from the left for unsigned or positive numbers, as shown in step 6 where 11 >> 2 becomes 2.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the binary result of a ^ b?

A 00001101

B 00001111

C 00000010

D 11111001

💡 Hint

Check the 'Result (binary)' column at step 3 in execution_table.

At which step does the variable c become negative?

A Step 5

B Step 2

C Step 4

D Step 6

💡 Hint

Look at the 'Result (decimal)' column for negative values in execution_table.

If we change a to 3 (00000011), what would be the result of a & b at step 1?

A 2

B 3

C 1

D 0

💡 Hint

AND sets bits only where both inputs have 1; compare bits of 3 and 11.

Concept Snapshot

Bit Manipulation Basics:
- AND (&): bits set if both bits 1
- OR (|): bits set if either bit 1
- XOR (^): bits set if bits differ
- NOT (~): bits flipped (two's complement)
- Left Shift (<<): bits shift left, zero fill right
- Right Shift (>>): bits shift right, zero or sign fill left

Full Transcript

This lesson shows how to use basic bit manipulation operators in C. We start with two numbers, 6 and 11, and apply AND, OR, XOR, NOT, left shift, and right shift. Each operation changes bits in a specific way. AND keeps bits set only if both inputs have 1. OR sets bits if either input has 1. XOR sets bits where inputs differ. NOT flips all bits, which can produce negative numbers in two's complement. Left shift moves bits left, doubling the number. Right shift moves bits right, dividing by powers of two. The execution table traces each step with decimal and binary results. Variable tracking shows how values change. Key moments clarify common confusions about negative results and bit shifts. Visual quizzes test understanding by referencing the execution steps and bit patterns.

Practice

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

easy

A. 0

B. 1

C. 6

D. 7

Solution

1. Step 1: Convert numbers to binary

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

2. Step 2: Perform bitwise AND operation

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

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
• Mixing bit positions during calculation

2. Which of the following is the correct syntax for left shifting the integer x by 2 bits 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

   The left shift operator is written as << and shifts bits to the left.

2. Step 2: Check syntax correctness

   x << 2; uses x << 2; which correctly shifts bits of x left by 2 positions.

3. Final Answer:

   x << 2; -> Option C

4. Quick Check:

   Left shift syntax = x << 2; [OK]

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

Common Mistakes:

• Using >>> which is invalid in C
• Confusing left shift with right shift
• Incorrect operator placement or syntax

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

int x = 6; // binary 0110
int y = x ^ 3; // 3 = 0011
printf("%d", y);

medium

A. 9

B. 7

C. 1

D. 5

Solution

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

   6 in binary is 0110, 3 is 0011. XOR operation: 0110 ^ 0011 = 0101.

2. Step 2: Calculate decimal value of XOR result

   0101 in binary equals 5 decimal.

3. Final Answer:

   5 -> Option D

4. Quick Check:

   6 ^ 3 = 5 [OK]

Hint: XOR flips bits where bits differ [OK]

Common Mistakes:

• Mixing XOR with OR or AND
• Incorrect binary conversion
• Misreading bit positions

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

int x = 8;
int y = ~x << 1;
printf("%d", y);

medium

A. Using ~ operator without parentheses causes wrong shift

B. Missing semicolon after declaration

C. Shift operator << cannot be used with ~ operator

D. No error, code runs correctly

Solution

1. Step 1: Understand operator precedence

   The bitwise NOT (~) has higher precedence than shift (<<), so ~x is evaluated first.

2. Step 2: Check if parentheses needed

   Without parentheses, ~x is computed, then shifted left. This is correct but may cause confusion if intended differently.

3. Step 3: Identify common mistake

   If intention was to shift x first then NOT, parentheses are needed. Otherwise, no syntax error but logic may be wrong.

4. Final Answer:

   Using ~ operator without parentheses causes wrong shift -> Option A

5. Quick Check:

   Operator precedence matters; use parentheses [OK]

Hint: Use parentheses to control bitwise operation order [OK]

Common Mistakes:

• Ignoring operator precedence
• Assuming shift applies before NOT
• Thinking code has syntax error when it doesn't

5. Given an integer n, which expression correctly checks if the 3rd bit (from right, zero-based) is set (1)?

hard

A. (n & (1 << 3)) != 0

B. (n | (1 << 3)) == 0

C. (n ^ (1 << 3)) == 0

D. (n >> 3) & 1 == 0

Solution

1. Step 1: Understand bit position and mask

   The 3rd bit (zero-based) means bit at position 3. Mask is 1 shifted left by 3: (1 << 3) = 8.

2. Step 2: Check if bit is set using AND

   Using (n & (1 << 3)) checks if that bit is 1. If result is not zero, bit is set.

3. Final Answer:

   (n & (1 << 3)) != 0 -> Option A

4. Quick Check:

   Bit check uses AND with mask [OK]

Hint: Use AND with (1 << bit_position) to check bit [OK]

Common Mistakes:

• Using OR or XOR instead of AND for checking
• Wrong bit position shift
• Comparing shifted bit to zero incorrectly