Today I needed a simple algorithm for checking if a number is a power of 2.

The algorithm needs to be:

- Simple
- Correct for any
`ulong`

value.

I came up with this simple algorithm:

```
private bool IsPowerOfTwo(ulong number)
{
if (number == 0)
return false;
for (ulong power = 1; power > 0; power = power << 1)
{
// This for loop used shifting for powers of 2, meaning
// that the value will become 0 after the last shift
// (from binary 1000...0000 to 0000...0000) then, the 'for'
// loop will break out.
if (power == number)
return true;
if (power > number)
return false;
}
return false;
}
```

But then I thought, how about checking if `log`

is an exactly round number? But when I checked for 2^63+1, _{2} x`Math.Log`

returned exactly 63 because of rounding. So I checked if 2 to the power 63 is equal to the original number - and it is, because the calculation is done in `double`

s and not in exact numbers:

```
private bool IsPowerOfTwo_2(ulong number)
{
double log = Math.Log(number, 2);
double pow = Math.Pow(2, Math.Round(log));
return pow == number;
}
```

This returned `true`

for the given wrong value: `9223372036854775809`

.

Is there a better algorithm?

There's a simple trick for this problem:

Note, this function will report

`true`

for`0`

, which is not a power of`2`

. If you want to exclude that, here's how:## Explanation

First and foremost the bitwise binary & operator from MSDN definition:

Now let's take a look at how this all plays out:

The function returns boolean (true / false) and accepts one incoming parameter of type unsigned long (x, in this case). Let us for the sake of simplicity assume that someone has passed the value 4 and called the function like so:

Now we replace each occurrence of x with 4:

Well we already know that 4 != 0 evals to true, so far so good. But what about:

This translates to this of course:

But what exactly is

`4&3`

?The binary representation of 4 is 100 and the binary representation of 3 is 011 (remember the & takes the binary representation of these numbers). So we have:

Imagine these values being stacked up much like elementary addition. The

`&`

operator says that if both values are equal to 1 then the result is 1, otherwise it is 0. So`1 & 1 = 1`

,`1 & 0 = 0`

,`0 & 0 = 0`

, and`0 & 1 = 0`

. So we do the math:The result is simply 0. So we go back and look at what our return statement now translates to:

Which translates now to:

We all know that

`true && true`

is simply`true`

, and this shows that for our example, 4 is a power of 2.