Fast power-of-two check

power of two

Is N a power of two?

This fits into the "bit trick" category. How can you check if a number is a power of two, without writing a loop? Here is a method I found on a couple websites a few years back (can't remember which ones):

  if (n != 0 && (n & (n-1)) == 0) {
      /* n is power of two */
  }

The reason that "n & (n-1)" is zero for a power-of-two is shown in the picture. Subtracting one will only clear the highest bit if it is the only bit that is set (and powers-of-two are the only numbers that have only one bit turned on). However, you also have to check if n is zero, because anything & zero is zero.