Check if Number is Power of Two in DSA C++ - Execution Trace

Concept Flow - Check if Number is Power of Two

Start with number n

↓

Check if n <= 0?

Yes→Return False

No↓

Check n & (n-1) == 0?

Yes→Return True

No↓

Return False

Start with the number, first check if it is positive. Then use bitwise AND between n and n-1 to decide if it is a power of two.

Execution Sample

DSA C++

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

This code checks if a number is a power of two using bitwise operations.

Execution Table

Step	Operation	Number n	Expression n & (n-1)	Result	Return Value
1	Check if n <= 0	16	N/A	False (16 > 0)	Continue
2	Calculate n-1	16	15	N/A	Continue
3	Calculate n & (n-1)	16	15	16 & 15 = 0b10000 & 0b01111 = 0b00000	0
4	Check if (n & (n-1)) == 0	16	0	True	Return True

💡 Returns True because 16 & 15 == 0, so 16 is a power of two.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
n	16	16	16	16	16
n-1	N/A	N/A	15	15	15
n & (n-1)	N/A	N/A	N/A	0	0

Key Moments - 3 Insights

Why do we check if n <= 0 first?

Because powers of two are positive numbers. The check stops negative numbers and zero early, as shown in step 1 of the execution_table.

Why does n & (n-1) equal zero only for powers of two?

Because powers of two have exactly one '1' bit in binary. Subtracting 1 flips that bit and all lower bits, so ANDing them results in zero. This is shown in step 3 and 4.

What happens if n is not a power of two?

Then n & (n-1) will not be zero, so the function returns false. This is the else case after step 4.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of n & (n-1) at step 3?

A 15

B 1

C 0

D 16

💡 Hint

Check the 'Expression n & (n-1)' and 'Result' columns at step 3.

At which step does the function decide to return True?

A Step 1

B Step 4

C Step 3

D Step 2

💡 Hint

Look at the 'Return Value' column to see when True is returned.

If n was 18 instead of 16, how would the value of n & (n-1) change at step 3?

A 1

B 0

C 16

D 18

💡 Hint

Calculate 18 & 17 in binary and check the result.

Concept Snapshot

Check if number n is power of two:
- Return false if n <= 0
- Use bitwise AND: (n & (n-1)) == 0 means power of two
- Only one bit set in powers of two
- Fast and efficient check using bits

Full Transcript

This concept checks if a number is a power of two using bitwise operations. First, it verifies the number is positive. Then it uses the fact that powers of two have only one bit set in binary. By performing a bitwise AND between the number and one less than the number, the result is zero only if the number is a power of two. The code returns true in that case, otherwise false. The execution table shows step-by-step how the number and expressions change, confirming the logic.

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