The problem requires you to write a function isPowerOf4 to check whether a given positive integer is a power of 4. Ideally your implementation should not contain a loop. This is a natural extension to the classical bit operations problem which asks you to write a function isPowerOf2 that checks if a positive integer is a power of 2.
Notice that a positive integer x is a power of 2 if and only if exactly one bit (except for the leading bit) is set (equals 1) in its binary representation. What happens if we do x & (x-1)?
When x = 0b111, x & (x-1) = 111 & 110 = 110.
When x = 0b101, x & (x-1) = 101 & 100 = 100.
When x = 0b100, x & (x-1) = 100 & 011 = 0.
It's not hard to see that x & (x-1) effectively turns one set bit of x to 0. So to check if positive integer x is a power of 2, we can simply compare x & (x-1) with 0:
def isPowerOf2(x):
return not x & (x-1)
Since each iteration of x & (x-1) turns off one set bit of x, a simple while loop can count the number of sets bits of a given integer in time O(k) instead of O(sizeof(int)) where k is the number of set bits of the given integer.
def numOfSetBits(x):
count = 0
while x:
x &= x - 1
count += 1
return count
Of course, isPowerOf2 can be implemented to check if the result of numOfSetBits equals 1. But this way x & (x-1) will be iterated k times instead of 1.
For a positive integer x to be a power of 4, it's necessary that x be a power of 2. What are some other requirements? Let's write down some positive integers in their binary forms:
2: 10
4: 100
8: 1000
16: 10000
Notice that in order for x to be a power of 4, its only set bit should be at the third, fifth or seventh, etc bit counting from the right. How do we check that? By creating a mask 0b01010101010101010101010101010101 which is 0x55555555 in hex.
The following snippet completes the task:
def isPowerOf4(x):
mask = 0x55555555
return isPowerOf2(x) and bool(x & mask)
isPowerOf2(x) checks that x contains exactly one set bit and bool(x & mask) checks that the correct bit is set.