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.

Practice

1. Which of the following numbers is a power of two?

easy

A. 16

B. 18

C. 20

D. 22

Solution

1. Step 1: Understand powers of two

   Powers of two are numbers like 1, 2, 4, 8, 16, 32, etc., where each is 2 raised to an integer.

2. Step 2: Check each option

   16 = 2^4, so it is a power of two. Others like 18, 20, 22 are not powers of two.

3. Final Answer:

   16 -> Option A

4. Quick Check:

   16 = 2^4 [OK]

Hint: Only numbers with one '1' bit in binary are powers of two [OK]

Common Mistakes:

• Confusing even numbers with powers of two
• Thinking any multiple of 2 is a power of two

2. Which of the following Python expressions correctly checks if n is a power of two?

easy

A. n | (n - 1) == 0

B. n & (n - 1) == 0

C. n ^ (n - 1) == 0

D. n + (n - 1) == 0

Solution

1. Step 1: Understand bitwise AND check

   For powers of two, binary form has only one '1'. n & (n-1) clears the lowest set bit. If result is 0, n is power of two.

2. Step 2: Analyze options

   n & (n - 1) == 0 uses correct bitwise AND check. Others use OR, XOR, or addition which do not correctly check power of two.

3. Final Answer:

   n & (n - 1) == 0 -> Option B

4. Quick Check:

   Bitwise AND check is standard for power of two [OK]

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

Common Mistakes:

• Using OR or XOR instead of AND
• Forgetting to check n > 0 before this test

3. What is the output of the following code?

def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

print(is_power_of_two(32))
print(is_power_of_two(45))

medium

A. False\nFalse

B. False\nTrue

C. True\nFalse

D. True\nTrue

Solution

1. Step 1: Check 32

   32 is 2^5, so n > 0 and n & (n-1) == 0 is True.

2. Step 2: Check 45

   45 is not a power of two, so n & (n-1) != 0, returns False.

3. Final Answer:

   True\nFalse -> Option C

4. Quick Check:

   32 power of two = True, 45 not = False [OK]

Hint: Check output for known powers of two and non-powers [OK]

Common Mistakes:

• Ignoring n > 0 condition
• Assuming all even numbers are powers of two

4. Find the error in this code snippet that checks if a number is a power of two:

def check_power(n):
    if n & (n - 1) == 0:
        return True
    else:
        return False

print(check_power(0))

medium

A. Missing check for n > 0 before bitwise operation

B. No error, code works fine

C. Should use OR instead of AND

D. Return values should be strings 'True' or 'False'

Solution

1. Step 1: Analyze bitwise check

   n & (n-1) == 0 works only if n > 0. For n=0, it returns True incorrectly.

2. Step 2: Identify missing condition

   Code lacks n > 0 check, so 0 incorrectly returns True.

3. Final Answer:

   Missing check for n > 0 before bitwise operation -> Option A

4. Quick Check:

   Always check n > 0 before bitwise test [OK]

Hint: Always check n > 0 before bitwise power of two test [OK]

Common Mistakes:

• Not handling zero or negative inputs
• Using wrong bitwise operators

5. You want to filter a list to keep only numbers that are powers of two. Which code snippet correctly does this?

nums = [0, 1, 2, 3, 4, 5, 8, 16, 18]

A) result = [x for x in nums if x & (x - 1) == 0]
B) result = [x for x in nums if x > 0 and x & (x - 1) == 0]
C) result = [x for x in nums if x | (x - 1) == 0]
D) result = [x for x in nums if x > 0 or x & (x - 1) == 0]

hard

A. result = [x for x in nums if x & (x - 1) == 0]

B. result = [x for x in nums if x > 0 or x & (x - 1) == 0]

C. result = [x for x in nums if x | (x - 1) == 0]

D. result = [x for x in nums if x > 0 and x & (x - 1) == 0]

Solution

1. Step 1: Understand filtering condition

   We must check x > 0 to avoid zero or negative numbers passing the test.

2. Step 2: Analyze each option

   result = [x for x in nums if x > 0 and x & (x - 1) == 0] correctly uses x > 0 and bitwise check. result = [x for x in nums if x & (x - 1) == 0] misses x > 0, so 0 passes incorrectly. Options C and D use wrong operators or logic.

3. Final Answer:

   result = [x for x in nums if x > 0 and x & (x - 1) == 0] -> Option D

4. Quick Check:

   Filter with x > 0 and bitwise AND check [OK]

Hint: Filter with x > 0 and x & (x-1) == 0 for powers of two [OK]

Common Mistakes:

• Not filtering out zero
• Using OR instead of AND in condition
• Using bitwise OR instead of AND