---
# System prepended metadata

title: '[231. Power of Two](https://leetcode.com/problems/power-of-two/)'
tags: [leetcode]

---

---
tags: leetcode
---

# [231. Power of Two](https://leetcode.com/problems/power-of-two/)
---
# Solution 1
## The Key Idea for Solving This Coding Question
If a number `n` is a power of two, the follow statements hold.
1. $n == 2^{x}$ is true and $x$ is a non-negtive integer.
2. There is exactly one `1`-bit in the binary representation of `n`.

The key idea is to understand that for any number `n`, doing a bit-wise AND of `n` and `n−1` flips the least-significant `1`-bit of `n` to `0`.
```
n           = 01101000
n - 1       = 01100111
n & (n - 1) = 01100000
                  ^ The least significant 1-bit of n is flipped to 0.
```
## C++ Code
```cpp=
class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
}; 
```
## Time Complexity
$O(1)$
## Space Complexity
$O(1)$

<!---------->

# Solution 2
## The Key Idea for Solving This Coding Question

## C++ Code
```cpp=
class Solution {
public:
    bool isPowerOfTwo(int n) {
        if (n <= 0) {
            return false;
        }

        while (n > 1) {
            if (n % 2) {
                return false;
            }
            n = n / 2;
        }

        return true;
    }
};
```

## Time Complexity
$O(1)$
## Space Complexity
$O(1)$

<!---------->

# Solution 3
## The Key Idea for Solving This Coding Question
Recursion
## C++ Code
```cpp=
class Solution {
public:
    bool isPowerOfTwo(int n) {
        if (n <= 0) {
            return false;
        }
        if (n == 1) {
            return true;
        }
        if (n & 0x01) {
            return false;
        }
        return isPowerOfTwo(n >> 1);
    }
};
```
## Time Complexity
$O(1)$
## Space Complexity
$O(1)$
# Miscellaneous
<!--
# Test Cases
```
1
```
```
16
```
```
3
```
```
-1
```
```
-2
```
```
-3
```
```
-16
```
* Wrong Answer
```
0
```
* Runtime Error
```
-2147483648
```
-->