[LintCode] 142 O(1) Check Power of 2

Description
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;


思路
举几个power of 2的例子就看出来pattern了。
2¹ = 2 = 10
2² = 4 = 100
2³ = 8 = 1000
开头数是1，后面全是0。
我们再看看2n – 1的例子：
2¹ - 1 = 2 = 1
2² - 1 = 3 = 11
2³ - 1 = 7 = 111
全都是1。
所以只要n & (n – 1)为0，这个数就是2的幂次方。


Code

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