Why Check if Number is Power of Two in DSA C++?

The Big Idea

Discover a simple trick that turns a slow, boring task into a lightning-fast check!

The Scenario

Imagine you have a 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 repeatedly and checking if you end up with 1. This can take a lot of time if the list is long.

The Problem

Manually dividing numbers by 2 over and over is slow and easy to mess up. It's hard to keep track of all the divisions, especially for big numbers. This makes the process tiring and error-prone.

The Solution

Using a simple trick with binary numbers, we can quickly check if a number is a power of two. This method uses a fast operation that computers do easily, making the check instant and reliable.

Before vs After

✗ Before

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

✓ After

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

What It Enables

This lets you instantly know if a number is a power of two, enabling faster decisions in programs that need this check often.

Real Life Example

In computer graphics, textures often need to have sizes that are powers of two for better performance. Quickly checking this helps the program run smoothly.

Key Takeaways

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

Bitwise operations provide a fast and simple solution.

This check is useful in many computer applications like graphics and memory management.

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