Check if Number is Power of Two in DSA Go - Execution Trace

Concept Flow - Check if Number is Power of Two

Start with number n

↓

Check if n <= 0?

Yes→Return False

No↓

Check if n & (n-1) == 0?

Yes→Return True

No↓

Return False

Start with the number, ensure it's positive, then use bitwise check n & (n-1) to decide if it's a power of two.

Execution Sample

DSA Go

func isPowerOfTwo(n int) bool {
    if n <= 0 {
        return false
    }
    return (n & (n - 1)) == 0
}

This function returns true if n is a power of two, false otherwise.

Execution Table

Step	Operation	Input n	Check n <= 0	Compute n & (n-1)	Result	Return Value
1	Start	8	No
2	Check n <= 0	8	No
3	Compute n & (n-1)	8		8 & 7 = 0	0
4	Compare to 0	8			True	True
5	End	8				True
6	Start	10	No
7	Check n <= 0	10	No
8	Compute n & (n-1)	10		10 & 9 = 8	8
9	Compare to 0	10			False	False
10	End	10				False
11	Start	0	Yes
12	Check n <= 0	0	Yes
13	Return False	0				False

💡 Execution stops after returning True or False based on bitwise check or n <= 0 condition.

Variable Tracker

Variable	Start	After Step 3 (n=8)	After Step 8 (n=10)	After Step 12 (n=0)
n	input	8	10	0
n <= 0 check	undefined	false	false	true
n & (n-1)	undefined	0	8	undefined
Result (n & (n-1) == 0)	undefined	true	false	undefined
Return Value	undefined	true	false	false

Key Moments - 3 Insights

Why do we check if n <= 0 before the bitwise operation?

Because powers of two are positive numbers. If n is zero or negative, it cannot be a power of two. This is shown in execution_table rows 11-13 where n=0 returns false immediately.

What does the expression n & (n-1) == 0 mean?

It means n has only one bit set in its binary form. For example, 8 (1000) & 7 (0111) equals 0, so 8 is a power of two. This is shown in execution_table rows 3-4.

Why does the function return false for n=10?

Because 10 in binary is 1010, and 9 is 1001. Their bitwise AND is 1000 (8), not zero, so 10 is not a power of two. This is shown in execution_table rows 8-9.

Visual Quiz - 3 Questions

Look at the execution_table, what is the result of n & (n-1) when n=8 at step 3?

A 8

B 7

C 0

D 1

💡 Hint

Check the 'Compute n & (n-1)' column at step 3 in execution_table.

At which step does the function return false because n <= 0?

A Step 13

B Step 9

C Step 4

D Step 2

💡 Hint

Look for the step where 'Return False' happens due to n <= 0 in execution_table.

If n was 16, what would be the result of n & (n-1)?

A 16

B 0

C 15

D 1

💡 Hint

Recall that powers of two have n & (n-1) equal to zero, as shown for n=8 in execution_table.

Concept Snapshot

Check if number n is power of two:
- If n <= 0, return false
- Else return (n & (n-1)) == 0
This uses bitwise AND to check only one bit set
Example: 8 & 7 == 0 means 8 is power of two
Efficient and fast check

Full Transcript

This concept checks if a number is a power of two using a simple bitwise trick. First, it ensures the number is positive because powers of two cannot be zero or negative. Then it uses the expression n & (n-1) which clears the lowest set bit. If the result is zero, it means only one bit was set in n, so n is a power of two. The execution table shows step-by-step how the function handles inputs like 8, 10, and 0, returning true or false accordingly. The variable tracker follows the key variables through the steps. Key moments clarify why the checks are done and what the bitwise operation means. The visual quiz tests understanding of these steps. This method is efficient and commonly used in programming.

Practice

1. Which of the following statements correctly describes a number that is a power of two?

easy

A. It has exactly one bit set to 1 in its binary form.

B. It is always an odd number.

C. It is divisible by 3.

D. It has all bits set to 1 in its binary form.

Solution

1. Step 1: Understand binary representation of powers of two

   A power of two in binary has exactly one '1' bit and the rest are '0's. For example, 4 is 100 in binary.

2. Step 2: Analyze the options

   The statement "It has exactly one bit set to 1 in its binary form" matches the binary property of powers of two. The other options do not: powers of two (except 1) are even, not divisible by 3, and do not have all bits set to 1.

3. Final Answer:

   It has exactly one bit set to 1 in its binary form. -> Option A

4. Quick Check:

   Power of two = one '1' bit [OK]

