Check if Number is Power of Two in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if a number is a power of two using bitwise AND.

DSA C++

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

Drag options to blanks, or click blank then click option'

An + 1

B1

Cn - 1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using n + 1 instead of n - 1

Checking only if n is positive without bitwise check

The expression n & (n - 1) clears the lowest set bit. For powers of two, this results in zero.

2fill in blank

medium

Complete the code to return false if the number is zero.

DSA C++

bool isPowerOfTwo(int n) {
    if ([1]) return false;
    return (n & (n - 1)) == 0;
}

Drag options to blanks, or click blank then click option'

An == 0

Bn < 0

Cn == 1

Dn > 0

Attempts:

3 left

💡 Hint

Common Mistakes

Checking if n == 1 instead of n == 0

Not handling zero case

Zero is not a power of two, so we return false if n is zero.

3fill in blank

hard

Fix the error in the return statement to correctly check power of two.

DSA C++

bool isPowerOfTwo(int n) {
    if (n == 0) return false;
    return (n & [1]) == 0;
}

Drag options to blanks, or click blank then click option'

An - 1

Bn + 1

C1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using n + 1 instead of n - 1

Using 1 or 0 incorrectly in bitwise AND

The correct check uses n - 1 to clear the lowest set bit.

4fill in blank

hard

Fill both blanks to complete the function that returns true if n is a power of two and false otherwise.

DSA C++

bool isPowerOfTwo(int n) {
    if ([1]) return false;
    return (n & [2]) == 0;
}

Drag options to blanks, or click blank then click option'

An <= 0

Bn == 0

Cn - 1

Dn + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Checking only for zero instead of <= 0

Using n + 1 instead of n - 1

We first check if n is less than or equal to zero, then use n & (n - 1) to check power of two.

5fill in blank

hard

Fill all three blanks to complete the function that returns true if n is a power of two, false otherwise.

DSA C++

bool isPowerOfTwo(int n) {
    if ([1]) return false;
    return ([2] & [3]) == 0;
}

Drag options to blanks, or click blank then click option'

An < 1

Bn

Cn - 1

Dn + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using n + 1 instead of n - 1

Checking n == 0 instead of n < 1

Check if n is less than 1, then use n & (n - 1) to verify if n is a power of two.

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