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

Overview - Check if Number is Even or Odd Using Bits

What is it?

Checking if a number is even or odd using bits means looking at the number's binary form and using a simple rule to decide its type. Instead of dividing the number by 2, we use a bit operation that is faster and more direct. This method uses the fact that even numbers always end with a 0 in binary, and odd numbers end with a 1. It is a quick way to tell if a number is even or odd by looking at its last bit.

Why it matters

This method exists because it is much faster and more efficient than using division or modulus operations, especially in computers. Without this, programs would take longer to check even or odd numbers, which can slow down many applications like games, data processing, or real-time systems. Using bits saves time and energy, making software run smoother and faster.

Where it fits

Before learning this, you should understand what binary numbers are and how bits represent numbers. After this, you can learn about other bitwise operations and how they help in optimizing algorithms and solving problems quickly.

Mental Model

Core Idea

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

Think of it like...

It's like checking if a light switch is off or on to know if the room is dark or lit; the last bit is the switch that tells the number's type.

Number in binary:  ... b3 b2 b1 b0
                      └──┘
                      last bit
If last bit (b0) = 0 -> Even
If last bit (b0) = 1 -> Odd

Build-Up - 6 Steps

1

Foundation

Understanding Binary Numbers

Concept: Learn how numbers are represented in binary form using bits.

Every number in a computer is stored as a series of bits (0s and 1s). Each bit represents a power of 2, starting from the rightmost bit which is 2^0 (1). For example, the number 6 in binary is 110 because it is 1*4 + 1*2 + 0*1.

Result

You can see any number as a sequence of bits, where each bit has a place value.

Understanding binary is essential because bitwise operations work directly on these bits, making them very fast and efficient.

2

Foundation

What Makes a Number Even or Odd

Concept: The difference between even and odd numbers in binary is in the last bit.

Even numbers end with 0 in binary because they are multiples of 2. Odd numbers end with 1 because they have one extra unit beyond a multiple of 2. For example, 4 is 100 (ends with 0), and 5 is 101 (ends with 1).

Result

You can tell if a number is even or odd just by looking at its last bit.

Knowing this simple fact lets us use bit operations to check even or odd without division.

3

Intermediate

Using Bitwise AND to Check Last Bit

🤔Before reading on: do you think using AND with 1 will keep or remove the last bit? Commit to your answer.

Concept: Bitwise AND with 1 isolates the last bit of a number.

The AND operation compares each bit of two numbers. When you AND any number with 1 (binary 0001), all bits except the last become 0. The last bit stays the same. For example, 6 (110) & 1 (001) = 0, and 7 (111) & 1 (001) = 1.

Result

If (number & 1) == 0, number is even; if 1, number is odd.

Understanding how AND isolates the last bit is key to using bitwise operations for even-odd checks.

4

Intermediate

Implementing Even-Odd Check in Go

🤔Before reading on: do you think the code will print 'Even' for 10 and 'Odd' for 7? Commit to your answer.

Concept: Write a Go program using bitwise AND to check if a number is even or odd.

package main import "fmt" func main() { numbers := []int{10, 7, 0, -3, -4} for _, num := range numbers { if num&1 == 0 { fmt.Printf("%d is Even\n", num) } else { fmt.Printf("%d is Odd\n", num) } } }

Result

10 is Even 7 is Odd 0 is Even -3 is Odd -4 is Even

Seeing the code in action confirms the bitwise method works for positive, zero, and negative numbers.

5

Advanced

Why Bitwise is Faster Than Modulus

🤔Before reading on: do you think bitwise operations are faster than modulus (%)? Commit to your answer.

Concept: Bitwise operations are simpler and faster at the machine level than division or modulus.

Modulus (%) requires division, which is a complex and slower operation for the CPU. Bitwise AND is a single CPU instruction that directly manipulates bits. This difference matters in performance-critical code or when checking many numbers quickly.

Result

Using bitwise AND reduces CPU cycles and speeds up programs that check even or odd numbers repeatedly.

Knowing the performance difference helps choose the best method in real-world programming.

6

Expert

Handling Negative Numbers in Bitwise Checks

🤔Before reading on: do you think negative numbers behave the same as positive ones with bitwise AND? Commit to your answer.

Concept: Negative numbers use two's complement binary representation, but the last bit still indicates even or odd.

In two's complement, negative numbers have the same last bit pattern for even or odd as positive numbers. For example, -3 in binary ends with 1, so it is odd. This means the bitwise AND method works for negative numbers without changes.

Result

The bitwise check correctly identifies even or odd for negative numbers too.

Understanding two's complement ensures confidence that bitwise checks are universally valid.

Under the Hood

