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 if (n & (n-1)) == 0?

Yes→Return True

No↓

Return False

Start with the number n, if n is positive, check if n & (n-1) equals zero. If yes, n is a power of two; otherwise, it is not.

Execution Sample

DSA C#

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

This code checks if a number n is a power of two by using bitwise AND between n and n-1.

Execution Table

Step	Operation	n	n-1	n & (n-1)	Result	Return Value
1	Input number	8	7	-	-	-
2	Check if n <= 0	8	7	-	False	-
3	Calculate n & (n-1)	8	7	0	-	-
4	Check if (n & (n-1)) == 0	8	7	0	True	-
5	Return result	8	7	0	True	True

💡 Returns True because 8 & 7 equals 0, confirming 8 is a power of two.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
n	-	8	8	8	8
n-1	-	-	7	7	7
n & (n-1)	-	-	-	0	0
Return Value	-	-	-	-	True

Key Moments - 3 Insights

Why do we check if n <= 0 before the bitwise operation?

Because powers of two are positive numbers. Checking n <= 0 first avoids incorrect results for zero or negative numbers, as shown in step 2 of the execution_table.

Why does (n & (n-1)) == 0 mean n is a power of two?

Because powers of two have only one '1' bit in binary. Subtracting 1 flips all bits after that '1'. ANDing n with n-1 clears the lowest set bit. If the result is zero, only one bit was set, confirming a power of two (see step 3 and 4).

What happens if n is not a power of two?

The bitwise AND will not be zero, so the function returns false. This is implied by the flow in the concept_flow and the final return in step 5.

Visual Quiz - 3 Questions

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

A 7

B 0

C 8

D 1

💡 Hint

Check the 'n & (n-1)' column at step 3 in the execution_table.

At which step does the function decide to return True?

A Step 2

B Step 4

C Step 5

D Step 3

💡 Hint

Look at the 'Return Value' column and the 'Return result' operation in the execution_table.

If n was 10 instead of 8, what would be the result of (n & (n-1))?

A 2

B 0

C 8

D 10

💡 Hint

Calculate 10 & 9 in binary or imagine the bitwise AND operation similar to step 3.

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
- Efficient and fast bitwise check

Full Transcript

This concept checks if a number is a power of two by using a bitwise trick. First, it ensures the number is positive. Then it performs a bitwise AND between the number and one less than the number. If the result is zero, it means the number has only one bit set, so it is a power of two. The execution table shows step-by-step how the number 8 is checked and confirmed as a power of two. Key moments clarify why the initial check for positivity is needed and why the bitwise operation works. The quiz tests understanding of the bitwise results and return steps.

Practice

1. Which of the following statements correctly describes a number that is a power of two?

easy

A. It is divisible by 3.

B. It is always an odd number.

C. It has all bits set to 1 in its binary form.

D. It has exactly one bit set to 1 in its binary form.

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 for correctness

   Odd numbers and divisibility by 3 do not define powers of two. Having 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 D

4. Quick Check:

   Power of two = one '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. return (n & (n + 1)) == 0;

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

C. return (n & (n - 1)) == 0 && n > 0;

D. return (n ^ (n - 1)) == 0;

Solution

1. Step 1: Understand bitwise check for power of two

   For a power of two, n & (n - 1) clears the only set bit, resulting in 0. Also, n must be positive.

2. Step 2: Analyze other expressions

   Other options use incorrect bitwise operations that do not correctly identify powers of two.

3. Final Answer:

   return (n & (n - 1)) == 0 && n > 0; -> Option C

4. Quick Check:

   Bitwise AND with n-1 equals 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;
bool result = (n & (n - 1)) == 0 && n > 0;
Console.WriteLine(result);

medium

A. True

B. False

C. Compile-time error

D. Runtime exception

Solution

1. Step 1: Calculate bitwise AND of n and n-1

   For n=16 (binary 10000), n-1=15 (binary 01111). Bitwise AND is 0.

2. Step 2: Check if result is zero and n is positive

   Since (n & (n - 1)) == 0 and n > 0, the expression is true.

3. Final Answer:

   True -> Option A

4. Quick Check:

   16 is power of two, so output is True [OK]

Hint: If n & (n-1) == 0 and n>0, output is True [OK]

Common Mistakes:

• Miscomputing bitwise AND
• Ignoring n > 0 condition
• Confusing True and False outputs

4. The following code is intended to check if n is a power of two. What is the error?

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

medium

A. The expression should be (n | (n - 1)) == 0 instead.

B. It does not check if n is positive, so zero or negative numbers return true incorrectly.

C. The function should return an integer, not a boolean.

D. The bitwise AND operator is used incorrectly; it should be OR.

Solution

1. Step 1: Analyze the bitwise condition

   The expression (n & (n - 1)) == 0 is true for powers of two but also for zero.

2. Step 2: Identify missing condition

   Zero and negative numbers are not powers of two, so the function must check n > 0.

3. Final Answer:

   It does not check if n is positive, so zero or negative numbers return true incorrectly. -> Option B

4. Quick Check:

   Check n > 0 to avoid false positives [OK]

Hint: Always check n > 0 when using bitwise power of two check [OK]

Common Mistakes:

• Omitting n > 0 check
• Using wrong bitwise operator
• Returning wrong data type

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. Use a loop doubling a variable starting at 1 until it is >= n.

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. Return n ^ (n - 1) to get the smallest power of two.

Solution

1. Step 1: Understand the problem requirement

   We need the smallest power of two >= n, so start from 1 and double until reaching or exceeding n.

2. Step 2: Analyze other options

   Bitwise operations like AND, OR, XOR with n-1 do not produce the smallest power of two >= n.

3. Final Answer:

   Use a loop doubling a variable starting at 1 until it is >= n. -> Option A

4. Quick Check:

   Doubling loop finds smallest power of two >= n [OK]

Hint: Double from 1 until >= n to find smallest power of two [OK]

Common Mistakes:

• Using bitwise AND/OR/XOR incorrectly for this task
• Not handling n less than 1
• Assuming bitwise ops give next power of two