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