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

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

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

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

-->