Check if Number is Power of Two in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does it mean for a number to be a power of two?

A number is a power of two if it can be written as 2 raised to an integer exponent, like 1, 2, 4, 8, 16, etc.

intermediate

Which bitwise operation can quickly check if a number is a power of two?

Using (n & (n - 1)) == 0 checks if n is a power of two, because powers of two have only one '1' bit in binary.

beginner

Why must we check that the number is greater than zero when checking for power of two?

Because zero or negative numbers are not powers of two, and the bitwise trick works only for positive numbers.

beginner

What is the binary pattern of a power of two number?

It has exactly one '1' bit and all other bits are '0'. For example, 8 in binary is 1000.

beginner

Show the C++ code snippet to check if an integer n is a power of two.

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

Which of these numbers is NOT a power of two?

A 16

B 32

C 18

D 64

18 is not a power of two because it cannot be written as 2^k for any integer k.

What does the expression (n & (n - 1)) == 0 check for?

A If n is a power of two

B If n is odd

C If n is zero

D If n is negative

This expression is true only when n is a power of two (and n > 0).

Why do we check n > 0 before using the bitwise trick?

A Because zero and negative numbers are powers of two

B Because the bitwise trick only works for positive numbers

C Because negative numbers have all bits set

D Because zero is a power of two

The bitwise trick works only for positive numbers; zero and negatives are not powers of two.

What is the binary form of 8, a power of two?

A 0011

B 1111

C 0101

D 1000

8 in binary is 1000, which has exactly one '1' bit.

Which of these C++ code snippets correctly checks if n is a power of two?

A return n > 0 && (n & (n - 1)) == 0;

B return n == 0 || (n & (n - 1)) == 0;

C return (n & (n + 1)) == 0;

D return n > 0 && (n | (n - 1)) == 0;

Option A is the correct and standard way to check for power of two.

Explain how to check if a number is a power of two using bitwise operations.

Think about how powers of two look in binary and how subtracting 1 changes the bits.

Write a simple C++ function to check if an integer is a power of two and explain each step.

Use the bitwise trick and remember to exclude zero and negatives.

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