Hint: Power of two has only one '1' bit in binary [OK]

Common Mistakes:

• Thinking powers of two are always odd
• Confusing powers of two with numbers divisible by 3
• Assuming all bits are set to 1

2. Which of the following Go code snippets correctly checks if an integer n is a power of two?

easy

A. if n & (n + 1) == 0 { /* power of two */ }

B. if n | (n - 1) == 0 { /* power of two */ }

C. if n & (n - 1) == 0 { /* power of two */ }

D. if n ^ (n - 1) == 0 { /* power of two */ }

Solution

1. Step 1: Understand bitwise check for power of two

   The expression n & (n - 1) == 0 is true only if n is a power of two (and n > 0).

2. Step 2: Analyze each option

   The snippet if n & (n - 1) == 0 { /* power of two */ } uses the correct bitwise AND operation. The others use incorrect bitwise operations that do not correctly check for power of two.

3. Final Answer:

   if n & (n - 1) == 0 { /* power of two */ } -> Option C

4. Quick Check:

   Use n & (n-1) == 0 to check power of two [OK]

Hint: Use n & (n-1) == 0 to check power of two [OK]

Common Mistakes:

• Using bitwise OR instead of AND
• Using n + 1 instead of n - 1
• Using XOR which does not work here

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

package main
import "fmt"
func main() {
    n := 16
    if n > 0 && (n & (n - 1)) == 0 {
        fmt.Println("Power of Two")
    } else {
        fmt.Println("Not Power of Two")
    }
}

medium

A. Runtime Error

B. Power of Two

C. Compilation Error

D. Not Power of Two

Solution

1. Step 1: Evaluate the condition for n = 16

   16 in binary is 10000. 16 - 1 = 15 (binary 01111). Bitwise AND: 10000 & 01111 = 0.

2. Step 2: Check the if condition

   Since n > 0 and bitwise AND is 0, the condition is true, so it prints "Power of Two".

3. Final Answer:

   Power of Two -> Option B

4. Quick Check:

   16 & 15 == 0 means power of two [OK]

Hint: Check if n & (n-1) == 0 and n > 0 [OK]

Common Mistakes:

• Ignoring n > 0 check
• Misunderstanding bitwise AND result
• Assuming all even numbers are powers of two

4. The following Go code is intended to check if n is a power of two. What is the error?

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

medium

A. The function should return an integer, not bool.

B. The bitwise AND operator is used incorrectly.

C. The parentheses around n - 1 are unnecessary and cause error.

D. It does not handle the case when n is zero or negative.

Solution

1. Step 1: Understand the function logic

   The expression n & (n - 1) == 0 returns true for powers of two and also for zero.

2. Step 2: Identify missing check

   Zero and negative numbers are not powers of two, but this function returns true for zero. It lacks a check for n > 0.

3. Final Answer:

   It does not handle the case when n is zero or negative. -> Option D

4. Quick Check:

   Check n > 0 before bitwise test [OK]

Hint: Always check n > 0 before bitwise power of two test [OK]

Common Mistakes:

• Not checking for n > 0
• Misusing bitwise operators
• Assuming parentheses cause error

5. You want to write a Go function that returns true if a number n is a power of two, but also handles zero and negative inputs correctly. Which of the following implementations is correct?

hard

A. func isPowerOfTwo(n int) bool {
return n > 0 && (n & (n - 1)) == 0
}

B. func isPowerOfTwo(n int) bool {
return n >= 0 && (n | (n - 1)) == 0
}

C. func isPowerOfTwo(n int) bool {
return n != 0 && (n & (n + 1)) == 0
}

D. func isPowerOfTwo(n int) bool {
return (n & (n - 1)) == 1
}

Solution

1. Step 1: Check for positive input

   The function must ensure n is greater than zero to exclude zero and negatives.

2. Step 2: Use correct bitwise condition

   The condition (n & (n - 1)) == 0 correctly identifies powers of two.

3. Step 3: Analyze options

   The implementation func isPowerOfTwo(n int) bool { return n > 0 && (n & (n - 1)) == 0 } correctly combines both checks. The others use incorrect operators or conditions.

4. Final Answer:

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

5. Quick Check:

   Check n > 0 and n & (n-1) == 0 [OK]

Hint: Check n > 0 and n & (n-1) == 0 for power of two [OK]

Common Mistakes:

• Using bitwise OR instead of AND
• Not checking n > 0
• Using wrong bitwise expressions