💡 Problem Formulation: Detecting whether a given integer is a power of two is a common task in programming. In Python, there are several ways to achieve this. For instance, given the input number 8, the output should be True since 8 is 2 raised to the power of 3. Conversely, if the input is 5, the output should be False, as 5 is not a power of two.
Method 1: Using Logarithm and Modulo
This method calculates the base-2 logarithm of the number and checks if the result is an integer by comparing it to its integer cast. If the log value modulo 1 equals 0, then the number is a power of two.
Here’s an example:
import math
def is_power_of_two(number):
if number <= 0:
return False
log_value = math.log2(number)
return log_value.is_integer()
print(is_power_of_two(8))
print(is_power_of_two(5))Output:
True False
The math.log2() function finds the logarithm of the number with base 2, and is_integer() checks if the resulting floating-point value is equivalent to an integer.
Method 2: Using Bitwise Operations
A number that is a power of two has exactly one bit set in its binary representation. This method checks for that property by using an ‘and’ bitwise operation.
Here’s an example:
def is_power_of_two(number):
return number != 0 and (number & (number - 1)) == 0
print(is_power_of_two(8))
print(is_power_of_two(5))Output:
True False
Here, (number & (number - 1)) will be zero only if there is a single bit set in number, i.e., it is a power of two.
Method 3: Using Iteration and Division
By repeatedly dividing the number by two and checking if it eventually equals 1, we can determine if it’s a power of two. This method is straightforward but less efficient for large numbers.
Here’s an example:
def is_power_of_two(number):
if number <= 0:
return False
while number % 2 == 0:
number //= 2
return number == 1
print(is_power_of_two(8))
print(is_power_of_two(5))Output:
True False
If the number is not a power of two, the loop will eventually set the number to a value other than one, concluding the check.
Method 4: Using Recursion
A recursive function divides the number by two and calls itself until either 1 or a non-even number is reached. It is a less preferred method due to its potential to reach stack overflow on larger numbers.
Here’s an example:
def is_power_of_two(number):
if number == 1:
return True
elif number % 2 != 0 or number == 0:
return False
else:
return is_power_of_two(number/2)
print(is_power_of_two(8))
print(is_power_of_two(5))Output:
True False
This function checks the divisibility by two and recurses until it finds a non-power of two or concludes the power of two property.
Bonus One-Liner Method 5: Using Set Comprehension
The set comprehension creates a set of powers of two within a range, and the function checks the membership of the given number in the set. It can be executed with a simple one-liner code.
Here’s an example:
is_power_of_two = lambda number: number in {2**x for x in range(number.bit_length() + 1)}
print(is_power_of_two(8))
print(is_power_of_two(5))Output:
True False
Python’s set comprehension constructs the set to which the number is compared, and bit_length() is used to limit the necessary range size.
Summary/Discussion
- Method 1: Logarithm and Modulo. Precise and easy to understand. Can fail on very large numbers due to precision issues.
- Method 2: Bitwise Operations. Fast and efficient. Not as immediately intuitive as other methods.
- Method 3: Iteration and Division. Straightforward. Not very efficient for very large numbers.
- Method 4: Recursion. Elegant. Risky for large numbers because it can cause stack overflow.
- Bonus Method 5: Set Comprehension. Clever one-liner. Less performance-efficient due to creation of a set.