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

The Big Idea

Discover how a tiny bit can save you from slow math and make your programs lightning fast!

The Scenario

Imagine you want to quickly decide if a number is even or odd while doing math homework or programming a game. You might try dividing the number by 2 and checking the remainder.

But what if you have to check millions of numbers fast? Doing division every time can slow things down.

The Problem

Using division or modulus (%) to check even or odd is slow because computers take more time to divide than to do simple bit checks.

Also, division can be more error-prone if you forget to handle negative numbers or zero correctly.

The Solution

Using bits, you can check the last bit of a number to see if it is 0 or 1. If the last bit is 0, the number is even; if it is 1, the number is odd.

This method is very fast and uses simple operations that computers do instantly.

Before vs After

✗ Before

if number % 2 == 0 {
    fmt.Println("Even")
} else {
    fmt.Println("Odd")
}

✓ After

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

What It Enables

This lets you quickly and efficiently check even or odd numbers in programs that need speed, like games or big data processing.

Real Life Example

In video games, deciding if a character's step number is even or odd can change animations or sounds instantly without slowing the game.

Key Takeaways

Division for even/odd is slower and more complex.

Bitwise AND with 1 quickly tells if a number is even or odd.

This method is simple, fast, and reliable for many programming tasks.

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