Check if Number is Power of Two in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of power of two check using bitwise AND

What is the output of the following C++ code snippet?

DSA C++

int n = 16;
bool isPowerOfTwo = (n & (n - 1)) == 0 && n != 0;
std::cout << (isPowerOfTwo ? "Yes" : "No") << std::endl;

A "Yes"

B "No"

C Runtime error

D Compilation error

💡 Hint

Remember that powers of two have only one bit set in binary.

The expression n & (n - 1) clears the lowest set bit. For powers of two, this results in zero. Since 16 is a power of two, the output is "Yes".

❓ Predict Output

intermediate

Output when input is zero

What does the following code print when n = 0?

DSA C++

int n = 0;
bool isPowerOfTwo = (n & (n - 1)) == 0 && n != 0;
std::cout << (isPowerOfTwo ? "Yes" : "No") << std::endl;

A Compilation error

B Runtime error

C "Yes"

D "No"

💡 Hint

Zero is not a power of two.

The condition n != 0 ensures zero is excluded. So the output is "No".

🔧 Debug

advanced

Identify the error in power of two check

What error does this code produce?

DSA C++

int n = 8;
bool isPowerOfTwo = (n & n - 1) == 0;
std::cout << (isPowerOfTwo ? "Yes" : "No") << std::endl;

A Logical error producing wrong output

B Outputs "Yes"

C Compilation error

D Outputs "No"

💡 Hint

Check operator precedence in the expression.

The expression (n & n - 1) is parsed as (n & n) - 1 due to operator precedence, which is incorrect. This causes wrong output.

🧠 Conceptual

advanced

Why does (n & (n-1)) == 0 check power of two?

Which explanation correctly describes why (n & (n-1)) == 0 checks if n is a power of two?

A It checks if n is zero.

B It counts the number of set bits in n.

C It clears the lowest set bit; if result is zero, only one bit was set.

D It shifts bits to the right until n becomes zero.

💡 Hint

Think about what happens to the binary bits when subtracting 1.

Subtracting 1 flips the lowest set bit and all bits after it. ANDing with n clears that bit. If the result is zero, n had only one set bit, meaning it is a power of two.

🚀 Application

expert

Count how many numbers are powers of two in a list

Given the list {3, 4, 6, 8, 16, 18}, how many numbers are powers of two?

A 5

B 3

C 4

D 2

💡 Hint

Check each number with the bitwise power of two test.

4, 8, and 16 are powers of two. So the count is 3.

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