Skip to main content

231. Power of Two

easy

Check whether an integer is a power of two. The textbook bit-trick: a positive integer is a power of two if and only if n & (n - 1) is zero.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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 == 2^x.

Constraints

  • -2^31 <= n <= 2^31 - 1

Examples

Example 1

Input
n = 1
Output
true

Explanation: 2^0 = 1

Example 2

Input
n = 16
Output
true

Explanation: 2^4 = 16

Example 3

Input
n = 3
Output
false

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Powers of two in binary have exactly one set bit. Anything else has zero or two-plus.

Hint 2

n & (n - 1) clears the lowest set bit. If n has exactly one set bit, the result is 0.

Hint 3

Don't forget the n > 0 check — n = 0 and negative numbers should return false.

Solution approach

Reveal approach

One-line trick. Return n > 0 && (n & (n - 1)) == 0. The first conjunct rejects zero and negatives (which the constraints allow). The second exploits that powers of two have a single set bit, so n - 1 flips that bit to zero and turns every lower bit into one — AND'ing gives zero. Any other positive number has at least two set bits and one will survive the AND. O(1) time, O(1) space.

Complexity

Time
O(1)
Space
O(1)

Related patterns

  • bit-manipulation

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Apple

Practice these live with InterviewChamp.AI

Drill Power of Two and Bit Manipulation problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →