C 1 line solution using bit-tricks with &


  • 7
    bool isPowerOfFour(int n) {
            return n>0 && (n&(n-1))==0 && (n&0x55555555);
    }
    

  • 0
    B

    awesome code!


  • 0
    G

    So amazing!!!!!!!!!!!!


  • 0
    L

    if (n > 0): then:
    if (n&(n-1)) means that n is power of 2, and there is only one bit whose value is 1 in 32 bits.
    0x5 == (0101)B, so 0x55555555 means that every odd bit is 1.
    if (n&0x55555555) means that the only bit whose value is 1 is odd bit, then and the number of 0 bits behind 1 bit is even. So n is power of 4.
    All by observation:
    4 == 100, the number of 0 bits is multiple is even, so true
    8 == 1000, 0 bits odd, not true
    16 == 10000, even, true
    and so on...


  • 0
    C

    It can be simplifed to (n&(n-1)) == 0 && (n&0x55555555), i.e., there's no need to bitwise-and with n > 0 since n&0x55555555 == 0 for all n <= 0.

    Indeed, in both one's and two's complement representations, if n < 0 then its highest order bit is 1 but the highest order bit of 0x55555555 is 0, thus n&0x55555555 == 0. The same holds for n = -0 in one's complement representation. Finally if n = +0 then all bits are 0 and again n&0x55555555 == 0.


Log in to reply
 

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