Check if Number is Power of Two in DSA Python

Mental Model

A number is a power of two if it has exactly one '1' bit in its binary form.

Analogy: Imagine a row of light switches where only one switch is turned on at a time; that means the number is a power of two.

Number: 8
Binary: 1 0 0 0
          ↑
Only one '1' bit is on.

Dry Run Walkthrough

Input: number = 8

Goal: Determine if 8 is a power of two

Step 1: Check if number is less than or equal to 0

number = 8

Why: Negative numbers and zero cannot be powers of two

Step 2: Calculate number & (number - 1): 8 & 7

8 in binary: 1000
7 in binary:  0111
Bitwise AND:   0000

Why: If result is 0, number has only one '1' bit

Step 3: Since result is 0, conclude number is power of two

Result = 0 means true

Why: Only powers of two have this property

Result:

8 is a power of two

Annotated Code

DSA Python

class PowerOfTwoChecker:
    @staticmethod
    def is_power_of_two(number: int) -> bool:
        if number <= 0:
            return False
        return (number & (number - 1)) == 0

if __name__ == '__main__':
    number = 8
    checker = PowerOfTwoChecker()
    if checker.is_power_of_two(number):
        print(f'{number} is a power of two')
    else:
        print(f'{number} is NOT a power of two')

if number <= 0:

Check for invalid numbers that cannot be powers of two

return (number & (number - 1)) == 0

Use bitwise AND to check if only one bit is set

Output

8 is a power of two

Complexity Analysis

Time: O(1) because bitwise operations take constant time

Space: O(1) because no extra space is used

vs Alternative: Compared to looping or dividing repeatedly, this bitwise method is much faster and simpler

Edge Cases

number = 0

Returns False because zero is not a power of two

DSA Python

if number <= 0:

number = 1

Returns True because 1 is 2^0, a power of two

DSA Python

return (number & (number - 1)) == 0

number = -4

Returns False because negative numbers cannot be powers of two

DSA Python

if number <= 0:

When to Use This Pattern

When you need to quickly check if a number is a power of two, use the bitwise AND trick because it efficiently tests the single '1' bit property.

Common Mistakes

Mistake: Checking if number % 2 == 0 repeatedly without stopping
Fix: Use the bitwise method instead of loops for constant time check

Mistake: Not handling zero or negative numbers
Fix: Add a condition to return False if number <= 0

Summary

Checks if a number has exactly one '1' bit in binary form.

Use when you want a fast way to test if a number is a power of two.

The key insight is that powers of two have only one bit set, so number & (number - 1) equals zero.

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