Check if Number is Power of Two in DSA C++ - 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 is useful in computing because powers of two often relate to memory sizes and binary operations. The task is to write a method that tells if a given number fits this pattern.

Why it matters

Many computer systems and algorithms work best with sizes that are powers of two, like memory blocks or data chunks. Without this check, programs might waste resources or run slower. Knowing if a number is a power of two helps optimize performance and avoid errors in tasks like allocating memory or designing efficient loops.

Where it fits

Before this, you should understand basic number properties and binary numbers. After this, you can learn about bitwise operations and how they speed up calculations. This concept also leads into topics like binary trees, memory alignment, and efficient algorithm design.

Mental Model

Core Idea

A number is a power of two if it has exactly one '1' 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, it means 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 set, so 8 is a power of two.

Number: 10
Binary: 00001010

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

Build-Up - 6 Steps

1

Foundation

Understanding Powers of Two

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

Powers of two are numbers like 1, 2, 4, 8, 16, etc. Each is 2 multiplied by itself some number of times. In binary, these numbers have a single '1' followed by zeros. For example, 4 in binary is 100, and 16 is 10000.

Result

You can recognize powers of two by their binary form having only one '1'.

Understanding the binary pattern of powers of two is key to checking them efficiently.

2

Foundation

Binary Representation Basics

Concept: Learn how numbers are represented in binary and how to count bits.

Every number can be shown in binary as a series of 0s and 1s. Each position represents a power of two. Counting how many '1's appear helps identify special numbers like powers of two.

Result

You can convert numbers to binary and count their '1' bits.

Knowing binary basics allows you to spot patterns that decimal numbers hide.

3

Intermediate

Simple Loop to Count Ones

🤔Before reading on: do you think counting all '1' bits is the fastest way to check power of two? Commit to yes or no.

Concept: Use a loop to count how many '1' bits a number has to check if it is exactly one.

Write a loop that shifts the number right and counts how many times the last bit is 1. If the count is exactly one, the number is a power of two.

Result

For input 8, count is 1, so output is true. For 10, count is 2, so output is false.

This method works but is slower than bit tricks; it shows the direct connection between bit count and powers of two.

4

Intermediate

Bitwise Trick Using AND Operation

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

Concept: Use the fact that powers of two have only one '1' bit to check with a single bitwise operation.

If n is a power of two, then n & (n-1) equals zero. This happens because subtracting 1 flips the rightmost '1' bit and all bits after it. ANDing with n clears that bit, resulting in zero.

Result

For 8 (1000), 8 & 7 (0111) = 0, so true. For 10 (1010), 10 & 9 (1001) = 8 (not zero), so false.

This trick is very fast and uses the binary pattern of powers of two cleverly.

5

Advanced

Handling Edge Cases and Zero

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

Concept: Understand that zero and negative numbers are not powers of two and must be handled explicitly.

Zero has no '1' bits, so it is not a power of two. Negative numbers in two's complement have many '1's and are not powers of two. The check must exclude these cases by ensuring n > 0.

Result

Input 0 or negative numbers return false; positive powers of two return true.

Recognizing and excluding invalid inputs prevents incorrect results and bugs.

6

Expert

Using Built-in CPU Instructions

🤔Before reading on: do you think CPUs have special instructions to count bits? Commit to yes or no.

Concept: Modern CPUs have instructions to count set bits or find the lowest set bit, which can speed up power of two checks.

Functions like __builtin_popcount in GCC or _BitScanForward in MSVC count bits quickly. Using these can optimize checks in performance-critical code.

Result

Power of two checks become faster on supported hardware by using these instructions.

Leveraging hardware features can make simple checks extremely efficient in real-world applications.

Under the Hood

The key is the binary representation of numbers. Powers of two have exactly one bit set to 1. The expression n & (n-1) clears the lowest set bit. If the result is zero, it means there was only one bit set. This works because subtracting 1 flips bits from the rightmost 1 bit, changing the pattern in a predictable way.

Why designed this way?

This method was designed to use simple, fast bitwise operations that CPUs execute quickly. It avoids loops and counting bits manually, which are slower. Historically, bitwise tricks were developed to optimize low-level code and hardware interactions.

Number n in binary:    00010000 (16)
Number n-1 in binary:  00001111 (15)

Bitwise AND (n & n-1): 00000000

If result is zero, n is power of two.

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 should be included.

Reality: Zero is not a power of two; 2^0 equals 1, not zero.

Why it matters: Including zero causes incorrect results and can break algorithms relying on positive powers of two.

Quick: Does the bitwise trick n & (n-1) work for negative numbers? Commit to yes or no.

Common Belief: The bitwise trick works for all integers, including negatives.

Reality: It only works correctly for positive integers; negative numbers have different binary representations and fail the test.

Why it matters: Using the trick without checking positivity leads to wrong answers and bugs.

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

Common Belief: If a number has one or more '1' bits, it is a power of two.

Reality: Only exactly one '1' bit means power of two; more than one means it is not.

Why it matters: Misunderstanding this leads to false positives and incorrect logic.

Quick: Is the fastest way to check power of two always looping through bits? Commit to yes or no.

Common Belief: Looping through bits is the fastest and simplest method.

Reality: Bitwise tricks and CPU instructions are faster and more efficient.

Why it matters: Using slow methods can degrade performance in critical systems.

Expert Zone

1

The bitwise trick n & (n-1) only works if n is positive; zero or negative inputs must be filtered first.

2

Some CPUs provide instructions to count trailing zeros or set bits, which can be used to check powers of two even faster.

3

In some systems, powers of two are used for alignment and memory allocation, so this check is critical for low-level optimizations.

When NOT to use

Avoid using this check for floating-point numbers or non-integer types. For those, use logarithmic or other mathematical methods. Also, if the input can be negative or zero, always validate before applying the bitwise trick.

