Skip to main content

231. Power of Two

easy

Decide whether an integer is a power of two — ideally without a loop. A bit-trick favorite: powers of two are exactly the integers where (n & (n - 1)) == 0.

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 are exactly the positive integers with exactly one set bit in binary.

Hint 2

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

Hint 3

So the one-liner is: return n > 0 && (n & (n - 1)) == 0. The n > 0 guard rules out 0 and negatives.

Hint 4

Alternative: n & -n isolates the lowest set bit. If n & -n == n, n had only that one bit.

Solution approach

Reveal approach

Use the bit identity: powers of two have exactly one set bit, and n & (n - 1) clears the lowest set bit. So n is a power of two iff n > 0 and (n & (n - 1)) == 0. The n > 0 guard handles 0 (which has no set bits) and negatives (whose two's-complement representations have many set bits). O(1) time and space. A second equally-clean approach: n & -n returns the lowest set bit alone; if that equals n, then n had only that one bit. Both are interview-grade answers; pick whichever you can explain more clearly.

Complexity

Time
O(1)
Space
O(1)

Related patterns

  • bit-manipulation
  • math

Related problems

Asked at

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

  • Amazon
  • Microsoft
  • Apple

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →