💡 Problem Formulation: Given an integer n, the challenge is to check whether it is a power of 4. The expected output is a boolean value—True if n is indeed a power of 4, such as 4^2=16, and False otherwise, e.g., 15 which is not a power of 4.
Method 1: Iterative Division
This method repeatedly divides the number by 4 to see if it reduces to 1, which indicates that it is a power of 4. The function keeps dividing the number as long as it’s divisible by 4 and positive. If it reaches 1, the input is a power of 4.
Here’s an example:
def is_power_of_four(n):
if n <= 0:
return False
while n % 4 == 0:
n /= 4
return n == 1
print(is_power_of_four(16))
print(is_power_of_four(15))Output:
True False
This code defines a function is_power_of_four() that returns True if the number is a power of 4 and False if not. It uses a while loop to continuously divide the number by 4 until it’s no longer possible, checking in the end if the resulting number is 1.
Method 2: Logarithmic Check
Using logarithms, you can determine if a number is a power of 4 by checking if the logarithm base 4 of the number is an integer. This mathematically sound technique is efficient but might suffer from floating-point precision issues.
Here’s an example:
import math
def is_power_of_four(n):
if n <= 0:
return False
return math.log(n, 4).is_integer()
print(is_power_of_four(64))
print(is_power_of_four(10))Output:
True False
Here, the is_power_of_four() function computes the base 4 logarithm of n and checks if it’s an integer using is_integer(). This is a neat and computationally efficient way to solve the problem assuming that precision isn’t lost in the process.
Method 3: Binary Representation Check
Since powers of 4 in binary always have a single ‘1’ followed by an even number of zeros, this method inspects the number’s binary representation. It fits perfectly for systems-related tasks where binary manipulations are common.
Here’s an example:
def is_power_of_four(n):
return n != 0 and n & (n - 1) == 0 and n & 0xAAAAAAAA == 0
print(is_power_of_four(256))
print(is_power_of_four(255))Output:
True False
This function is_power_of_four() does a bitwise AND with n and n-1 to check if n is a power of 2 and then checks that this power of 2 is a power of 4 by anding with 0xAAAAAAAA, which is a hexadecimal number with all the bits in places that are powers of 4 set to 0.
Method 4: Mathematical Property
There is a mathematical property stating that for a number to be a power of 4, it must be a power of 2, and its square root must also be a power of 2. This method is straightforward and easily understandable.
Here’s an example:
def is_power_of_two(n):
return n > 0 and (n & (n - 1)) == 0
def is_power_of_four(n):
return is_power_of_two(n) and is_power_of_two(int(n**0.5))
print(is_power_of_four(256))
print(is_power_of_four(14))Output:
True False
The is_power_of_four() function relies on an auxiliary function is_power_of_two() to confirm whether the number is a power of 2. Then, it checks whether the square root of the number (also must be a power of 2) to affirm it’s a power of 4.
Bonus One-Liner Method 5: Use of Set
By precomputing a set of powers of 4 within the range of expected inputs, you can perform an extremely fast membership check using set lookup. This is particularly effective for small ranges.
Here’s an example:
powers_of_four = {4**i for i in range(16)}
def is_power_of_four(n):
return n in powers_of_four
print(is_power_of_four(1024))
print(is_power_of_four(1023))Output:
True False
This example uses a set comprehension to create a set of powers of 4. The function is_power_of_four() then simply checks if the given number n is within this set, providing instant results.
Summary/Discussion
- Method 1: Iterative Division. Simple and easy to understand. It can become less efficient for very large numbers due to the number of iterations needed.
- Method 2: Logarithmic Check. Efficient and concise. Might be inaccurate for very large numbers or numbers close to the floating-point precision limit.
- Method 3: Binary Representation Check. Fast and efficient for integers. Highly technical and not as straightforward for those unfamiliar with bitwise operations.
- Method 4: Mathematical Property. Relies on knowledge of powers of 2. Two separate checks may be considered less efficient than necessary.
- Bonus Method 5: Use of Set. Extremely fast for known, limited ranges. Not scalable for very large values or when the range of inputs is not predetermined.