easy

Power of Two

Check whether an integer is a power of two using a bit trick.

1. Define the problem

Power of Two

Given an integer n, return true if it is a power of two . Otherwise, return false. A power of two has exactly one set bit , so n & (n - 1) — the trick that clears the lowest set bit — leaves 0 only when n was a power of two.

Constraints

  • -231 ≤ n ≤ 231 - 1

Example

Inputn = 16
Outputtrue

Explanation 16 = 24, and its binary form 10000 has exactly one set bit.

2. Know the words first

In plain terms

Power of two
A number of the form 2^x for some non-negative integer x — 1, 2, 4, 8, 16, and so on.
3. Visualize the solution

Clear the lowest set bit and check what remains

Clear the lowest set bit and check what remains
Statusinit

n = 16 = 10000. n - 1 = 15 = 01111.

What happens in this step

n = 16, n - 1 = 15
  n     = 00010000
  n - 1 = 00001111

16 has a single set bit at position 4. Subtracting 1 flips that bit off and sets every bit below it to 1, so n - 1 shares none of n's bits — a promising sign for a power of two.
Step 1 of 6

Steps to visualize

  1. If n is 0 or negative, it cannot be a power of two — return false immediately.
  2. Compute n & (n - 1), which clears the lowest set bit.
  3. If n had exactly one set bit, this leaves 0.
  4. If any bits remain, n had more than one set bit and is not a power of two.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Clear the lowest set bit and check what remains
Statusinit

n = 16 = 10000. n - 1 = 15 = 01111.

What happens in this step

n = 16, n - 1 = 15
  n     = 00010000
  n - 1 = 00001111

16 has a single set bit at position 4. Subtracting 1 flips that bit off and sets every bit below it to 1, so n - 1 shares none of n's bits — a promising sign for a power of two.
Step 1 of 6
5. Solution

Solution

solution.tsTypeScript
function isPowerOfTwo(n) {
  if (n <= 0) {
    return false;
  }

  return (n & (n - 1)) === 0;
}
Time
O(1)
Space
O(1)
6. Test cases

Test cases

InputExpectedCovers
n = 16trueexample from the docstring
n = 1true2^0 is a power of two
n = 0falsezero has no set bits and is not a power of two
n = -16falsea negative value can never be a power of two
n = 218falsea value with more than one set bit
n = 1073741824truea large power of two near the 32-bit boundary
n = 3falsetwo adjacent set bits

Keep reading