Power of Four Check
Problem
Given a whole number n that fits in a signed 32-bit integer, return True if n equals 4 raised to some whole power (1, 4, 16, 64 and so on) and False otherwise. Zero and negative numbers are never powers of four. Try to answer without a loop, using only bit operations.
Examples
Input: n = 16
Output: True
Why: 16 is 4 squaredInput: n = 8
Output: False
Why: 8 is a power of two, but its single set bit is in the wrong placeInput: n = 1
Output: True
Why: edge case, 4 to the power 0 is 1Hints
0 / 3
Every power of four is also a power of two. Start by recalling how a power of two looks in binary.
A power of two has exactly one set bit, and n & (n - 1) clears it. What extra thing is true about where that bit sits for 1, 4, 16 and 64?
The single bit of a power of four always lands on an even position: 0, 2, 4 and so on. Check that n is positive, that it has one set bit, and that a mask with a 1 in every even position keeps that bit.
Solution
A power of four is a power of two whose only set bit sits at an even position, since each multiplication by four shifts that bit two places left. Subtracting one from a power of two flips its single bit and every bit below it, so n & (n - 1) is zero exactly for powers of two. The mask 0x55555555 has a 1 in every even position of a 32-bit word, so it keeps the bit of 1, 4, 16 and 64 but drops the bit of 2, 8 and 32. Time and space are O(1).
def is_power_of_four(n):
one_bit = n > 0 and (n & (n - 1)) == 0 # a power of two has a single set bit
return one_bit and (n & 0x55555555) != 0 # ...and for four it sits at an even position
print(is_power_of_four(16)) # -> True
print(is_power_of_four(8)) # -> False
print(is_power_of_four(1)) # -> True
print(is_power_of_four(0)) # -> FalseStuck on the idea rather than the code? Masks and Power of Two covers it.