Check if Number is Power of Two in DSA Go - Deep Dive

Overview - Check if Number is Power of Two

What is it?

Checking if a number is a power of two means finding out if it can be written as 2 raised to some whole number. For example, 1, 2, 4, 8, and 16 are powers of two. This check helps in many computer tasks where powers of two have special importance. It is a simple yes or no question about the number.

Why it matters

Many computer systems and algorithms work best or only work correctly when numbers are powers of two. Without this check, programs might run slower or give wrong answers. For example, memory sizes and data structures often rely on powers of two for efficiency. Knowing if a number is a power of two helps optimize and avoid errors.

Where it fits

Before this, you should understand basic number properties and binary numbers. After this, you can learn about bitwise operations and how computers use bits to represent numbers. This concept is a stepping stone to more advanced topics like efficient algorithms and memory management.

Mental Model

Core Idea

A number is a power of two if it has exactly one '1' bit in its binary form.

Think of it like...

Imagine a row of light switches where only one switch is turned on at a time. If exactly one switch is on, the number is a power of two; if more or none are on, it is not.

Binary representation example:

Number: 8
Binary: 00001000

Only one '1' bit is on, so 8 is a power of two.

Number: 10
Binary: 00001010

Two '1' bits are on, so 10 is NOT a power of two.

Build-Up - 7 Steps

1

Foundation

Understanding Powers of Two

Concept: Learn what powers of two are and how they look in numbers.

Powers of two are numbers like 1, 2, 4, 8, 16, 32, and so on. Each is 2 multiplied by itself some number of times. For example, 2^0 = 1, 2^1 = 2, 2^2 = 4, 2^3 = 8, etc. These numbers grow quickly and have special patterns in binary.

Result

You can recognize powers of two by their values and understand their importance.

Understanding the basic pattern of powers of two sets the foundation for recognizing them in different forms, especially binary.

2

Foundation

Binary Representation Basics

Concept: Learn how numbers are shown in binary, using only 0s and 1s.

Every number can be written in binary, which is a series of bits (0s and 1s). Each bit represents a power of two. For example, the number 5 is 101 in binary (1*4 + 0*2 + 1*1). This helps us see patterns related to powers of two.

Result

You can convert simple numbers to binary and understand what each bit means.

Knowing binary is key because powers of two have a unique pattern in binary: only one bit is set to 1.

3

Intermediate

Identifying Single Set Bit Pattern

🤔Before reading on: do you think a power of two can have multiple '1' bits in binary? Commit to yes or no.

Concept: A power of two has exactly one bit set to 1 in its binary form.

Look at binary numbers: 1 (0001), 2 (0010), 4 (0100), 8 (1000). Each has only one '1'. Numbers like 3 (0011) or 6 (0110) have more than one '1' bit and are not powers of two. This pattern helps us check quickly.

Result

You can tell if a number is a power of two by counting its '1' bits in binary.

Recognizing the single set bit pattern is the mental shortcut that makes checking powers of two fast and simple.

4

Intermediate

Using Bitwise AND Trick

🤔Before reading on: do you think n & (n-1) equals zero for powers of two? Commit to yes or no.

Concept: Using bitwise AND between a number and one less than it can tell if it's a power of two.

For a power of two n, n & (n-1) equals 0. For example, 8 (1000) & 7 (0111) = 0. For 10 (1010) & 9 (1001) = 8 (1000), not zero. This is a fast way to check without counting bits.

Result

You can quickly check if a number is a power of two using a simple bitwise operation.

Understanding this trick reveals how computers use bits to perform fast checks without loops or counting.

5

Intermediate

Handling Edge Cases and Zero

🤔Before reading on: is zero a power of two? Commit to yes or no.

Concept: Zero and negative numbers are not powers of two and must be handled separately.

Zero (0) has no bits set and is not a power of two. Negative numbers in two's complement form have different bit patterns and are not powers of two. So, the check must exclude these cases explicitly.

Result

You avoid false positives by excluding zero and negatives from the check.

Knowing edge cases prevents bugs and ensures your check is correct for all inputs.

6

Advanced

Implementing in Go with Bitwise Operations

🤔Before reading on: do you think the Go code can check power of two in one line? Commit to yes or no.

Concept: Use Go's bitwise operators to implement the check efficiently and clearly.

Here is a Go function: func isPowerOfTwo(n int) bool { return n > 0 && (n&(n-1)) == 0 } This returns true if n is positive and n & (n-1) is zero, meaning n is a power of two.

Result

The function returns true for powers of two and false otherwise, quickly and cleanly.

Writing concise code using bitwise logic leverages computer hardware for speed and simplicity.

7

Expert

Why Bitwise Check is Optimal and Its Limits

🤔Before reading on: do you think this method works for all integer types and sizes? Commit to yes or no.

Concept: The bitwise check is optimal but depends on integer representation and size.

