Skip to main content
Ace Hired
All coding problems

Power of Two

Easybit manipulationBit manipulationbit manipulationmatheasy

Maintained by Vikas D, software engineer

You receive a single integer n. Your job is to report whether n can be written as 2 raised to a non-negative whole power: 1, 2, 4, 8, 16, and so on. If such an exponent exists, return true; if not, return false.

Note that 1 counts as a power of two because it equals 2 to the zero. Zero and every negative number can never be a power of two, so those must always return false.

The input can be any 32-bit signed integer, which means it ranges from a large negative value up to a large positive one. A correct answer has to handle the edge cases at both ends, not just the small friendly numbers.

The fastest known approach hinges on how powers of two look in binary: each one has a single 1 bit and nothing else set, which gives a constant-time check.

Examples

Input: n = 1
Output: true

1 equals 2 to the zero, so it is a power of two.

Input: n = 16
Output: true

16 equals 2 to the fourth. In binary it is 10000, a single set bit.

Input: n = 3
Output: false

3 is 11 in binary, which has two set bits, so it sits between 2 and 4 rather than on a power.

Input: n = -4
Output: false

A power of two is always positive, so any negative input returns false even though 4 itself is a power of two.

Constraints

  • -2^31 <= n <= 2^31 - 1
  • n is a single 32-bit signed integer.
  • Return a boolean, not a number or string.

Visible test cases

  • isPowerOfTwo(0) == false
  • isPowerOfTwo(1) == true
  • isPowerOfTwo(2) == true
  • isPowerOfTwo(3) == false
  • isPowerOfTwo(16) == true
  • isPowerOfTwo(1024) == true
  • isPowerOfTwo(-4) == false

Hints

Hint 1

Powers of two are always strictly positive, so you can reject zero and every negative number up front.

Hint 2

Write a few powers of two in binary (1, 10, 100, 1000) and count the 1 bits in each. Notice they all have exactly one.

Hint 3

For a number with one set bit, subtracting 1 flips that bit to 0 and turns every lower bit to 1, so n and n-1 share no bits. Test that with a bitwise AND.

Loading the editor...

Approaches

Repeated division

Time O(log n) · Space O(1)

Keep dividing by 2 while the value stays even; a true power of two reduces all the way down to 1.

  1. If n is less than or equal to 0, return false immediately.
  2. While n is even and greater than 1, divide n by 2.
  3. After the loop, return true when n equals 1, otherwise false.
  4. Any odd factor other than the final 1 leaves a remainder and exposes the number as not a power of two.

Optimal single-bit check

Time O(1) · Space O(1)

A positive power of two has exactly one set bit, and for such numbers n & (n - 1) clears that bit and yields 0.

  1. Return false right away if n is not positive, since 0 and negatives can never qualify.
  2. Compute n & (n - 1).
  3. If the result is 0, n had a single set bit, so it is a power of two; return true.
  4. Otherwise n had more than one set bit, so return false.

Common mistakes

  • Forgetting the positivity guard: 0 & -1 is 0 and (-4) & (-5) can also surprise you, so without the n > 0 check those inputs wrongly look like powers of two.
  • Treating 1 as not a power of two. It is 2 to the zero and must return true.
  • Using n % 2 in a loop without first excluding n <= 0, which can loop forever or misclassify negatives.
  • Returning the integer result of n & (n - 1) instead of comparing it to 0 and returning a boolean.

Follow-up variations

  • Extend the same one-line trick to detect a power of four, where the single set bit must also land on an even position.
  • Without arithmetic operators, count the set bits and return true only when the count is exactly one.
  • Handle an unbounded big integer rather than a fixed 32-bit value and discuss how the binary trick still applies.
  • Given a power of two, return its exponent k such that n equals 2 to the k.

Recommended problems

Build the rest of your prep