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

The Big Idea

Discover how a tiny bit can save you tons of time when checking numbers!

The Scenario

Imagine you have a long list of numbers and you want to quickly find out which ones are even and which are odd. Doing this by dividing each number by 2 and checking the remainder can be slow if the list is very large.

The Problem

Using division and modulus operations repeatedly takes more time and uses more computing power. It can slow down programs, especially when working with millions of numbers or in devices with limited resources.

The Solution

Using bits to check if a number is even or odd is much faster. The last bit of a number in binary tells us if it is even (0) or odd (1). This method uses a simple AND operation with 1, which is very quick and efficient.

Before vs After

✗ Before

if (number % 2 == 0) {
    Console.WriteLine("Even");
} else {
    Console.WriteLine("Odd");
}

✓ After

if ((number & 1) == 0) {
    Console.WriteLine("Even");
} else {
    Console.WriteLine("Odd");
}

What It Enables

This technique enables lightning-fast checks for even or odd numbers, making programs more efficient and responsive.

Real Life Example

In video games, checking if a character's step count is even or odd can trigger different animations instantly without slowing down the game.

Key Takeaways

Manual division for even/odd checks is slower and costly.

Bitwise AND with 1 quickly reveals even or odd status.

This method improves performance in large-scale or resource-limited tasks.

Practice

1. Which bit operation can be used to check if a number is even or odd in C#?

easy

A. Using bitwise OR with 1 (number | 1)

B. Using bitwise XOR with 1 (number ^ 1)

C. Using bitwise AND with 1 (number & 1)

D. Using bitwise NOT (~number)

Solution

1. Step 1: Understand bitwise AND with 1

   Bitwise AND with 1 checks the least significant bit of the number.

2. Step 2: Check least significant bit for even or odd

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

3. Final Answer:

   Using bitwise AND with 1 (number & 1) -> Option C

4. Quick Check:

   Least significant bit check = number & 1 [OK]

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

Common Mistakes:

• Using bitwise OR instead of AND
• Using XOR which toggles bits
• Using NOT which flips all bits

2. Which of the following C# code snippets correctly checks if num is odd using bits?

easy

A. if ((num & 1) == 0) { Console.WriteLine("Odd"); }

B. if ((num ^ 1) == 1) { Console.WriteLine("Odd"); }

C. if ((num | 1) == 1) { Console.WriteLine("Odd"); }

D. if ((num & 1) == 1) { Console.WriteLine("Odd"); }

Solution

1. Step 1: Understand bitwise AND check for odd

   Odd numbers have least significant bit 1, so (num & 1) == 1 means odd.

2. Step 2: Verify code logic

   if ((num & 1) == 1) { Console.WriteLine("Odd"); } prints "Odd" when (num & 1) equals 1, correctly identifying odd numbers.

3. Final Answer:

   if ((num & 1) == 1) { Console.WriteLine("Odd"); } -> Option D

4. Quick Check:

   Odd check = (num & 1) == 1 [OK]

Hint: Use (num & 1) == 1 to check odd numbers [OK]

Common Mistakes:

• Checking (num & 1) == 0 for odd (actually even)
• Using OR or XOR instead of AND
• Confusing equality check with assignment

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

int num = 14;
if ((num & 1) == 0)
    Console.WriteLine("Even");
else
    Console.WriteLine("Odd");

medium

A. Odd

B. Even

C. 14

D. Error

Solution

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

   14 in binary is 1110; 1110 & 0001 = 0, so (num & 1) == 0 is true.

2. Step 2: Determine output based on condition

   Since condition is true, it prints "Even".

3. Final Answer:

   Even -> Option B

4. Quick Check:

   14 & 1 = 0 means Even [OK]

Hint: Even numbers have last bit 0, so (num & 1) == 0 [OK]

Common Mistakes:

• Assuming 14 is odd
• Confusing bitwise AND with OR
• Expecting numeric output instead of string

4. Find the error in this C# code that checks if a number is odd:

int num = 7;
if (num & 1 == 1)
    Console.WriteLine("Odd");
else
    Console.WriteLine("Even");

medium

A. Missing parentheses around (num & 1)

B. Using bitwise OR instead of AND

C. Incorrect variable type for num

D. No error, code is correct

Solution

1. Step 1: Analyze operator precedence

   In C#, equality (==) has higher precedence than bitwise AND (&), so 'num & 1 == 1' parses as 'num & (1 == 1)', which is 'num & 1'. This does not compare (num & 1) to 1 as intended.

2. Step 2: Identify the error

   Missing parentheses around (num & 1) causes incorrect evaluation. Correct code should be 'if ((num & 1) == 1)'.

3. Final Answer:

   Missing parentheses around (num & 1) -> Option A

4. Quick Check:

   Use parentheses to ensure correct precedence [OK]

Hint: C# precedence: == > & , so use parentheses to ensure correct evaluation [OK]

Common Mistakes:

• Misjudging precedence (thinking & > ==)
• Using bitwise OR instead of AND
• Assuming parentheses are not required

5. You want to write a C# method that returns "Even" or "Odd" for any integer using bitwise operations. Which of these implementations is correct and efficient?

public string CheckEvenOdd(int num) {
    // Options:
    // A) return (num & 1) == 0 ? "Even" : "Odd";
    // B) return (num | 1) == 0 ? "Even" : "Odd";
    // C) return (num ^ 1) == 0 ? "Even" : "Odd";
    // D) return (~num & 1) == 0 ? "Even" : "Odd";
}

hard

A. Option A

B. Option B

C. Option C

D. Option D

Solution

1. Step 1: Evaluate each option's logic

   Option A correctly checks if least significant bit is 0 for even; others use incorrect bitwise logic.

2. Step 2: Confirm correctness and efficiency

   Option A uses simple bitwise AND and ternary operator, efficient and clear.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Use (num & 1) == 0 for even check [OK]

Hint: Use (num & 1) == 0 ? "Even" : "Odd" for quick check [OK]

Common Mistakes:

• Using OR or XOR which give wrong results
• Using NOT which flips bits incorrectly
• Ignoring ternary operator for return