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

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

Start with two numbers

↓

Apply AND (&)

→Result: bits where both are 1

↓

Apply OR (|)

→Result: bits where at least one is 1

↓

Apply XOR (^)

→Result: bits where bits differ

↓

Apply NOT (~)

→Result: bits flipped

↓

Apply Left Shift (<<)

→Result: bits shifted left, zeros fill right

↓

Apply Right Shift (>>)

→Result: bits shifted right, zeros fill left

↓

End

Start with two numbers and apply bitwise AND, OR, XOR, NOT, left shift, and right shift operations step-by-step to see how bits change.

Execution Sample

DSA Rust

let a = 6;  // 0110 in binary
let b = 11; // 1011 in binary
let and = a & b;
let or = a | b;
let xor = a ^ b;
let not_a = !a;
let left_shift = a << 1;
let right_shift = b >> 2;

This code applies bitwise AND, OR, XOR, NOT, left shift, and right shift on two numbers a=6 and b=11.

Execution Table

Step	Operation	Operands	Bitwise Result (binary)	Decimal Result	Explanation
1	AND (&)	6 (0110) & 11 (1011)	0010	2	Bits where both operands have 1
2	OR (|)	6 (0110) | 11 (1011)	1111	15	Bits where at least one operand has 1
3	XOR (^)	6 (0110) ^ 11 (1011)	1101	13	Bits where operands differ
4	NOT (~)	~6 (0110)	1001 (4-bit view)	-7 (2's complement)	Bits flipped; in Rust, !6 equals -7 due to signed integers
5	Left Shift (<<)	6 (0110) << 1	1100	12	Bits shifted left by 1, zero fills right
6	Right Shift (>>)	11 (1011) >> 2	0010	2	Bits shifted right by 2, zeros fill left
7	End	-	-	-	All operations completed

💡 All bitwise operations on a=6 and b=11 completed

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 (0110)	6 (0110)	6 (0110)	6 (0110)	6 (0110)	6 (0110)	6 (0110)	6 (0110)
b	11 (1011)	11 (1011)	11 (1011)	11 (1011)	11 (1011)	11 (1011)	11 (1011)	11 (1011)
and	-	2 (0010)	2 (0010)	2 (0010)	2 (0010)	2 (0010)	2 (0010)	2 (0010)
or	-	-	15 (1111)	15 (1111)	15 (1111)	15 (1111)	15 (1111)	15 (1111)
xor	-	-	-	13 (1101)	13 (1101)	13 (1101)	13 (1101)	13 (1101)
not_a	-	-	-	-	-7 (1001 2's comp)	-7 (1001 2's comp)	-7 (1001 2's comp)	-7 (1001 2's comp)
left_shift	-	-	-	-	-	12 (1100)	12 (1100)	12 (1100)
right_shift	-	-	-	-	-	-	2 (0010)	2 (0010)

Key Moments - 3 Insights

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

In Rust, integers are signed and use two's complement. The NOT operation flips all bits, including the sign bit, resulting in -7. See step 4 in execution_table.

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

Left shifting bits by 1 moves all bits one place left, adding a zero on the right, effectively doubling the number. See step 5 in execution_table where 6 << 1 becomes 12.

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

Bits shifted out on the right are discarded, and zeros fill in from the left for unsigned or logical shifts. See step 6 where 11 >> 2 becomes 2.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the decimal result of XOR operation?

A 15

B 13

C 2

D 12

💡 Hint

Check the 'Decimal Result' column at step 3 in execution_table.

At which step does the variable 'left_shift' get its value updated?

A Step 5

B Step 4

C Step 6

D Step 3

💡 Hint

Look at variable_tracker row for 'left_shift' and see when it changes from '-' to a number.

If we change 'a' from 6 to 4 (0100), what would be the AND (&) result with b=11 at step 1?

A 4

B 2

C 0

D 6

💡 Hint

AND operation keeps bits set in both numbers; 4 (0100) & 11 (1011) = 0000 (0 decimal).

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 (signed in Rust)
- Left Shift (<<): bits move left, zero fills right
- Right Shift (>>): bits move right, zero fills left

Full Transcript

This lesson shows how to use basic bit manipulation operators in Rust. Starting with two numbers, 6 and 11, we apply AND, OR, XOR, NOT, left shift, and right shift. Each operation changes bits in a specific way. AND keeps bits set in both numbers. OR sets bits if either number has it. XOR sets bits where numbers differ. NOT flips all bits, resulting in negative numbers due to Rust's signed integers. Left shift moves bits left, doubling the number. Right shift moves bits right, dividing the number. The execution table tracks each step's binary and decimal results. Variable tracker shows how variables update after each operation. Key moments clarify common confusions about NOT and shifts. Visual quiz tests understanding by referencing these steps. This helps beginners see exactly how bits change with each operation.

Practice

1. What is the result of the bitwise AND operation between 0b1101 and 0b1011?

easy

A. 0b1001

B. 0b1111

C. 0b0101

D. 0b0011

Solution

1. Step 1: Understand bitwise AND operation

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

2. Step 2: Apply AND to each bit of 0b1101 and 0b1011

   Bits: 1&1=1, 1&0=0, 0&1=0, 1&1=1, so result is 0b1001.

3. Final Answer:

   0b1001 -> Option A

4. Quick Check:

   1101 & 1011 = 1001 [OK]

Hint: AND keeps bits set only if both are 1 [OK]

Common Mistakes:

• Confusing AND with OR operation
• Mixing bit positions when calculating
• Forgetting binary format in answer

2. Which of the following is the correct Rust syntax to perform a bitwise XOR between variables a and b?

easy

A. let c = a & b;

B. let c = a && b;

C. let c = a ^ b;

D. let c = a | b;

Solution

1. Step 1: Recall Rust bitwise XOR operator

   In Rust, the caret symbol (^) is used for bitwise XOR.

2. Step 2: Check each option's operator

   The options use: & (bitwise AND), && (logical AND), | (bitwise OR), ^ (bitwise XOR). Only ^ is correct.

3. Final Answer:

   let c = a ^ b; -> Option C

4. Quick Check:

   Bitwise XOR in Rust uses ^ [OK]

Hint: XOR uses ^ symbol in Rust [OK]

Common Mistakes:

• Using && instead of ^ for XOR
• Confusing bitwise OR (|) with XOR
• Using logical operators instead of bitwise

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

let x: u8 = 0b0011_1100;
let y: u8 = 0b0000_1101;
let z = x | y;
println!("{:08b}", z);

medium

A. 00111101

B. 00110001

C. 00001101

D. 00111100

Solution

1. Step 1: Understand bitwise OR operation

   Bitwise OR returns 1 if at least one bit is 1 in either number.

2. Step 2: Apply OR to each bit of x and y

   x = 00111100, y = 00001101; OR bits: 0|0=0,0|0=0,1|0=1,1|0=1,1|1=1,1|1=1,0|0=0,0|1=1; result = 00111101.

3. Final Answer:

   00111101 -> Option A

4. Quick Check:

   00111100 | 00001101 = 00111101 [OK]

Hint: OR sets bit if either bit is 1 [OK]

Common Mistakes:

• Mixing OR with AND operation
• Misreading binary digits
• Ignoring leading zeros in output

4. Identify the error in this Rust code snippet that attempts to left shift a variable:

let a: u8 = 0b0001_0001;
let b = a << 8
println!("{:08b}", b);

medium

A. Incorrect use of << operator, should be >>

B. Shift amount exceeds variable bit size causing overflow

C. Cannot print binary format with {:08b}

D. Missing semicolon after variable declaration

Solution

1. Step 1: Check for syntax errors

   The declaration 'let b = a << 8' is missing a semicolon (;).

2. Step 2: Verify other parts

   << is correct for left shift; Rust masks large shift amounts without panic/overflow error; {:08b} works for binary output.

3. Final Answer:

   Missing semicolon after variable declaration -> Option D

4. Quick Check:

   Missing ; after let causes compile error [OK]

Hint: Rust statements must end with semicolon [OK]

Common Mistakes:

• Omitting semicolons after let statements
• Confusing left shift with right shift
• Assuming shifts panic on large amounts

5. Given a 16-bit unsigned integer num, which Rust expression correctly clears (sets to 0) the 5th bit (counting from 0 at the right) without affecting other bits?

hard

A. num | (1 << 5)

B. num & !(1 << 5)

C. num ^ (1 << 5)

D. num << 5

Solution

1. Step 1: Understand clearing a bit

   To clear a bit, use AND with a mask that has 0 at target bit and 1 elsewhere.

2. Step 2: Create mask for 5th bit

   1 << 5 creates a mask with 1 at 5th bit; negating it with ! flips bits, making 0 at 5th bit.

3. Step 3: Apply mask with AND

   num & !(1 << 5) clears 5th bit, keeps others unchanged.

4. Final Answer:

   num & !(1 << 5) -> Option B

5. Quick Check:

   Clear bit 5 using AND with inverted mask [OK]

Hint: Clear bit with AND and inverted mask [OK]

Common Mistakes:

• Using OR instead of AND to clear bits
• Using XOR which toggles bits
• Shifting num instead of mask