Skip to content

Latest commit

 

History

History
 
 

231. Power of Two

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
 
 
s1.cpp
s1.cpp
 
 
s2.cpp
s2.cpp
 
 
s3.cpp
s3.cpp
 
 

README.md

231. Power of Two (Easy)

Given an integer, write a function to determine if it is a power of two.

Example 1:

Input: 1
Output: true 
Explanation: 20 = 1

Example 2:

Input: 16
Output: true
Explanation: 24 = 16

Example 3:

Input: 218
Output: false

Related Topics:
Math, Bit Manipulation

Similar Questions:

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));
    }
};