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

The Big Idea

Discover how a tiny bit can save you big time in 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 long.

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 large data or in devices with limited resources.

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 method is very fast and efficient.

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 determine even or odd numbers, speeding up programs and saving resources.

Real Life Example

In games or graphics, quickly checking even or odd numbers can help decide patterns or colors without slowing down the frame rate.

Key Takeaways

Manual division is slower and uses more resources.

Bitwise check uses only one bit to decide even or odd.

This method is faster and better for performance-critical tasks.

Practice

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

easy

A. Shift the number right by 1

B. Check the least significant bit using AND with 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: 0 means even, 1 means odd.

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

   Performing bitwise AND with 1 keeps only the LSB. If result is 0, number is even; if 1, odd.

3. Final Answer:

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

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 an integer n is odd using bitwise operators?

easy

A. if ((n & 1) == 1) printf("Odd");

B. if ((n >> 1) == 1) printf("Odd");

C. if ((n & 1) == 0) printf("Odd");

D. if ((n ^ 1) == 1) printf("Odd");

Solution

1. Step 1: Understand bitwise AND with 1

   Using n & 1 isolates the least significant bit. If it equals 1, the number is odd.

2. Step 2: Check condition for odd number

   The correct condition is (n & 1) == 1 to print "Odd".

3. Final Answer:

   if ((n & 1) == 1) printf("Odd"); -> Option A

4. Quick Check:

   n & 1 == 1 means odd [OK]

Hint: Use (n & 1) == 1 to detect odd numbers [OK]

Common Mistakes:

• Checking for == 0 to print odd (actually even)
• Using right shift instead of AND
• Using XOR incorrectly for odd check

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

int n = 14;
if (n & 1)
    printf("Odd");
else
    printf("Even");

medium

A. Odd

B. Compilation error

C. Even

D. 14

Solution

1. Step 1: Evaluate n & 1 for n = 14

   Binary of 14 is 1110. The least significant bit is 0. So, 14 & 1 = 0.

2. Step 2: Check the if condition

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

3. Final Answer:

   Even -> Option C

4. Quick Check:

   14 is even, so output is 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 logical AND
• Expecting output "14" instead of even/odd

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

int n = 7;
if (n & 1 == 1)
    printf("Odd");
else
    printf("Even");

medium

A. Missing parentheses around (n & 1)

B. Using == instead of = in if condition

C. Incorrect use of bitwise OR instead of AND

D. No error, code works fine

Solution

1. Step 1: Analyze operator precedence in condition

   In C, == has higher precedence than &. So expression is evaluated as n & (1 == 1).

2. Step 2: Evaluate the expression and fix

   Since (1 == 1) is true (1), expression becomes n & 1, which is correct but confusing. To avoid this, parentheses should be used: (n & 1) == 1.

3. Final Answer:

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

4. Quick Check:

   Use (n & 1) == 1 to ensure correct evaluation [OK]

Hint: Use parentheses: (n & 1) == 1 to avoid precedence errors [OK]

Common Mistakes:

• Ignoring operator precedence causing wrong evaluation
• Using assignment = instead of comparison ==
• Confusing bitwise AND with logical AND

5. You want to write a function in C that returns 1 if a number is odd and 0 if even, using bitwise operators. Which of the following implementations is correct and efficient?

int isOdd(int n) {
    // Choose one
}

hard

A. return (n >> 1) & 1;

B. return !(n & 1);

C. return n ^ 1;

D. return (n & 1) == 1 ? 1 : 0;

Solution

1. Step 1: Understand the goal of the function

   The function should return 1 if n is odd, 0 if even, using bitwise operations.

2. Step 2: Evaluate each option

   return (n & 1) == 1 ? 1 : 0; correctly returns 1 if LSB is 1 (odd), else 0. return (n >> 1) & 1; returns the second least significant bit, incorrect. return n ^ 1; returns n XOR 1, which changes the number, not a boolean. return !(n & 1); returns 1 if even, opposite of requirement.

3. Final Answer:

   return (n & 1) == 1 ? 1 : 0; -> Option D

4. Quick Check:

   Use (n & 1) == 1 to detect odd and return 1 [OK]

Hint: Return (n & 1) == 1 for odd check function [OK]

Common Mistakes:

• Using bit shift instead of checking LSB
• Returning modified number instead of boolean
• Negating the condition incorrectly