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

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

Start with number n

↓

Check last bit: n & 1

↓

Output Even

↓

End

We check the last bit of the number using bitwise AND with 1. If last bit is 0, number is even; if 1, number is odd.

Execution Sample

DSA Go

func isEven(n int) bool {
    return (n & 1) == 0
}

// Example: n = 5
// 5 in binary: 0101
// 5 & 1 = 1 (odd)

This code checks if the last bit of n is 0 (even) or 1 (odd) using bitwise AND.

Execution Table

Step	Operation	Number (n)	Bitwise AND (n & 1)	Result	Output
1	Start with n	5 (0101)	-	-	-
2	Calculate n & 1	5 (0101)	1 (0001)	1	Odd
3	Check if (n & 1) == 0	5 (0101)	1	False	Odd
4	Return result	5 (0101)	-	-	False (odd)
5	End	-	-	-	-

💡 Bitwise AND result is 1, so number is odd; execution stops.

Variable Tracker

Variable	Start	After Step 2	After Step 3	Final
n	5	5	5	5
n & 1	-	1	1	1
isEven	-	-	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's even (0) or odd (1). See execution_table step 2 where n & 1 extracts the last bit.

What if the number is 0? Is it even or odd?

0 in binary ends with 0, so n & 1 = 0, meaning even. This matches the logic in execution_table step 3.

Why not use modulo (%) operator instead of bitwise AND?

Bitwise AND is faster and directly checks the last bit, unlike modulo which does division. The code uses n & 1 for efficiency as shown in execution_sample.

Visual Quiz - 3 Questions

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

A 0

B 1

C 5

D Undefined

💡 Hint

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

At which step does the code decide the number is odd?

A Step 1

B Step 4

C Step 3

D Step 5

💡 Hint

Look at the 'Result' and 'Output' columns in execution_table to see when odd is determined.

If n was 4, what would 'n & 1' be at step 2?

A 0

B 1

C 4

D Undefined

💡 Hint

Recall that even numbers have last bit 0; check variable_tracker for n & 1 values.

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
- This checks the last binary bit efficiently
- Faster than modulo operator

Full Transcript

To check if a number is even or odd using bits, we look at the last bit of its binary form. Using bitwise AND with 1 (n & 1) extracts this last bit. If the result is 0, the number is even; if 1, it is odd. For example, number 5 in binary is 0101. 5 & 1 equals 1, so 5 is odd. This method is efficient and faster than using modulo. The code returns true if even, false if odd based on this check.

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