Is a power of two

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. 1: 0001
  2. 2: 0010
  3. 4: 0100
  4. 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.

  1. number & (number - 1)

For example for number 8 that operations will look like:

  1.   1000
  2. - 0001
  3.   ----
  4.   0111
  6.   1000
  7. & 0111
  8.   ----
  9.   0000

References