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.