Why Check if Number is Power of Two in DSA Go?

The Big Idea

Discover the magic trick that turns slow division into instant power-of-two checks!

The Scenario

Imagine you have a big list of numbers and you want to find out which ones are powers of two, like 1, 2, 4, 8, 16, and so on. Doing this by hand means dividing each number by 2 again and again until you reach 1 or a number that is not divisible by 2.

The Problem

This manual way is slow and boring, especially if the list is very long. It's easy to make mistakes counting divisions or forgetting to check all numbers. It wastes time and can cause errors.

The Solution

Using a simple trick with bits, computers can quickly check if a number is a power of two without dividing repeatedly. This method is fast, clean, and reliable, saving time and avoiding mistakes.

Before vs After

✗ Before

func isPowerOfTwo(number int) bool {
    if number < 1 {
        return false
    }
    for number%2 == 0 {
        number = number / 2
    }
    return number == 1
}

✓ After

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

What It Enables

This lets you instantly check if a number is a power of two, enabling faster programs and easier problem solving.

Real Life Example

In computer memory, sizes are often powers of two. Quickly checking if a size fits this rule helps optimize storage and speed.

Key Takeaways

Manual division to check powers of two is slow and error-prone.

Bitwise tricks provide a fast and simple solution.

This method improves performance and reliability in many computing tasks.

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