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.