Check if Number is Power of Two in DSA Go

Mental Model

A number is a power of two if it can be made by multiplying 2 by itself some times, like 1, 2, 4, 8, 16, and so on.

Analogy: Think of stacking blocks where each new stack doubles the height of the previous one. If the height matches exactly one of these stacks, it is a power of two.

Number: 8
Binary: 1 0 0 0
Only one '1' bit means power of two.

Dry Run Walkthrough

Input: number = 8

Goal: Check if 8 is a power of two

Step 1: Check if number is zero or negative

number = 8

Why: Zero or negative numbers cannot be powers of two

Step 2: Calculate number & (number - 1): 8 & 7

8 (1000) & 7 (0111) = 0 (0000)

Why: If result is zero, number has only one '1' bit, so it is power of two

Step 3: Return true because result is zero

number = 8 is power of two

Why: Only one bit set means power of two

Result:

8 is a power of two: true

Annotated Code

DSA Go

package main

import "fmt"

func isPowerOfTwo(n int) bool {
    if n <= 0 {
        return false // negative or zero can't be power of two
    }
    return (n & (n - 1)) == 0 // true if only one bit set
}

func main() {
    number := 8
    result := isPowerOfTwo(number)
    fmt.Printf("%d is a power of two: %t\n", number, result)
}

if n <= 0 { return false }

exclude zero and negative numbers early

return (n & (n - 1)) == 0

check if only one bit is set by bitwise AND with n-1

Output

8 is a power of two: true

Complexity Analysis

Time: O(1) because bitwise operations take constant time

Space: O(1) because no extra space is used

vs Alternative: Compared to looping and dividing by 2 repeatedly (O(log n)), this bitwise method is faster and simpler

Edge Cases

number = 0

returns false because zero is not a power of two

DSA Go

if n <= 0 { return false }

number = 1

returns true because 1 is 2^0, a power of two

DSA Go

return (n & (n - 1)) == 0

number = -4

returns false because negative numbers are not powers of two

DSA Go

if n <= 0 { return false }

When to Use This Pattern

When you need to quickly check if a number is a power of two, use the bitwise AND trick n & (n-1) == 0 because it efficiently tests if only one bit is set.

Common Mistakes

Mistake: Checking if number % 2 == 0 repeatedly without stopping at 1
Fix: Use the bitwise method or ensure the loop divides until number equals 1

Mistake: Not handling zero or negative numbers
Fix: Add a check to return false if number is less than or equal to zero

Summary

Checks if a number has exactly one bit set in binary, meaning it is a power of two.

Use when you want a fast, simple way to verify powers of two without loops.

The key insight is that powers of two have only one '1' bit, so n & (n-1) clears that bit and results in zero.

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