https://leetcode.com/problems/power-of-four

How we can check that number is power of 4? Straightforward algorithm is to try to divide it by 4 and check if we have 1 after several divisions, but complexity of this approach will be O(log n). There is smarter way. To check that number is power of 4, we need to check 3 conditions:

  1. Number is positive.
  2. Number is power of 2.
  3. This power of 2 is even power.

First condition is trivial. For the second condition we can use x&(x-1) trick, which removes the last significant bit of binary representation, for example 11010 & 11001 = 11000. Number is power of two if it have only one significant bit, that is after this operation it must be equal to zero.

The last part is a bit tricky. Hopefully if reached this step, we already know, that number is a power of 2, so we have not a lot of options left: 1, 10, 100, 1000, … How we can distinguish one half of them (odd powers) from another half? The trick is to use binary mask m = 1010101010101010101010101010101. For even powers of 2 we have for example m&100 = 100, if we use odd power, for example m&1000 = 0.

Complexity: both time and space is O(1), and this is honest O(1), not O(32) or O(16).

class Solution:
    def isPowerOfFour(self, num):
        return num > 0 and num & (num-1) == 0 and 0b1010101010101010101010101010101 & num == num

If you like the solution, you can upvote it on leetcode discussion section: Problem 0342