231

231. Power of Two (Easy)

Given an integer n, return true if it is a power of two. Otherwise, return false.

An integer n is a power of two, if there exists an integer x such that n == 2x.

 

Example 1:

Input: n = 1
Output: true
Explanation: 20 = 1

Example 2:

Input: n = 16
Output: true
Explanation: 24 = 16

Example 3:

Input: n = 3
Output: false

 

Constraints:

• -231 <= n <= 231 - 1

 

Follow up: Could you solve it without loops/recursion?

Companies:
Amazon, Snapchat, Google

Related Topics:
Math, Bit Manipulation, Recursion

Similar Questions:

• Number of 1 Bits (Easy)
• Power of Three (Easy)
• Power of Four (Easy)

Solution 1.

// OJ: https://leetcode.com/problems/power-of-two/
// Author: github.com/lzl124631x
// Time: O(1)
// Space: O(1)
class Solution {
public:
    bool isPowerOfTwo(int n) {
        if (n <= 0) return false;
        while ((n & 1) == 0) n >>= 1;
        return n == 1;
    }
};

Solution 2.

n & -n gets the lowest bit of n. If n - (n & -n) is zero, then n is power of 2.

// OJ: https://leetcode.com/problems/power-of-two/
// Author: github.com/lzl124631x
// Time: O(1)
// Space: O(1)
class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && !(n - (n & -n));
    }
};

Solution 3.

n & (n - 1) removes the lowest bit of n. If it's zero, then n is power of 2.

// OJ: https://leetcode.com/problems/power-of-two/
// Author: github.com/lzl124631x
// Time: O(1)
// Space: O(1)
class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && !(n & (n - 1));
    }
};