Skip to content
DSA in JavaScript
Math & Bits

Is a power of two

Algorithm · Starter

Level: StarterBit Manipulation

Step through it: Bit Manipulation pattern

nums
4
1
2
1
2
running xor
0
·
·
·
·
·

Step 1 of 5

Goal: every number appears twice except one. Find the odd one out without extra memory. Trick: the XOR operation (^) turns two equal numbers into 0, and anything XOR 0 stays itself. So XOR everything together and the pairs vanish.

Given a positive integer, write a function to find if it is a power of two or not.

Naive solution

In naive solution we just keep dividing the number by two unless the number becomes 1 and every time we do so, we check that remainder after division is always 0. Otherwise, the number can't be a power of two.

Bitwise solution

Powers of two in binary form always have just one bit set. The only exception is with a signed integer (e.g. an 8-bit signed integer with a value of -128 looks like: 10000000)

1: 0001
2: 0010
4: 0100
8: 1000

So after checking that the number is greater than zero, we can use a bitwise hack to test that one and only one bit is set.

number & (number - 1)

For example for number 8 that operations will look like:

  1000
- 0001
  ----
  0111

  1000
& 0111
  ----
  0000

Code

isPowerOfTwo.js
/**
 * @param {number} number
 * @return {boolean}
 */
export default function isPowerOfTwo(number) {
  // 1 (2^0) is the smallest power of two.
  if (number < 1) {
    return false;
  }

  // Let's find out if we can divide the number by two
  // many times without remainder.
  let dividedNumber = number;
  while (dividedNumber !== 1) {
    if (dividedNumber % 2 !== 0) {
      // For every case when remainder isn't zero we can say that this number
      // couldn't be a result of power of two.
      return false;
    }

    dividedNumber /= 2;
  }

  return true;
}
isPowerOfTwoBitwise.js
/**
 * @param {number} number
 * @return {boolean}
 */
export default function isPowerOfTwoBitwise(number) {
  // 1 (2^0) is the smallest power of two.
  if (number < 1) {
    return false;
  }

  /*
   * Powers of two in binary look like this:
   * 1: 0001
   * 2: 0010
   * 4: 0100
   * 8: 1000
   *
   * Note that there is always exactly 1 bit set. The only exception is with a signed integer.
   * e.g. An 8-bit signed integer with a value of -128 looks like:
   * 10000000
   *
   * So after checking that the number is greater than zero, we can use a clever little bit
   * hack to test that one and only one bit is set.
   */
  return (number & (number - 1)) === 0;
}

References

Practice

Spotted a mistake or something unclear? Report it on GitHub.

On this page