The check works because of binary representation and two's complement for signed integers. However, for unsigned integers or very large numbers, behavior depends on type size. Also, this method doesn't work for floating-point numbers or non-integers. Understanding these limits is key for correct use.

Result

You know when this method applies and when to use other checks or data types.

Knowing the underlying assumptions prevents misuse and subtle bugs in complex systems.

Under the Hood

The check n & (n-1) == 0 works because subtracting 1 from a power of two flips the only set bit and all lower bits. When ANDed with the original number, the result is zero if and only if there was exactly one set bit. This relies on binary arithmetic and two's complement representation for negative numbers.

Why designed this way?

This method was designed to leverage fast bitwise operations that CPUs perform natively. It avoids loops or counting bits, making it very efficient. Alternatives like counting bits are slower. The design balances speed and simplicity, fitting well with how computers represent numbers.

Number n in binary:    00010000 (16)
Number n-1 in binary:  00001111 (15)
Bitwise AND (n & n-1): 00000000 (0)

Only one bit set in n causes AND with n-1 to clear that bit, resulting in zero.

Myth Busters - 4 Common Misconceptions

Quick: Is zero considered a power of two? Commit to yes or no.

Common Belief: Zero is a power of two because 2^0 equals 1, so zero must be included.

Reality: Zero is not a power of two. 2^0 equals 1, not zero. Zero has no bits set and fails the bitwise check.

Why it matters: Treating zero as a power of two causes incorrect results and bugs in algorithms relying on this check.

Quick: Can negative numbers be powers of two? Commit to yes or no.

Common Belief: Negative numbers can be powers of two if their absolute value is a power of two.

Reality: Negative numbers are not powers of two in standard integer representation. Their binary form in two's complement has multiple bits set.

Why it matters: Ignoring sign leads to false positives and errors in programs that expect only positive powers of two.

Quick: Does the bitwise check work for floating-point numbers? Commit to yes or no.

Common Belief: The bitwise check works for any number, including decimals.

Reality: The bitwise check only works for integers. Floating-point numbers have different binary formats and cannot be checked this way.

Why it matters: Applying this check to floats causes wrong results and confusion.

Quick: Does having one '1' bit always mean the number is a power of two? Commit to yes or no.

Common Belief: If a number has one '1' bit in binary, it is always a power of two.

Reality: This is true only for positive integers. Zero and negatives can have one '1' bit but are not powers of two.

Why it matters: Not checking positivity leads to incorrect conclusions.

Expert Zone

1

The bitwise trick depends on two's complement representation; different integer encodings would break it.

2

For unsigned integers, the check is simpler since negativity is not a concern, but care is needed with zero.

3

In some systems, compiler optimizations can replace this check with hardware instructions for even faster performance.

When NOT to use

Do not use this method for floating-point numbers, negative integers, or non-integer types. For floats, use logarithmic checks or math libraries. For arbitrary large integers, consider bit counting or specialized libraries.

Production Patterns

This check is widely used in low-level system code, memory allocators, graphics programming, and performance-critical algorithms where powers of two align data or optimize loops.

Connections

Bit Manipulation

Builds-on

Understanding this check deepens knowledge of bit manipulation techniques, which are fundamental for efficient low-level programming.

Memory Alignment

Application

Powers of two are crucial in memory alignment, ensuring data is stored efficiently and accessed quickly in hardware.

Signal Processing

Cross-domain similarity

In signal processing, powers of two determine FFT sizes for efficient computation, showing how this concept spans computing and engineering.

Common Pitfalls

#1 Including zero as a power of two.

Wrong approach:

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

Correct approach:

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

Root cause:

Not checking that n is positive allows zero to pass the bitwise check incorrectly.

#2 Applying the check to negative numbers.

Wrong approach:

func isPowerOfTwo(n int) bool {
return n > 0 && (n & (n-1)) == 0
}
// Called with n = -8

Correct approach:

func isPowerOfTwo(n int) bool {
return n > 0 && (n & (n-1)) == 0
}
// Avoid calling with negative numbers or handle separately

Root cause:

Misunderstanding that negative numbers cannot be powers of two in two's complement.

#3 Trying to use this method on floating-point numbers.

Wrong approach:

func isPowerOfTwoFloat(f float64) bool {
return int(f) > 0 && (int(f) & (int(f)-1)) == 0
}

Correct approach:

func isPowerOfTwoFloat(f float64) bool {
if f <= 0 || f != float64(int(f)) {
return false
}
n := int(f)
return n > 0 && (n & (n-1)) == 0
}

Root cause:

Ignoring that floats need special handling and direct bitwise operations on them are invalid.

Key Takeaways

A number is a power of two if it has exactly one '1' bit in its binary form and is positive.

The bitwise check n & (n-1) == 0 is a fast and efficient way to verify powers of two.

Always exclude zero and negative numbers to avoid incorrect results.

This method relies on binary representation and two's complement encoding of integers.

Understanding this concept unlocks many efficient programming techniques and system optimizations.

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