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

Mental Model

The last bit of a number in binary tells if it is even or odd. If the last bit is 0, the number is even; if 1, it is odd.

Analogy: Think of a light switch that can be either off (0) or on (1). The last bit is like that switch showing if the number is even (off) or odd (on).

Number in binary:  ... b3 b2 b1 b0
                      ↑
                   last bit

Dry Run Walkthrough

Input: number = 5

Goal: Determine if 5 is even or odd using bit operations

Step 1: Check the last bit of 5 using bitwise AND with 1

5 in binary: 0101
1 in binary:  0001
AND result:   0001 (which is 1)

Why: The last bit is 1, so the number is odd

Result:

5 is odd

Annotated Code

DSA Rust

fn is_even(num: i32) -> bool {
    // Check last bit: 0 means even, 1 means odd
    (num & 1) == 0
}

fn main() {
    let numbers = [4, 5, 10, 11];
    for &num in &numbers {
        if is_even(num) {
            println!("{} is even", num);
        } else {
            println!("{} is odd", num);
        }
    }
}

(num & 1) == 0

Check last bit to decide even or odd

if is_even(num) {

Use bit check result to print even or odd

Output

4 is even

5 is odd

10 is even

11 is odd

Complexity Analysis

Time: O(1) because bitwise AND is a single operation

Space: O(1) because no extra memory is used

vs Alternative: Faster than using modulo (%) which can be slower on some systems

Edge Cases

number = 0

0 is even because last bit is 0

DSA Rust

(num & 1) == 0

negative numbers like -3

Works correctly because bitwise AND checks last bit regardless of sign

DSA Rust

(num & 1) == 0

When to Use This Pattern

When you need a fast way to check even or odd without division, use bitwise AND with 1 to check the last bit.

Common Mistakes

Mistake: Using modulo operator (%) instead of bitwise AND for checking even/odd
Fix: Use (num & 1) == 0 for faster and simpler check

Mistake: Checking if (num & 1) == 1 and returning true for even
Fix: Remember last bit 1 means odd, so (num & 1) == 0 means even

Summary

It checks if a number is even or odd by looking at its last binary bit.

Use it when you want a quick and efficient way to find even or odd numbers.

The last bit of a number tells you if it is even (0) or odd (1).

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