Using O(1) time to check whether an integer n is a power of 2.

Example

For n=4, return true;

For n=5, return false;

思路：

知识点： n & (n - 1) 使得从右边数最后一个1变为0

x & (x - 1) 用于消去x最后一位的1, 比如x = 12, 那么在二进制下就是(1100)2x           = 1100x - 1       = 1011x & (x - 1) = 1000

 所以如果一个数是二的幂数，那么它肯定就只有一个1，x & (x - 1) 会使得唯一的1也变成0。同时，这个数要比0大

Note:

1) * 2 is same as << 1, so the number contains only one bit that is 1, the rest of bits are 0. 

2) n-1 sets all the bits after bit 1 from 0 to 1, and bit 1 to from 1 to 0

3) (n & (n-1)) always equal to 0 when n is power of 2

4) eg. 8(1000) &7(0111), 4(0100) &3(0011)

5) when n = 0, it suppose to return false, but it will return true.

class Solution {public:    /*     * @param n: An integer     * @return: True or false     */    bool checkPowerOf2(int n) {        // write your code here        return n > 0 && (n & (n - 1)) == 0;    }};

Here is a O(n) way:

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