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

Concept Flow - Check if Number is Even or Odd Using Bits

Start with number n

↓

Perform bitwise AND: n & 1

↓

Is result 0?

Yes→Number is Even

No↓

Number is Odd

The flow checks the last bit of the number using bitwise AND with 1. If the last bit is 0, the number is even; otherwise, it is odd.

Execution Sample

DSA C++

int n = 5;
if ((n & 1) == 0) {
  // even
} else {
  // odd
}

This code checks if the number 5 is even or odd by looking at its last bit.

Execution Table

Step	Operation	Number (n)	Bitwise AND (n & 1)	Result	Conclusion
1	Start with number	5
2	Calculate n & 1	5	1
3	Check if (n & 1) == 0	5	1	False	Number is Odd
4	End	5	1	False	Number is Odd

💡 Bitwise AND result is 1, so number 5 is odd.

Variable Tracker

Variable	Start	After Step 2	After Step 3	Final
n	5	5	5	5
n & 1		1	1	1
Result (is even?)			False	False

Key Moments - 3 Insights

Why do we use 'n & 1' to check even or odd?

Because the last bit of a binary number tells if it is even (0) or odd (1). The execution_table step 2 shows the bitwise AND extracting this last bit.

What does it mean if 'n & 1' equals 0?

It means the last bit is 0, so the number is even. See execution_table step 3 where the condition is checked.

Can this method work for negative numbers?

Yes, because the last bit still indicates even or odd regardless of sign. The bitwise AND operation works the same way.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'n & 1' at step 2?

A 0

B 5

C 1

D Undefined

💡 Hint

Check the 'Bitwise AND (n & 1)' column at step 2 in the execution_table.

At which step does the program conclude the number is odd?

A Step 2

B Step 3

C Step 1

D Step 4

💡 Hint

Look at the 'Conclusion' column in the execution_table for when the odd conclusion appears.

If the number was 8 instead of 5, what would 'n & 1' be at step 2?

A 0

B 1

C 8

D Undefined

💡 Hint

Remember that even numbers have last bit 0, so 'n & 1' would be 0. Refer to the concept_flow.

Concept Snapshot

Check if number is even or odd using bitwise AND:
- Use expression (n & 1)
- If result is 0, number is even
- If result is 1, number is odd
- Works by checking last binary bit
- Fast and efficient method

Full Transcript

This concept shows how to check if a number is even or odd using bits. We start with a number n. We perform a bitwise AND operation between n and 1, which checks the last bit of n. If the last bit is 0, the number is even; if it is 1, the number is odd. For example, with n=5, 5 & 1 equals 1, so 5 is odd. This method works for all integers and is very fast because it uses bit operations. The execution table traces each step: starting with n=5, calculating n & 1, checking the result, and concluding the number's parity.

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