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

The Big Idea

Discover how a tiny bit can instantly tell you if a number is even or odd, making your code lightning fast!

The Scenario

Imagine you want to quickly find out if a number is even or odd by looking at it or doing simple math in your head.

For small numbers, you might try dividing by 2 and checking the remainder, but what if you have thousands of numbers to check fast?

The Problem

Using division or modulus operations to check even or odd numbers can be slow for computers when done many times.

It also uses more processing power and can slow down programs that need to make this check repeatedly.

The Solution

Using bits, specifically the last bit of a number, we can instantly tell if it is even or odd.

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

This method is very fast and uses very little computing power.

Before vs After

✗ Before

fn is_even(number: u32) -> bool {
    number % 2 == 0
}

✓ After

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

What It Enables

This lets programs check even or odd numbers instantly, making them faster and more efficient.

Real Life Example

In games or simulations, quickly deciding if a step or move is even or odd can affect animations or logic without slowing down the game.

Key Takeaways

Manual division or modulus is slower for checking even/odd.

Bitwise AND with 1 quickly reveals even or odd by checking the last bit.

This method improves speed and efficiency in programs.

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