Welcome to Subscribe On Youtube

231. Power of Two

Description

Given an integer n, return true if it is a power of two. Otherwise, return false.

An integer n is a power of two, if there exists an integer x such that n == 2x.

 

Example 1:

Input: n = 1
Output: true
Explanation: 20 = 1

Example 2:

Input: n = 16
Output: true
Explanation: 24 = 16

Example 3:

Input: n = 3
Output: false

 

Constraints:

• -231 <= n <= 231 - 1

 

Follow up: Could you solve it without loops/recursion?

Solutions

Solution 1: Bit Manipulation

According to the properties of bit manipulation, executing $\texttt{n\&(n-1)}$ can eliminate the last bit $1$ in the binary form of $n$. Therefore, if $n > 0$ and $\texttt{n\&(n-1)}$ results in $0$, then $n$ is a power of $2$.

The time complexity is $O(1)$, and the space complexity is $O(1)$.

Solution 2: Lowbit

According to the definition of $\text{lowbit}$, we know that $\text{lowbit}(x) = x \& (-x)$, which can get the decimal number represented by the last bit $1$ of $n$. Therefore, if $n > 0$ and $\text{lowbit}(n)$ equals $n$, then $n$ is a power of $2$.

The time complexity is $O(1)$, and the space complexity is $O(1)$.

• Java
• C++
• Python
• Go
• TypeScript
• Javascript
• Rust

• class Solution {
      public boolean isPowerOfTwo(int n) {
          return n > 0 && (n & (n - 1)) == 0;
      }
  }
  
  
  // Solution 2
  class Solution {
      public boolean isPowerOfTwo(int n) {
          return n > 0 && n == (n & (-n));
      }
  }
  
  

• class Solution {
  public:
      bool isPowerOfTwo(int n) {
          return n > 0 && (n & (n - 1)) == 0;
      }
  };
  
  
  // Solution 2
  class Solution {
  public:
      bool isPowerOfTwo(int n) {
          return n > 0 && n == (n & (-n));
      }
  };
  
  

• class Solution:
      def isPowerOfTwo(self, n: int) -> bool:
          return n > 0 and (n & (n - 1)) == 0
  
  
  # Solution 2
  class Solution:
      def isPowerOfTwo(self, n: int) -> bool:
          return n > 0 and n == n & (-n)
  
  

• func isPowerOfTwo(n int) bool {
  	return n > 0 && (n&(n-1)) == 0
  }
  
  
  // Solution 2
  func isPowerOfTwo(n int) bool {
  	return n > 0 && n == (n&(-n))
  }
  
  

• function isPowerOfTwo(n: number): boolean {
      return n > 0 && (n & (n - 1)) === 0;
  }
  
  
  // Solution 2
  function isPowerOfTwo(n: number): boolean {
      return n > 0 && n === (n & -n);
  }
  
  

• /**
   * @param {number} n
   * @return {boolean}
   */
  var isPowerOfTwo = function (n) {
      return n > 0 && (n & (n - 1)) == 0;
  };
  
  
  // Solution 2
  /**
   * @param {number} n
   * @return {boolean}
   */
  var isPowerOfTwo = function (n) {
      return n > 0 && n === (n & -n);
  };
  
  

• impl Solution {
      pub fn is_power_of_two(n: i32) -> bool {
          n > 0 && (n & (n - 1)) == 0
      }
  }
  
  
  // Solution 2
  impl Solution {
      pub fn is_power_of_two(n: i32) -> bool {
          n > 0 && n == (n & (-n))
      }
  }
  
  

All Problems

All Solutions