O(1) Check Power of 2

Easy Bit Manipulation

LintCode: http://www.lintcode.com/en/problem/o1-check-power-of-2/

Question

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 ;

Challenge

O(1) time

Thinking

• If n < 0, return false
• Use & operator to compare n and n - 1.
  Hit: 4 = ‘100’ 3 = ‘11’, 8 = ‘1000’, 7 = ‘111’ (binary value)

Solution

Java

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