💡 Problem Formulation: We often encounter situations in coding where we need to determine if a given integer is a power of two. This check can be useful in various contexts, such as bit manipulation, optimization problems, or while working with binary trees. To illustrate, if an input is 8, the desired output would be True as 8 is 2 to the power of 3. Conversely, if the input is 7, the output should be False.
Method 1: Iterative Division
This method involves continuously dividing the number by two, checking if it’s divisible without a remainder. If we eventually reach 1, the original number is a power of two. The function stops early if a division has a remainder, returning False.
Here’s an example:
def is_power_of_two(n):
if n <= 0:
return False
while n % 2 == 0:
n //= 2
return n == 1
print(is_power_of_two(32))
print(is_power_of_two(7))The output will be:
True False
This method effectively reduces the number until it can be determined whether it is a power of two. It is straightforward but can be slower for large numbers since it performs multiple division operations.
Method 2: Bitwise AND with the Preceding Number
Using bitwise operations, we can determine if a number is a power of two by checking if it has exactly one bit set to 1 (since powers of two are represented as such in binary). Thus, we perform an AND operation between the number and its predecessor; if the result is 0, the number is a power of two.
Here’s an example:
def is_power_of_two(n):
return n > 0 and (n & (n - 1)) == 0
print(is_power_of_two(8))
print(is_power_of_two(14))The output will be:
True False
This method is very efficient since it completes in constant time regardless of the size of the number, making it suitable for large integers.
Method 3: Logarithmic Check
A mathematical approach involves using logarithms. We use the base-2 logarithm of the number and check if the result is an integer. If it is, the number is a power of two. This method relies on the property that logarithms can revert exponentiation.
Here’s an example:
import math
def is_power_of_two(n):
if n <= 0:
return False
log_result = math.log(n, 2)
return log_result.is_integer()
print(is_power_of_two(256))
print(is_power_of_two(245))The output will be:
True False
This method is precise and works well, but may suffer from floating-point representation errors for very large numbers and might not be as fast as bitwise operations.
Method 4: Power of Two Set
Another way to check if a number is a power of two is to precalculate a set of powers of two within a range and simply check the membership of the given number in that set. It’s very quick for numbers within the precalculated range.
Here’s an example:
powers_of_two = {1 << exp for exp in range(0, 31)} # Assuming 32-bit integer
def is_power_of_two(n):
return n in powers_of_two
print(is_power_of_two(1024))
print(is_power_of_two(1023))The output will be:
True False
While this is a fast method for a fixed range of numbers, it is not practical for very large numbers beyond the precalculated range and consumes memory for the set.
Bonus One-Liner Method 5: Using Bit Counting
A fast and clever one-liner uses the built-in Python function bin() to check if the binary representation of the number contains only one ‘1’. It’s a concise version of the bitwise AND method.
Here’s an example:
is_power_of_two = lambda n: n > 0 and bin(n).count('1') == 1
print(is_power_of_two(64))
print(is_power_of_two(65))The output will be:
True False
This one-liner is readable and efficient for small to moderately large numbers, leveraging Python’s built-in capabilities.
Summary/Discussion
- Method 1: Iterative Division. Easy to understand. Slower for large numbers due to multiple divisions.
- Method 2: Bitwise AND. Extremely fast and efficient. Operates in constant time, best for performance-critical applications.
- Method 3: Logarithmic Check. Mathematically elegant. Can suffer from floating-point errors with very large numbers and is not as fast as bitwise methods.
- Method 4: Power of Two Set. Quick for numbers in the precalculated range. Consumes memory for the set and not suitable for numbers beyond this range.
- Bonus Method 5: One-liner Using Bit Counting. Compact and Pythonic, leveraging built-in functions. Efficiency may decrease with very large numbers.