Check if Number is Even or Odd Using Bits in DSA Rust - Execution Trace

Concept Flow - Check if Number is Even or Odd Using Bits

Start with number n

↓

Perform bitwise AND: n & 1

↓

Is result 0?

Yes→Number is Even

No↓

Number is Odd

We check the last bit of the number using bitwise AND with 1. If it is 0, the number is even; if 1, it is odd.

Execution Sample

DSA Rust

fn is_even(n: u32) -> bool {
    (n & 1) == 0
}

fn main() {
    let num = 5;
    println!("{} is even? {}", num, is_even(num));
}

This code checks if a number is even by testing its last bit using bitwise AND.

Execution Table

Step	Operation	Number (n)	Bitwise AND (n & 1)	Result	Conclusion
1	Input number	5 (binary 0101)	-	-	-
2	Calculate n & 1	5 (0101)	1 (0001)	1	Odd (since result != 0)
3	Output	5	-	-	5 is Odd

💡 Bitwise AND result is 1, so number is odd and execution ends.

Variable Tracker

Variable	Start	After Step 2	Final
n	5	5	5
n & 1	-	1	1
is_even	-	false	false

Key Moments - 3 Insights

Why do we use 'n & 1' to check even or odd?

Because the last bit of a binary number tells if it's even (0) or odd (1). See execution_table step 2 where n & 1 extracts this bit.

What if the number is 0? Is it even or odd?

0 & 1 equals 0, so 0 is even. This matches the logic in execution_table step 2 for any number.

Why not use modulo (%) operator instead?

Bitwise AND is faster and directly checks the last bit without division. This is efficient for low-level checks.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'n & 1' at step 2 for number 5?

A 1

B 5

C 0

D Undefined

💡 Hint

Check the 'Bitwise AND (n & 1)' column at step 2 in execution_table.

At which step does the program conclude the number is odd?

A Step 1

B Step 3

C Step 2

D No conclusion

💡 Hint

Look at the 'Conclusion' column in execution_table for the final output.

If the input number was 4, what would 'n & 1' be at step 2?

A 4

B 1

C 0

D Undefined

💡 Hint

Recall that even numbers have last bit 0, so n & 1 should be 0.

Concept Snapshot

Check even/odd by testing last bit:
Use (n & 1) == 0 for even
If result is 1, number is odd
Bitwise AND is fast and simple
No division needed

Full Transcript

To check if a number is even or odd using bits, we look at its last binary bit. We do this by performing a bitwise AND between the number and 1. If the result is 0, the number is even; if 1, it is odd. For example, number 5 in binary is 0101. 5 & 1 equals 1, so 5 is odd. This method is efficient because it avoids division and directly inspects the binary representation.

Practice

1. What does the expression num & 1 check when determining if a number is even or odd?

easy

A. It checks the least significant bit of the number

B. It checks if the number is greater than 1

C. It divides the number by 2

D. It adds 1 to the number

Solution

1. Step 1: Understand bitwise AND operation

   The expression num & 1 performs a bitwise AND between the number and 1, which isolates the least significant bit (rightmost bit).

2. Step 2: Interpret the least significant bit

   If the least significant bit is 1, the number is odd; if it is 0, the number is even.

3. Final Answer:

   It checks the least significant bit of the number -> Option A

4. Quick Check:

   Least significant bit = odd/even check [OK]

Hint: Check last bit with & 1 to find odd or even fast [OK]

Common Mistakes:

• Thinking & 1 divides the number
• Confusing bitwise AND with addition
• Assuming it checks if number > 1

2. Which Rust code snippet correctly checks if a number n is odd using bitwise operations?

easy

A. if n ^ 1 == 1 { println!("Odd"); }

B. if n | 1 == 1 { println!("Odd"); }

C. if n & 0 == 1 { println!("Odd"); }

D. if n & 1 == 1 { println!("Odd"); }

Solution

1. Step 1: Identify correct bitwise operator for odd check

   The bitwise AND operator & with 1 isolates the least significant bit, which indicates oddness.

2. Step 2: Verify condition correctness

   Checking if n & 1 == 1 means the number is odd. Other operators like OR | or XOR ^ do not correctly check oddness.

3. Final Answer:

   if n & 1 == 1 { println!("Odd"); } -> Option D

4. Quick Check:

   Use & 1 == 1 to check odd [OK]

Hint: Use & 1 == 1 to check odd numbers in Rust [OK]

Common Mistakes:

• Using OR or XOR instead of AND
• Comparing with 0 instead of 1
• Using bitwise operators incorrectly

3. What will be the output of this Rust code?

let num = 14;
if num & 1 == 0 {
    println!("Even");
} else {
    println!("Odd");
}

medium

A. Even

B. Odd

C. 14

D. Compilation error

Solution

1. Step 1: Evaluate bitwise AND of 14 and 1

   Binary of 14 is 1110, and 1 is 0001. 1110 & 0001 = 0.

2. Step 2: Check condition and print output

   Since num & 1 == 0 is true, the code prints "Even".

3. Final Answer:

   Even -> Option A

4. Quick Check:

   14 & 1 = 0 means Even [OK]

Hint: If num & 1 equals 0, number is even [OK]

Common Mistakes:

• Assuming 14 is odd
• Confusing bitwise AND with arithmetic AND
• Expecting output to be the number itself

4. Identify the error in this Rust code snippet that checks if a number is odd:

let n = 7;
if n & 1 = 1 {
    println!("Odd");
} else {
    println!("Even");
}

medium

A. Using & instead of && in if condition

B. Missing semicolon after println!

C. Using single = instead of == in if condition

D. Variable n is not declared

Solution

1. Step 1: Check the if condition syntax

   The condition uses single equals = which is assignment, not comparison.

2. Step 2: Correct the comparison operator

   It should use double equals == to compare n & 1 with 1.

3. Final Answer:

   Using single = instead of == in if condition -> Option C

4. Quick Check:

   Use == for comparison, not = [OK]

Hint: Use == for comparison, not = assignment [OK]

Common Mistakes:

• Confusing assignment (=) with equality (==)
• Thinking & is logical AND instead of bitwise
• Ignoring compiler error messages

5. Given a list of integers nums = [2, 3, 4, 5, 6], which Rust code correctly uses bitwise operations to filter only odd numbers and print them?

hard

A. for num in nums.iter() {
if num & 0 == 1 {
println!("{}", num);
}
}

B. for &num in &nums {
if num & 1 == 1 {
println!("{}", num);
}
}

C. for num in nums {
if num | 1 == 1 {
println!("{}", num);
}
}

D. for num in nums {
if num ^ 1 == 1 {
println!("{}", num);
}
}

Solution

1. Step 1: Understand iteration and bitwise odd check

   Iterate over references to numbers and use num & 1 == 1 to check odd numbers.

2. Step 2: Verify correct syntax and logic

   for &num in &nums { if num & 1 == 1 { println!("{}", num); } } correctly iterates with for &num in &nums and checks oddness with bitwise AND. Other options misuse operators or iteration.

3. Final Answer:

   for &num in &nums { if num & 1 == 1 { println!("{}", num); } } -> Option B

4. Quick Check:

   Use & 1 == 1 inside loop over &nums [OK]

Hint: Iterate references and use & 1 == 1 to print odd numbers [OK]

Common Mistakes:

• Using wrong bitwise operators like | or ^
• Iterating without references causing ownership errors
• Checking with & 0 instead of & 1