At the machine level, numbers are stored as sequences of bits. The bitwise AND operation compares each bit of two numbers and returns 1 only if both bits are 1. When ANDing with 1, all bits except the least significant bit become 0, isolating that last bit. This operation is a single CPU instruction, making it extremely fast.

Why designed this way?

Computers use binary because it is simple and reliable to represent two states (0 and 1). Bitwise operations were designed to manipulate these bits directly for efficiency. Checking even or odd by looking at the last bit avoids costly division operations, improving speed and reducing power consumption.

Number bits:  b7 b6 b5 b4 b3 b2 b1 b0
                 │  │  │  │  │  │  │  └─ last bit
AND with 1:      0  0  0  0  0  0  0  1
Result:          0  0  0  0  0  0  0  b0
If b0=0 -> Even
If b0=1 -> Odd

Myth Busters - 3 Common Misconceptions

Quick: Does checking (number & 1) work for negative numbers the same as positive? Commit yes or no.

Common Belief: Bitwise even-odd check only works for positive numbers.

Reality: It works for negative numbers too because two's complement preserves the last bit meaning.

Why it matters: Believing otherwise might cause unnecessary code complexity or wrong checks for negative values.

Quick: Is bitwise AND with 1 the same as modulus 2? Commit yes or no.

Common Belief: Bitwise AND with 1 is different and less reliable than modulus 2.

Reality: They produce the same result for even-odd checks, but bitwise is faster.

Why it matters: Not knowing this can lead to slower code and missed optimization opportunities.

Quick: Does the last bit alone always tell if a number is even or odd? Commit yes or no.

Common Belief: Sometimes other bits affect even-odd status, not just the last bit.

Reality: Only the last bit determines even or odd; other bits do not affect this property.

Why it matters: Misunderstanding this can cause confusion and incorrect bitwise logic.

Expert Zone

1

Negative numbers in two's complement keep the last bit meaning, but their full binary form is different, which can confuse beginners.

2

Bitwise operations are atomic and can be used safely in concurrent programming without locks for simple checks.

3

Some processors have special instructions optimized for bitwise operations, making this method even more efficient on certain hardware.

When NOT to use

Avoid bitwise checks if you need to handle non-integer types or very large numbers where bitwise operations are not defined. Also, if code clarity is more important than performance, using modulus (%) might be preferred for readability.

Production Patterns

In real-world systems, bitwise even-odd checks are used in embedded systems, game loops, and performance-critical code where millions of checks happen per second. They are also common in low-level device drivers and network packet processing.

Connections

Bitwise Operations

Builds-on

Understanding even-odd checks using bits opens the door to mastering other bitwise operations like shifts, masks, and toggles.

Two's Complement Representation

Depends on

Knowing how negative numbers are stored in two's complement explains why bitwise checks work uniformly for positive and negative integers.

Digital Electronics

Shares principles

The concept of checking the last bit to determine parity is similar to how digital circuits use flip-flops and gates to detect signals and states.

Common Pitfalls

#1 Assuming bitwise AND with 1 works on floating-point numbers.

Wrong approach:

var num float64 = 4.0
if int(num)&1 == 0 {
fmt.Println("Even")
} else {
fmt.Println("Odd")
}

Correct approach:

var num int = 4
if num&1 == 0 {
fmt.Println("Even")
} else {
fmt.Println("Odd")
}

Root cause:

Bitwise operations only work on integers; converting floats to int without care can cause errors or unexpected results.

#2 Using bitwise AND with a number other than 1 to check even or odd.

Wrong approach:

if num&2 == 0 {
fmt.Println("Even")
} else {
fmt.Println("Odd")
}

Correct approach:

if num&1 == 0 {
fmt.Println("Even")
} else {
fmt.Println("Odd")
}

Root cause:

Only the least significant bit (bit 0) determines even or odd; using other bits gives wrong results.

#3 Ignoring negative numbers and assuming bitwise check fails.

Wrong approach:

if num < 0 {
// fallback to modulus
if num%2 == 0 {
fmt.Println("Even")
} else {
fmt.Println("Odd")
}
} else {
if num&1 == 0 {
fmt.Println("Even")
} else {
fmt.Println("Odd")
}
}

Correct approach:

if num&1 == 0 {
fmt.Println("Even")
} else {
fmt.Println("Odd")
}

Root cause:

Misunderstanding two's complement representation causes unnecessary complexity.

Key Takeaways

The last bit of a binary number uniquely determines if it is even or odd.

Using bitwise AND with 1 is a fast and efficient way to check even or odd without division.

This method works for positive, zero, and negative integers due to two's complement representation.

Bitwise operations are single CPU instructions, making them faster than modulus operations.

Understanding binary and bitwise logic is foundational for many performance optimizations in programming.

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