Lintcode: O(1) Check Power of 2

Count Ones:
When there is only one bit is set in an integer, this int is power of 2.
So I check each bit of the Integer.
Time: O(32)
Space: O(1)
Time complexity is not good enough.

Note: take notice of negative int and zero.
e.g. 1000 0000 0000 0000 ....... (31 zeros) is an exception of counting ones method.
a quick way to find negative of a given number in two's complement representation is to invert all bits and add one. (~x + 1)

class Solution {
public:
    /*
     * @param n: An integer
     * @return: True or false
     */
    bool checkPowerOf2(int n) {
        // write your code here
        if(n <= 0) return false;
        int num = 0;
        for(int i = 0; i < 32; i++){
            if(n & 1<<i) num++;
            if(num > 1) return false;
        }
        return true;
    }
};

Decrement and compare
http://algorithm.yuanbin.me/math_and_bit_manipulation/o1_check_power_of_2.html
10 ways!
Only when there is 1 bit of n is 1, n & (n - 1) == 0; In other cases, all == 1. Of course, when x = 1000 0000(31 0s), this equation works. So x has to be positive.
Time: O(1)
Space: O(1)

class Solution {
public:
    /*
     * @param n: An integer
     * @return: True or false
     */
    bool checkPowerOf2(int n) {
        return (n > 0) && !(n & (n - 1));  //note & has lower precedence than ==
    }
};

Divide by Two:
Shift right (same with divide by two)
Time: O(32) -- worst case
Space: O(1)

class Solution {
public:
    /*
     * @param n: An integer
     * @return: True or false
     */
     //each scentence has two versions, annotation is divide by two way, the other is shift right way.
    bool checkPowerOf2(int n) {
        if(n <= 0) return false;
        while(n > 1){
            //if(n % 2 != 0) return false;
            if(n & 1) return false;
            //n = n / 2;
            n = n >> 1;
        }
        return true;
    }
};