Power of Two

# Power of Two ## Difficulty Easy ## Tags `bit manipulation`, `math` ## Problem Statement Given an integer `n`, return `True` if it is a power of two, `False` otherwise. An integer `n` is a power of two if there exists an integer `x` such that `n == 2^x`. ## Constraints - -2³¹ ≤ n ≤ 2³¹ - 1 - Solve in O(1) time without using loops or recursion. ## Signatures ### Python ```python def is_power_of_two(n: int) -> bool: pass ``` ### Java ```java public class Solution { public boolean is_power_of_two(int n) { return null; } } ``` ### Csharp ```csharp public class Solution { public bool is_power_of_two(int n) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: bool is_power_of_two(int n) { } }; ``` ### C ```c bool is_power_of_two(int n) { } ``` ### Ruby ```ruby def is_power_of_two(n) end ``` ### Perl ```perl sub is_power_of_two { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def is_power_of_two(n: Int): Boolean = { } } ``` ### Haskell ```haskell is_power_of_two :: ... -> ... is_power_of_two args = undefined ``` ### Clojure ```clojure (defn is_power_of_two [n] ) ``` ### Scheme ```scheme (define (is_power_of_two n) ) ``` ## Examples ### Example 1 **Input:** ``` n = 1 ``` **Output:** ``` True ``` **Explanation:** 2⁰ = 1 ### Example 2 **Input:** ``` n = 16 ``` **Output:** ``` True ``` **Explanation:** 2⁴ = 16 ### Example 3 **Input:** ``` n = 3 ``` **Output:** ``` False ``` ### Example 4 **Input:** ``` n = 0 ``` **Output:** ``` False ``` **Explanation:** There is no x where 2^x = 0. ### Example 5 **Input:** ``` n = -16 ``` **Output:** ``` False ``` **Explanation:** Negative numbers cannot be powers of two. ## Hints 1. Powers of two in binary have exactly one bit set: 1, 10, 100, 1000... 2. Consider the expression `n & (n - 1)`. 3. For a power of two: `n = 1000...0` and `n-1 = 0111...1` 4. So `n & (n - 1) = 0` for powers of two. 5. Don't forget to handle n ≤ 0.