class Solution {
public:
bool isPowerOfFour(int num) {
return ((num1)&num)==0 && (num1)%3==0;
}
};
Simple C++ O(1) solution without 0x55555555

It means that binary representation of 4, 16 etc. will be 4 = 0100, 16 = 00010000. If you subtract 1 from 4, 16, .... you will get something like 0011 for 4 and 00001111 for 16. Finally when you make & you check that all the right bits is zero(it is one of the properties of numbers that is power of four).

in 32 bits format, the right side of a power of 2 would be "1" followed by any number of "0"
while the right side of a power of 4 would be "1" followed by EVEN number of "0"
(for example: 2^3="0000 0000 0000 1000"; 4^2="0000 0000 0001 0000")So, after (num1), for a power of 2, there would be ANY number of "1" in serial in the end;
While, after (num1), for a power of 4, there would be EVEN number of "1" in serial in the end.Denote a number with m of "1" in serial in the end as "serial1(m)".
we have:
serial1(2m)=4^m1=3+(3<<2)+(3<<4)+...+(3<<2m)=3+3*(4^1)+3*(4^2)+...+3*(4^m)
so (4^m1)%3==0 for any m.
While for those that are a power of 2 but not a power of 4, we have:
serial1(2m+1)=3+(3<<2)+(3<<4)+...+(3<<2m)+(1<<(2m+1))=3+3*(4^1)+3*(4^2)+...+3*(4^m)+1*(2^(2m+1))
So serial1(2m+1)%3=1*(2^(2m+1))%3 !=0 for all m.So num&(num1)==0 ensures num is a power of 2. And (num1)%3==0 ensures (num1) is a serial1(2m), that is num is a power of 4
prove done

@hua24
Thank you for the detail explanation!
You have some minor error of the equations:
serial1(2k) == 4^k1 == 3 + (3<<2) + (3<<4) +...+ (3<<(2*(k1))) == 3*(4^0) + 3*(4^1) + 3*(4^2) +...+ 3*(4^(k1));
serial1(2k+1) == 2^(2k+1)1 == 3 + (3<<2) + (3<<4) +...+ (3<<(2*(k1))) + (1<<2k) == 3*(4^0) + 3*(4^1) + 3*(4^2) +...+ 3*(4^(k1)) + (1<<2k);

@mmyang said in Simple C++ O(1) solution without 0x55555555:
rial1(2k) == 4^k1 == 3 + (3<<2) + (3<<4) +...+ (3<<(2*(k1))) == 3*(4^0) + 3*(4^1) + 3*(4^2) +...+ 3*(4^(k1));
Thanks!