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

The Big Idea

Discover how a tiny bit can save you from slow math and speed up your programs!

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 (%) to check even or odd can be slow for many numbers because division is a heavier operation for computers.

Also, if you do it manually for many numbers, it takes time and can cause mistakes.

The Solution

Using bits, you can check if a number is even or odd by looking at just one bit -- the last bit.

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

This is very fast and simple for computers to do.

Before vs After

✗ Before

if (number % 2 == 0) {
    // even
} else {
    // odd
}

✓ After

if ((number & 1) == 0) {
    // even
} else {
    // odd
}

What It Enables

This lets you quickly and efficiently check even or odd status for huge lists of numbers or in performance-critical code.

Real Life Example

In games or graphics, you might need to quickly decide if a pixel or frame number is even or odd to apply different effects without slowing down the program.

Key Takeaways

Manual division for even/odd is slow for many numbers.

Bitwise AND with 1 checks the last bit to find even/odd instantly.

This method is faster and less error-prone for computers.

Practice

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

easy

A. Check the least significant bit using AND with 1

B. Shift the number right by 1

C. XOR the number with 1

D. Invert all bits of the number

Solution

1. Step 1: Understand the least significant bit (LSB)

   The LSB of a binary number determines if it is even or odd. If LSB is 0, number is even; if 1, number is odd.

2. Step 2: Use AND operation with 1 to check LSB

   Performing bitwise AND with 1 isolates the LSB. Result 0 means even, 1 means odd.

3. Final Answer:

   Check the least significant bit using AND with 1 -> Option A

4. Quick Check:

   LSB & 1 = 0 (even) or 1 (odd) [OK]

Hint: Use n & 1 to check even or odd quickly [OK]

Common Mistakes:

• Using XOR instead of AND to check LSB
• Checking the most significant bit instead
• Using bit shift without checking bits

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

easy

A. if ((num & 1) == 0) { /* odd */ }

B. if ((num >> 1) == 1) { /* odd */ }

C. if ((num ^ 1) == 1) { /* odd */ }

D. if ((num & 1) == 1) { /* odd */ }

Solution

1. Step 1: Understand bitwise AND with 1

   Using (num & 1) extracts the least significant bit. If it equals 1, number is odd.

2. Step 2: Check condition for odd number

   The condition (num & 1) == 1 correctly identifies odd numbers.

3. Final Answer:

   if ((num & 1) == 1) { /* odd */ } -> Option D

4. Quick Check:

   (num & 1) == 1 means odd [OK]

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

Common Mistakes:

• Using == 0 to check odd (actually checks even)
• Using bit shift without comparison
• Using XOR incorrectly for odd check

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

int num = 14;
if (num & 1) {
    std::cout << "Odd";
} else {
    std::cout << "Even";
}

medium

A. Odd

B. Even

C. 14

D. Error

Solution

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

   14 in binary is 1110. The least significant bit is 0. So, 14 & 1 = 0.

2. Step 2: Check the if condition

   Since (num & 1) is 0, the else block executes, printing "Even".

3. Final Answer:

   Even -> Option B

4. Quick Check:

   14 & 1 = 0 means Even [OK]

Hint: Check LSB: 0 means even, 1 means odd [OK]

Common Mistakes:

• Assuming 14 is odd because it ends with 4
• Confusing bitwise AND with arithmetic AND
• Printing num instead of "Even" or "Odd"

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

int num = 7;
if (num & 1 == 1) {
    std::cout << "Odd";
} else {
    std::cout << "Even";
}

medium

A. Incorrect variable type for num

B. Using == instead of =

C. Missing parentheses around (num & 1)

D. No error, code is correct

Solution

1. Step 1: Analyze operator precedence in condition

   In C++, == has higher precedence than &. So, num & 1 == 1 is parsed as num & (1 == 1), which is num & 1. This is not the intended comparison.

2. Step 2: Identify the error

   Without parentheses, the expression does not explicitly compare (num & 1) to 1, which can cause confusion or unintended behavior. Parentheses are needed: (num & 1) == 1.

3. Final Answer:

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

4. Quick Check:

   Operator precedence requires parentheses for clarity [OK]

Hint: Use parentheses: (num & 1) == 1 to avoid precedence issues [OK]

Common Mistakes:

• Misinterpreting operator precedence (== > &)
• Thinking parentheses are not needed
• Believing the code works correctly without parentheses

5. You want to write a function in C++ that returns true if a number is even and false if odd, using bitwise operations. Which of the following implementations is correct?

hard

A. bool isEven(int n) { return (n & 1) == 0; }

B. bool isEven(int n) { return (n & 1) == 1; }

C. bool isEven(int n) { return (n >> 1) == 0; }

D. bool isEven(int n) { return !(n ^ 1); }

Solution

1. Step 1: Understand even number bit pattern

   Even numbers have least significant bit 0. So (n & 1) == 0 means even.

2. Step 2: Check each function implementation

   bool isEven(int n) { return (n & 1) == 1; } returns true for odd numbers, so incorrect. bool isEven(int n) { return (n & 1) == 0; } correctly returns true for even numbers. Options C and D do not correctly check evenness.

3. Final Answer:

   bool isEven(int n) { return (n & 1) == 0; } -> Option A

4. Quick Check:

   Even if LSB is 0 [OK]

Hint: Return (n & 1) == 0 for even check [OK]

Common Mistakes:

• Returning true for odd numbers by mistake
• Using bit shift incorrectly for even check
• Using XOR without understanding its effect