C#

## Check if a Number is a Power of 2 in C#

In this article, we are going to learn the most efficient and popular solutions to a very common problem – checking if a number is a power of 2. While it seems an easy task, we will see that some of these solutions are faulty in presence of corner cases.

In the following sections, we are only going to describe constant-time solutions. Let’s dive in!

## A Solution Based on the Logarithm

The `Math` library provides the `Log2()` method, which accepts a `double` and returns its logarithm base 2. We know that the logarithm is the inverse of exponentiation, so how can we use this to establish if the given number is a power of 2? We need to make sure that `Log2()` returns a round number:

```var log = Math.Log2(n);
return log == Math.Floor(log) && n > 0;```

The ending `n > 0` is necessary because this expression evaluates to true:

` Math.Log2(0) == double.NegativeInfinity && Math.Floor(double.NegativeInfinity) == double.NegativeInfinity`

We have one last unsolvable problem: we are working with `double`s, which are affected by the rounding error. This means that, for huge numbers, the result could be wrong. For example, with `n = 9223372036854775809`, that function returns `true`, although it is not a power of 2 (the last digit is odd).

Let’s now see some reliable and correct approaches!

## Check Power of 2 With a Tricky Bitmask Solution

This and the next solutions are based on a simple and convenient property of all the powers of 2: at the bit-level, a power of 2 has only one bit set to 1, all the others are 0. Let’s see a first solution based on this idea:

`(n & (-n)) == n && n > 0;`

At the bit-level, `-n` means applying the two’s complement operation to `n`. For example, let’s take `n = 16`:

```16    0b0001_0000 &
-16   0b1111_0000 =
-------------------
16    0b0001_0000```

This equivalence is true only when `n` has a single bit set to 1. Let’s prove it by considering once again the binary representation of 16: `0b0001_0000`. If we negate this sequence of bits, we get `0b1110_1111`, then we have to add 1 to obtain the two’s complement value of 16, which is `0b1111_0000`.

When adding 1 to `0b1110_1111`, the carry is propagated 4 times, setting again to 1 the only bit that was initially up in 16. The carry’s propagation is what makes the bit-wise `&` return a non-zero result, but this is not enough because the expression’s result must be `n`.

### Another Example

Let’s see what happens with `n = 20`, where 2 bits are set in its binary representation:

```20    0b0001_0100 &
-20   0b1110_1100 =
-------------------
4     0b0000_0100```

Here, the carry is propagated only twice, eventually setting the 3rd bit to 1 (starting from the least significant bit). What about the 5th bit? That bit is `&`ed with the negation of itself, so the final result will not have that bit set. This simple demonstration should have convinced you that only the rightmost 1-bit is preserved when performing `n & (-n)`. Therefore, the only way to make that expression return `n` is to choose a number having a single bit set to 1, i.e. a power of 2.

Again, `n = 0` is a problematic case: `(0 & 0) == 0`. The fix is the same, let’s just make sure that `n` starts from 1.

Unfortunately, it’s not over yet. What if the type of `n` is not `int` but `ulong`? In this case, the compiler complains because we’re working with an unsigned type. As a work-around, we can rewrite `-n` as `~n + 1`, which is the two’s complement of `n`. The final solution becomes:

`(n & (~n + 1)) == n && n > 0`

Let’s now see another approach based on the bitmask concept.

The probably most popular solution is:

`(n & (n - 1)) == 0 && n > 0`

The underlying logic is not so different from the one of the previous solution. In this case, instead of negating the number, we subtract 1 from it. This means that if the number has only one bit set to 1, i.e. is a power of 2, `n - 1` resets that bit and set all the following 0s to 1s. In such cases, `n & (n - 1)` is always 0:

```16    0b0001_0000 &
15    0b0000_1111 =
-------------------
0     0b0000_0000```

Instead, if we set an additional bit to 1, like with `n = 20`:

```20    0b0001_0100 &
19    0b0001_0011 =
-------------------
16    0b0001_0000```

The subtraction would just affect the least significant bit, leaving the other one unaltered.

We should not be surprised to see `n > 0`, for `n = 0` the expression would mistakenly return `true`.

We’ve seen several approaches, but what about the in-built options?

## The Built-in Solution

Starting from .NET 6, there is a built-in method called `BitOperations.IsPow2()` that does exactly what we have been trying to do until now. We’ve implemented this method as the second bitmask-based solution, but with a further optimization:

```[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static bool IsPow2(int value) => (value & (value - 1)) == 0 && value > 0;```

As the name suggests, the attribute `MethodImplOptions.AggressiveInlining` tells the JIT compiler to override the heuristics and inline the method when possible.

## Conclusions

When we use .NET 6, `IsPow2()` is the way to go: it is an optimized version of the faster algorithm we have seen. For all the previous versions of .NET 6, we are forced to create our utility method, that wraps the current implementation of `IsPow2()`.

Code Maze

Share
Code Maze

## HttpClient vs RestSharp – Which One to Use in .NET

HttpClient and RestSharp are HTTP Client libraries that we can use to consume APIs. Working…

Updated Date Jul 7, 2022

## Testing Repository Pattern Using Entity Framework

Unit Testing is extremely important for creating robust software. It's very simple in principle but…

Updated Date Jul 6, 2022

## Shell Sort in C#

Have you ever needed to sort a list of items, but didn't want to use…

Updated Date Jul 5, 2022

## How to Resolve Instances With ASP.NET Core DI

In ASP.NET Core dependency injection, we usually register injectable dependencies at the start of our…

Jul 4, 2022