Explained: One liner java solution (2ms) using bit manipulation


  • 1
    N

    Here is what I did:

    return  (num >= 1) && (Integer.bitCount(num) == 1) && ( (num & 1431655765)== num);
    

    The power of 4 is 1 (0001), 4 (0100) , 16 (1 0000), 64 (100 0000), ...
    However, the binary form of these numbers only includes one 1's bit. Using bit count we can verify if it has that one bit. But that one could be anywhere so we want to make sure that it is at the correct position. To do that, we can form a bit string that represents correct positions of all power of 4 which is this number 1431655765 (1010101010101010101010101010101).
    By performing bitwise & on a given number we should get the same number back if it is a power of 4, otherwise, we would get some number other than the given number.

    For example,

    3 & 1431655765:

    0000 0000 0000 0000 0000 0000 0000 0011
    &
    0101 0101 0101 0101 0101 0101 0101 0101

    will result into 1:
    0000 0000 0000 0000 0000 0000 0000 0001

    So, the original number changed to a different number. But, if it was power of four.

    For example, 16 = 4^2

    16 & 1431655765:

    0000 0000 0000 0000 0000 0000 0001 0000
    &
    0101 0101 0101 0101 0101 0101 0101 0101

    the result would be 16 :
    0000 0000 0000 0000 0000 0000 0001 0000

    So, it remains the same.

    Hopefully, that makes sense!
    Feel free to leave your constructive criticism in comments!


Log in to reply
 

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