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, first check if it is positive. Then use bitwise AND between n and n-1 to decide if it's a power of two.

Execution Sample

DSA C

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

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

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	1
6	Input number	10	9	-	-	-
7	Check if n <= 0	10	9	-	False	-
8	Calculate n & (n-1)	10	9	8	-	-
9	Check if n & (n-1) == 0	10	9	8	False	-
10	Return result	10	9	8	False	0
11	Input number	1	0	-	-	-
12	Check if n <= 0	1	0	-	False	-
13	Calculate n & (n-1)	1	0	0	-	-
14	Check if n & (n-1) == 0	1	0	0	True	-
15	Return result	1	0	0	True	1
16	Input number	0	-1	-	-	-
17	Check if n <= 0	0	-1	-	True	-
18	Return result	0	-1	-	False	0

💡 Execution stops after returning 1 (true) or 0 (false) for each input number.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
n	input	input	input	input	input
n-1	-	calculated	calculated	calculated	calculated
n & (n-1)	-	-	calculated	calculated	calculated
Return Value	-	-	-	-	0 or 1

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 execution_table rows 2 and 17.

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 and n-1 clears the only set bit, resulting in zero. See execution_table rows 3 and 13.

What happens if n is 1?

1 is a power of two (2^0). The bitwise check returns true because (1 & 0) == 0, as shown in execution_table rows 13-15.

Visual Quiz - 3 Questions

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

A 7

B 0

C 8

D 1

💡 Hint

Check the 'n & (n-1)' column in row 3 for n=8.

At which step does the function return 0 for n=10?

A Step 10

B Step 8

C Step 9

D Step 7

💡 Hint

Look at the 'Return Value' column for n=10 in the execution_table.

If n was -4, what would the check at step 2 return?

A Error

B True

C False

D Depends on n-1

💡 Hint

Step 2 checks if n <= 0 and returns false if true, see rows 2 and 17.

Concept Snapshot

Check if n is power of two:
- Return false if n <= 0
- Use bitwise: (n & (n-1)) == 0
- True means power of two
- False means not
- Works because powers of two have one set bit

Full Transcript

This concept checks if a number is a power of two using bitwise operations. First, it ensures the number is positive. Then it uses the expression (n & (n-1)) == 0. This works because powers of two have exactly one bit set in binary. Subtracting 1 flips bits after that set bit, so ANDing clears the only set bit, resulting in zero. The function returns 1 (true) if the number is a power of two, otherwise 0 (false). The execution table shows step-by-step how the input number, n-1, and the bitwise AND are calculated and checked. Key moments clarify why the initial check for positivity is needed and why the bitwise trick works. The visual quiz tests understanding of these steps.

Practice

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

easy

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

B. It is always an odd number.

C. It is divisible by 3.

D. It has all bits 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. For example, 4 is 100 in binary.

2. Step 2: Analyze the options

   It has exactly one bit set to 1 in its binary form. matches the binary property of powers of two. Options B, C, and D do not describe powers of two correctly.

3. Final Answer:

   It has exactly one bit set to 1 in its binary form. -> Option A

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
• Assuming powers of two have multiple '1' bits
• Confusing divisibility rules

2. Which of the following C code snippets correctly checks if an integer n is a power of two?

easy

A. if (n & (n - 1)) { /* not power of two */ } else { /* power of two */ }

B. if (n | (n - 1)) { /* power of two */ } else { /* not power of two */ }

C. if (n & (n + 1)) { /* power of two */ } else { /* not power of two */ }

D. if (n ^ (n - 1)) { /* power of two */ } else { /* not power of two */ }

Solution

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

   The expression n & (n - 1) is zero only if n is a power of two.

2. Step 2: Analyze each option

   if (n & (n - 1)) { /* not power of two */ } else { /* power of two */ } uses the correct expression. Options A, C, and D use incorrect bitwise operations that do not correctly check for power of two.

3. Final Answer:

   if (n & (n - 1)) { /* not power of two */ } else { /* power of two */ } -> Option A

4. Quick Check:

   n & (n-1) == 0 means power of two [OK]

Hint: Use n & (n-1) == 0 to check power of two [OK]

Common Mistakes:

• Using OR instead of AND in bitwise check
• Using n + 1 instead of n - 1
• Confusing XOR with AND

3. What is the output of the following C code snippet?

int n = 16;
if (n & (n - 1))
    printf("No\n");
else
    printf("Yes\n");

medium

A. Runtime error

B. No

C. Compilation error

D. Yes

Solution

1. Step 1: Calculate n & (n - 1) for n = 16

   16 in binary is 10000. 15 is 01111. Bitwise AND: 10000 & 01111 = 00000 (0).

2. Step 2: Check condition and output

   Since the result is 0, the else block executes, printing "Yes".

3. Final Answer:

   Yes -> Option D

4. Quick Check:

   16 & 15 = 0 means power of two [OK]

Hint: If n & (n-1) is zero, print Yes [OK]

Common Mistakes:

• Miscomputing bitwise AND
• Confusing output branches
• Assuming non-zero means power of two

4. Identify the error in the following C code that checks if n is a power of two:

int n = 10;
if (n & n - 1 == 0)
    printf("Power of two\n");
else
    printf("Not power of two\n");

medium

A. No error, code is correct

B. Missing parentheses around (n - 1) in bitwise operation

C. Incorrect variable initialization

D. Using bitwise OR instead of AND

Solution

1. Step 1: Analyze operator precedence in condition

   In C, == has higher precedence than &, so expression is evaluated as n & ((n - 1) == 0) which is incorrect.

2. Step 2: Correct the expression with parentheses

   Use (n & (n - 1)) == 0 to ensure correct evaluation.

3. Final Answer:

   Missing parentheses around (n - 1) in bitwise operation -> Option B

4. Quick Check:

   Use parentheses to fix precedence [OK]

Hint: Add parentheses: (n & (n - 1)) == 0 [OK]

Common Mistakes:

• Ignoring operator precedence
• Not using parentheses in bitwise expressions
• Assuming code compiles correctly without fix

5. You want to write a function in C that returns 1 if a number n is a power of two and 0 otherwise. Which of the following implementations correctly handles the case when n is zero or negative?

hard

A. int isPowerOfTwo(int n) { return n >= 0 && (n & (n + 1)) == 0; }

B. int isPowerOfTwo(int n) { return (n & (n - 1)) == 0; }

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

D. int isPowerOfTwo(int n) { return n != 0 || (n & (n - 1)) == 0; }

Solution

1. Step 1: Consider zero and negative inputs

   Zero and negative numbers are not powers of two, so the function must exclude them.

2. Step 2: Analyze each function

   int isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; } checks if n > 0 and then applies the bitwise check correctly. int isPowerOfTwo(int n) { return (n & (n - 1)) == 0; } misses the positive check. Options A, B, and D use incorrect logic or operators.

3. Final Answer:

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

4. Quick Check:

   Check n > 0 before bitwise test [OK]

Hint: Check n > 0 before bitwise test to avoid errors [OK]

Common Mistakes:

• Not handling zero or negative inputs
• Using wrong bitwise operators
• Using OR instead of AND in conditions