Check if Number is Even or Odd Using Bits in DSA Go

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, the number of cars is odd; if all cars are paired, the number is even. 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

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

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

5 in binary: 0101
1 in binary: 0001
Result: 0001 (which is 1)

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

Step 2: Check if result is 0 or 1

Result is 1

Why: If last bit is 1, number is odd

Result:

5 -> last bit 1 -> odd

Annotated Code

DSA Go

package main

import "fmt"

func isEven(num int) bool {
    // Check last bit using bitwise AND
    return (num & 1) == 0
}

func main() {
    number := 5
    if isEven(number) {
        fmt.Printf("%d is even\n", number)
    } else {
        fmt.Printf("%d is odd\n", number)
    }
}

return (num & 1) == 0

Check last bit to determine evenness

if isEven(number) {

Decide output based on bit check

Output

5 is odd

Complexity Analysis

Time: O(1) because bitwise operations take constant time regardless of number size

Space: O(1) because no extra memory is used besides input and a few variables

vs Alternative: Using modulo (%) operator also takes O(1) but bitwise AND is faster and more efficient at low level

Edge Cases

number = 0

Returns even because 0 & 1 == 0

DSA Go

return (num & 1) == 0

number = 1

Returns odd because 1 & 1 == 1

DSA Go

return (num & 1) == 0

negative numbers like -2

Works correctly because bitwise AND checks last bit regardless of sign

DSA Go

return (num & 1) == 0

When to Use This Pattern

When you need a fast way to check if a number is even or odd, use bitwise AND with 1 because it directly inspects the last binary digit.

Common Mistakes

Mistake: Using modulo operator (%) instead of bitwise AND when bit operations are required
Fix: Replace num % 2 == 0 with (num & 1) == 0 for bit-level check

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

Summary

It checks if the last bit of a number is 0 or 1 to decide even or odd.

Use it when you want a quick, low-level check for evenness without division.

The key insight is that the last binary bit alone tells if a number is even or odd.

Practice

1. What does the expression num & 1 check when determining if a number is even or odd?

easy

A. It checks the least significant bit to see if it is 1 (odd) or 0 (even).

B. It checks if the number is greater than 1.

C. It divides the number by 2.

D. It adds 1 to the number.

Solution

1. Step 1: Understand bitwise AND operation

   The expression num & 1 performs a bitwise AND between the number and 1, which isolates the least significant bit (rightmost bit).

2. Step 2: Interpret the least significant bit

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

3. Final Answer:

   It checks the least significant bit to see if it is 1 (odd) or 0 (even). -> Option A

4. Quick Check:

   num & 1 = 1 means odd, 0 means even [OK]

Hint: Check last bit with & 1; 1 means odd, 0 means even [OK]

Common Mistakes:

• Thinking & 1 divides the number
• Confusing bitwise AND with addition
• Assuming it checks if number > 1

2. Which of the following Go code snippets correctly checks if an integer n is odd using bitwise operations?

easy

A. if n & 0 == 1 { fmt.Println("Odd") }

B. if n | 1 == 1 { fmt.Println("Odd") }

C. if n ^ 1 == 1 { fmt.Println("Odd") }

D. if n & 1 == 1 { fmt.Println("Odd") }

Solution

1. Step 1: Analyze bitwise AND usage

   The correct way to check oddness is using bitwise AND with 1: n & 1. This isolates the least significant bit.

2. Step 2: Check condition correctness

   if n & 1 == 1 { fmt.Println("Odd") } uses n & 1 == 1, which is true if the number is odd. Other options use incorrect operators or values.

3. Final Answer:

   if n & 1 == 1 { fmt.Println("Odd") } -> Option D

4. Quick Check:

   Use & 1 == 1 to check odd [OK]

Hint: Use 'if n & 1 == 1' to check odd numbers in Go [OK]

Common Mistakes:

• Using bitwise OR instead of AND
• Comparing with 0 instead of 1
• Using XOR which changes bits

3. What will be the output of the following Go code?

package main
import "fmt"
func main() {
    n := 14
    if n & 1 == 0 {
        fmt.Println("Even")
    } else {
        fmt.Println("Odd")
    }
}

medium

A. Even

B. Odd

C. 14

D. Compilation error

Solution

1. Step 1: Evaluate bitwise AND for n=14

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

2. Step 2: Check the if condition

   Since 14 & 1 == 0, the condition is true, so it prints "Even".

3. Final Answer:

   Even -> Option A

4. Quick Check:

   14 & 1 = 0 means Even [OK]

Hint: If n & 1 == 0, number is even [OK]

Common Mistakes:

• Assuming 14 is odd
• Confusing bitwise AND with arithmetic AND
• Expecting output to be the number itself

4. Find the error in this Go code snippet that tries to print if a number is even or odd:

package main
import "fmt"
func main() {
    num := 7
    if num & 1 = 1 {
        fmt.Println("Odd")
    } else {
        fmt.Println("Even")
    }
}

medium

A. Using bitwise AND instead of OR

B. Using single '=' instead of '==' in if condition

C. Missing import statement

D. Variable 'num' not declared

Solution

1. Step 1: Identify the if condition syntax

   The condition uses single '=' which is assignment, not comparison. It should be '==' to compare values.

2. Step 2: Understand Go syntax rules

   Go requires '==' for equality checks. Using '=' in if condition causes a compilation error.

3. Final Answer:

   Using single '=' instead of '==' in if condition -> Option B

4. Quick Check:

   Use '==' for comparison, not '=' [OK]

Hint: Use '==' for comparison in if statements [OK]

Common Mistakes:

• Using '=' instead of '==' in conditions
• Confusing bitwise AND with logical AND
• Forgetting to declare variables

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

hard

A. func IsEven(n int) bool { return n & 1 == 1 }

B. func IsEven(n int) bool { return n | 1 == 0 }

C. func IsEven(n int) bool { return n & 1 == 0 }

D. func IsEven(n int) bool { return (n >> 1) == 0 }

Solution

1. Step 1: Understand even number bit pattern

   Even numbers have least significant bit 0, so n & 1 equals 0 for even numbers.

2. Step 2: Verify the correct implementation

   func IsEven(n int) bool { return n & 1 == 0 } is correct because even numbers have LSB 0. The implementation returning n & 1 == 1 checks for odd. The bitwise OR and right shift implementations are incorrect for checking evenness.

3. Final Answer:

   func IsEven(n int) bool { return n & 1 == 0 } -> Option C

4. Quick Check:

   Return true if n & 1 == 0 for even [OK]

Hint: Return n & 1 == 0 to check even numbers [OK]

Common Mistakes:

• Returning true for odd numbers instead of even
• Using right shift incorrectly
• Using bitwise OR instead of AND