# Simple C++ O(1) solution without 0x55555555

• ``````class Solution {
public:
bool isPowerOfFour(int num) {
return ((num-1)&num)==0 && (num-1)%3==0;
}
};``````

• neat! another way of validating 0x55555555

• This post is deleted!

• could you tell me the meaning of "(num-1)&num", I can't understand

• 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).

• hi, ((num-1)&num)==0 stand for the Power of two. and (num-1)%3==0 stand for 3n + 1, but why ((num-1)&num)==0 && (num-1)%3==0 is the PowerOfFour ?

• For all power of four integers n, (n-1) is always divisible by 3. For example, 0,3,15,63......

• Can you prove it in math?

• 4^x-1=(2^x-1)(2^x+1). And 2^x mod 3 is not 0. So either 2^x-1 or 2^x +1 must be 0.

• 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 (num-1), for a power of 2, there would be ANY number of "1" in serial in the end;
While, after (num-1), 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^m-1=3+(3<<2)+(3<<4)+...+(3<<2m)=3+3*(4^1)+3*(4^2)+...+3*(4^m)
so (4^m-1)%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&(num-1)==0 ensures num is a power of 2. And (num-1)%3==0 ensures (num-1) is a serial1(2m), that is num is a power of 4

prove done

• We can use induction to prove (num-1)%3==0.

``````1. (pow(4,1)-1)%3==0;
2.Suppose (pow(4,k)-1)%3==0, we can prove
(pow(4,k+1)-1)%3
=(4*(pow(4,k)-1)+4-1)%3==0
``````

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

`serial1(2k+1) == 2^(2k+1)-1 == 3 + (3<<2) + (3<<4) +...+ (3<<(2*(k-1))) + (1<<2k) == 3*(4^0) + 3*(4^1) + 3*(4^2) +...+ 3*(4^(k-1)) + (1<<2k);`

• `2^2k` is power of 4, `2^(2k+1)` is power of 2 but not 4. We can use mathematical induction to prove that `2^2k mod 3 == 1` and `2^(2k+1) mod 3 == 2`

• rial1(2k) == 4^k-1 == 3 + (3<<2) + (3<<4) +...+ (3<<(2*(k-1))) == 3*(4^0) + 3*(4^1) + 3*(4^2) +...+ 3*(4^(k-1));

Thanks!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.