Production Patterns

In production, this check is often used in memory allocators, graphics programming, and network packet sizes. It is combined with input validation and sometimes hardware-specific optimizations for speed.

Connections

Bit Manipulation

Builds-on

Understanding power of two checks deepens knowledge of bitwise operations, which are fundamental in many algorithms.

Memory Alignment

Application

Powers of two are critical in aligning memory addresses for performance and hardware requirements.

Signal Processing

Analogous pattern

In signal processing, powers of two relate to sample sizes for efficient Fourier transforms, showing a cross-domain importance.

Common Pitfalls

#1 Not checking if number is positive before bitwise operation.

Wrong approach:

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

Correct approach:

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

Root cause:

Assuming the bitwise trick works for all integers without filtering invalid inputs.

#2 Counting bits incorrectly by checking only if number is even or odd.

Wrong approach:

bool isPowerOfTwo(int n) {
return n % 2 == 0;
}

Correct approach:

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

Root cause:

Confusing even numbers with powers of two; many even numbers are not powers of two.

#3 Including zero as a power of two.

Wrong approach:

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

Correct approach:

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

Root cause:

Not explicitly excluding zero, which passes the bitwise test incorrectly.

Key Takeaways

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

The bitwise trick n & (n-1) == 0 quickly checks this but only for positive numbers.

Always exclude zero and negative numbers before applying the bitwise check.

Understanding binary representation is essential for efficient power of two checks.

Using CPU instructions can optimize this check in performance-critical applications.

Practice

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

easy

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

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

C. It is divisible by 3.

D. It is always an odd number.

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, e.g., 4 is 100.

2. Step 2: Check other options

   Odd numbers can have many bits set; divisibility by 3 is unrelated; all bits set to 1 means numbers like 7 (111), not powers of two.

3. Final Answer:

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

4. Quick Check:

   Power of two = single 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 all bits set to 1 with power of two
• Assuming divisibility by 3 means power of two

2. Which of the following C++ expressions correctly checks if an integer n is a power of two?

easy

A. (n & (n + 1)) == 0

B. (n | (n - 1)) == 0

C. (n & (n - 1)) == 0 && n > 0

D. (n ^ (n - 1)) == 0

Solution

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

   The expression (n & (n - 1)) == 0 is true only if n has exactly one bit set, and n > 0 ensures positive numbers.

2. Step 2: Analyze other options

   (n | (n - 1)) == 0 uses OR which doesn't check power of two; (n & (n + 1)) == 0 uses n + 1 which is incorrect; (n ^ (n - 1)) == 0 uses XOR which is unrelated.

3. Final Answer:

   (n & (n - 1)) == 0 && n > 0 -> Option C

4. Quick Check:

   Bitwise AND with n-1 zero means power of two [OK]

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

Common Mistakes:

• Using OR or XOR instead of AND
• Not checking if n is positive
• Using n + 1 instead of n - 1

3. What is the output of the following C++ code?

int n = 16;
if ((n & (n - 1)) == 0 && n > 0) {
    std::cout << "Power of Two";
} else {
    std::cout << "Not Power of Two";
}

medium

A. Power of Two

B. Not Power of Two

C. Compilation Error

D. Runtime Error

Solution

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

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

2. Step 2: Check if n > 0

   16 > 0 is true, so whole condition is true and "Power of Two" is printed.

3. Final Answer:

   Power of Two -> Option A

4. Quick Check:

   16 & 15 == 0 and 16 > 0 [OK]

Hint: Check bitwise AND with n-1 equals zero for power of two [OK]

Common Mistakes:

• Miscomputing bitwise AND
• Ignoring the n > 0 check
• Confusing output strings

4. The following code is intended to check if n is a power of two, but it has a bug. What is the bug?

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

medium

A. It does not check if n is positive, so zero or negative numbers return true incorrectly.

B. The bitwise AND operator is used incorrectly; it should be OR.

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

D. The expression should be (n | (n - 1)) == 0.

Solution

1. Step 1: Analyze the expression without positivity check

   The expression returns true for n=0 because 0 & -1 = 0, which is incorrect since 0 is not a power of two.

2. Step 2: Identify missing condition

   Adding n > 0 fixes the bug by excluding zero and negative numbers.

3. Final Answer:

   It does not check if n is positive, so zero or negative numbers return true incorrectly. -> Option A

4. Quick Check:

   Check n > 0 to avoid zero/negative false positives [OK]

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

Common Mistakes:

• Ignoring zero and negative inputs
• Using OR instead of AND
• Wrong return type assumptions

5. You want to write a function that returns the smallest power of two greater than or equal to a given positive integer n. Which approach correctly achieves this in C++?

hard

A. Return n ^ (n - 1) to get the smallest power of two.

B. Return n & (n - 1) to get the smallest power of two.

C. Return n | (n - 1) to get the smallest power of two.

D. Use a loop to shift 1 left until the value is >= n.

Solution

1. Step 1: Understand the problem

   We need the smallest power of two >= n, so we start from 1 and keep doubling (shifting left) until we reach or pass n.

2. Step 2: Analyze options

   Use a loop to shift 1 left until the value is >= n. uses a loop with left shift which correctly finds the smallest power of two >= n. Options B, C, D use bitwise operations that do not produce this result.

3. Final Answer:

   Use a loop to shift 1 left until the value is >= n. -> Option D

4. Quick Check:

   Shift 1 left until >= n to find smallest power of two [OK]

Hint: Shift 1 left repeatedly until >= n to find next power of two [OK]

Common Mistakes:

• Using bitwise AND/OR/XOR incorrectly for this problem
• Not handling cases where n is already a power of two
• Assuming bitwise ops alone give next power of two