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


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

  • 0
    L

    neat! another way of validating 0x55555555


  • 0
    H
    This post is deleted!

  • 0
    Z

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


  • 2
    O

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


  • 2
    P

    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 ?


  • 2
    E

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


  • 1
    L

    Can you prove it in math?


  • 10
    W

    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.


  • 3

    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


  • 3
    L

    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
    

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


  • 0
    F

    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


Log in to reply
 

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