C bitwise solution, with explanation in comments


  • 0
    bool isPowerOfTwo(int x) {
        // x = 4
        // 0000 0000 0000 0000 0000 0000 0000 0100
        // x = 8
        // 0000 0000 0000 0000 0000 0000 0000 1000
        // ...
        // We see that if x is power of 2, there will be only 1 at MSB
        // Also, x - 1 gives all ones after the previous
        // 1 digit: e.g. x = 8 - 1 ==> 0000 0000 ... 0111
        // So, x & (x - 1) is 0 only for x is power of 2
        // For zero, just return 1;
        // For negative number, use ~0 xor it to turn it
        // positive; e.g. x = -4
        // 1111 1111 1111 1111 1111 1111 1111 1100 ^
        // 1111 1111 1111 1111 1111 1111 1111 1111
        // 0000 0000 0000 0000 0000 0000 0000 0011 --> operand for &
        int sign_x = x >> 31;
        int minus = ((~0) ^ sign_x);
        return !((x & (x + minus)) + !x);
    }
    

Log in to reply
 

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