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

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 parking lot where cars park in pairs. If there is a leftover single car without a pair, it means the total number is odd. The last bit is like checking if there is a leftover car.

Number in binary:  ... b3 b2 b1 b0
Check last bit b0 -> 0 means even, 1 means odd

Dry Run Walkthrough

Input: number = 5 (binary 0101)

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

Step 1: Perform bitwise AND between number and 1 (5 & 1)

0101 & 0001 = 0001

Why: AND with 1 isolates the last bit to check if it is 0 or 1

Step 2: Check result of AND operation

Result is 1

Why: If result is 1, number is odd

Result:

Number 5 is odd because last bit is 1

Annotated Code

DSA C++

#include <iostream>
#include <string>
using namespace std;

// Function to check even or odd using bits
string checkEvenOdd(int num) {
    // AND with 1 isolates last bit
    if ((num & 1) == 0) {
        return "Even";
    } else {
        return "Odd";
    }
}

int main() {
    int number = 5; // input from dry run
    cout << number << " is " << checkEvenOdd(number) << "\n";
    return 0;
}

if ((num & 1) == 0) {

Check last bit by ANDing with 1 to determine even or odd

return "Even";

Return Even if last bit is 0

return "Odd";

Return Odd if last bit is 1

Output

5 is Odd

Complexity Analysis

Time: O(1) because bitwise AND operation takes constant time

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

vs Alternative: Using modulo (%) operator also takes O(1) time but bitwise AND is faster and uses less CPU cycles

Edge Cases

number = 0

Returns Even because 0 is even and last bit is 0

DSA C++

if ((num & 1) == 0) {

number = 1

Returns Odd because last bit is 1

DSA C++

if ((num & 1) == 0) {

negative numbers like -3

Returns Odd because bitwise AND checks last bit regardless of sign

DSA C++

if ((num & 1) == 0) {

When to Use This Pattern

When you need to quickly check if a number is even or odd without division or modulo, use bitwise AND with 1 for a fast and simple solution.

Common Mistakes

Mistake: Using modulo operator (%) instead of bitwise AND when the problem specifically asks for bit manipulation
Fix: Use (num & 1) to check last bit instead of num % 2

Mistake: Checking if (num & 1) == 1 to return even instead of odd
Fix: Remember (num & 1) == 0 means even, (num & 1) == 1 means odd

Summary

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

Use when you want a fast, low-level way to determine parity without division.

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

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