Check if Number is Power of Two in DSA Python - 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, reject non-positive numbers, then use bitwise check to decide if it's a power of two.

Execution Sample

DSA Python

def is_power_of_two(n):
    if n <= 0:
        return False
    return (n & (n - 1)) == 0

This function returns True if n is a power of two, otherwise False.

Execution Table

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

💡 Function returns True if bitwise AND is zero and n > 0, else False.

Variable Tracker

Variable	Start	After Step 3 (n-1)	After Step 4 (n & (n-1))	Final
n	Input value	8 / 10	8 / 10	8 / 10
n-1	-	7 / 9	7 / 9	7 / 9
n & (n-1)	-	-	0 / 8	0 / 8
Return Value	-	-	-	True / False

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

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 that bit and all lower bits, so AND becomes zero. See execution_table rows 4 and 10.

What happens if n is not a power of two?

The bitwise AND is not zero, so the function returns False, as in execution_table rows 10-12.

Visual Quiz - 3 Questions

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

A 8

B 0

C 7

D 1

💡 Hint

Check the 'Bitwise AND (n & (n-1))' column at step 4 for n=8.

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

A Step 12

B Step 11

C Step 8

D Step 10

💡 Hint

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

If n was 1, what would (n & (n-1)) equal and what would the function return?

A 0 and False

B 1 and False

C 0 and True

D 1 and True

💡 Hint

Recall that 1 in binary is 1, and 1-1=0, so AND is 0; function returns True.

Concept Snapshot

Check if n <= 0: return False
Else return (n & (n-1)) == 0
Only powers of two have one '1' bit
Bitwise AND clears lowest set bit
If result is zero, n is power of two

Full Transcript

This concept checks if a number is a power of two using bitwise operations. First, it rejects non-positive numbers because powers of two are positive. Then it uses the fact that powers of two have exactly one bit set in binary. By computing n & (n-1), it clears the lowest set bit. If the result is zero, it means there was only one bit set, so n is a power of two. The execution table shows step-by-step how the function processes inputs 8 and 10, returning True for 8 and False for 10. The variable tracker follows the values of n, n-1, and the bitwise AND operation. Key moments clarify why the initial check is needed and why the bitwise trick works. The quiz tests understanding of these steps.